大话数据结构五：线性表的链式存储结构（双向链表）

大话数据结构五：线性表的链式存储结构（双向链表）2014-12-281. 双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域，那么在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

2. 单链表和双向链表比较：

单链表：总是要从头到尾找结点，只能正遍历，不能反遍历。

双向链表：可以从头找到尾，也可以从尾找到头，即正反遍历都可以，可以有效提高算法的时间性能，但由于每个结点需要记录两份指针，所以在空间占用上略多一点，这就是通过空间来换时间。

3. Java实现双向链表：

// 双向链表public class DoubleLinkedList<E> {private Node<E> head; // 头结点private int size; // 链表长度// 建立一个空链表public DoubleLinkedList（） {head = null;size = 0;}// 在头结点前插入public boolean addBeforeHead（E data）{Node<E> newNode = new Node<E>（data）;if（isEmpty（））{head = newNode;}else{head.setPrev（newNode）;newNode.setNext（head）;head = newNode;}size++;return true;}// 在链表尾部插入public boolean addAfterTail（E data）{Node<E> newNode = new Node<E>（data）;if（isEmpty（））{head = newNode;}else{Node<E> tail = get（size）;tail.setNext（newNode）;newNode.setPrev（tail）; // 设置新结点的上一结点}size++;return true;}// 插入指定位置的结点public boolean insert（int position, E data） {if（position >= 1 && （position <= size + 1））{Node<E> newNode = new Node<E>（data）;if（isEmpty（） || position == 1）{ // 链表为空或在头结点前插入addBeforeHead（data）;}else if（position == size + 1）{ // 在尾结点后插入Node<E> preNode = get（position - 1）;newNode.setPrev（preNode）;preNode.setNext（newNode）;}else{ // 在其他位置插入Node<E> preNode = get（position - 1）; // 获取position的前一结点Node<E> afterNode = preNode.getNext（）; // 获取未插入结点时position位置对应结点 newNode.setPrev（preNode）; // ①newNode.setNext（afterNode）; // ②afterNode.setPrev（newNode）; // ③preNode.setNext（newNode）; // ④}size++;return true;}return false;}// 删除指定位置的结点public E delete（int position） { E result = null;if（position >= 1 && position <= size）{if（position == 1）{ // 删除头结点result = head.getData（）;Node<E> afterHead = head.getNext（）;afterHead.setPrev（null）;head.setNext（null）;head = afterHead; }else if（position == size）{ // 删除尾结点Node<E> preNode = get（position - 1）; // 获取待删除结点的前一结点Node<E> delNode = preNode.getNext（）; // 获取待删除结点result = delNode.getData（）;preNode.setNext（null）;}else{ // 删除其他结点Node<E> preNode = get（position - 1）; // 获取待删除结点的前一结点Node<E> delNode = preNode.getNext（）; // 获取待删除结点result = delNode.getData（）;Node<E> nextNode = delNode.getNext（）;// 获取待删除结点的下一结点preNode.setNext（nextNode）; // ①nextNode.setPrev（preNode）; // ②}size--;}return result;}// 获取某个位置的结点（正序遍历）public Node<E> get（int position）{Node<E> targetNode = null;if（！isEmpty（） && position >= 1 && position <= size）{ targetNode = head;for（int i = 1; i < position ; i++）{targetNode = targetNode.getNext（）; // 循环获取对应位置的结点}}return targetNode;}// 获取链表的长度public int getSize（）{return size;}// 判断链表是否为空public boolean isEmpty（）{return size == 0;}// 打印链表数据public void display（）{Node<E> node = head;System.out.print（"双向链表: "）;for（int i = 0; i < size; i++）{System.out.print（" " + node.getData（））;node = node.getNext（）;}System.out.println（""）;}}

//结点类，包含结点的数据和指向下一个节点的引用public class Node<E> {private E data; // 数据域private Node<E> next; // 指针域保存着下一节点的引用private Node<E> prev; // 指针域保存着上一节点的引用 （相比单链表，双向链表多了这个指针）public Node（） {}public Node（E data） {this.data = data;}public Node（E data, Node<E> next, Node<E> prev） {this.data = data;this.next = next;this.prev = prev;}public E getData（） {return data;}public void setData（E data） {this.data = data;}public Node<E> getNext（） {return next;}public void setNext（Node<E> next） {this.next = next;}public Node<E> getPrev（） {return prev;}public void setPrev（Node<E> prev） {this.prev = prev;}}

public class Main {public static void main（String[] args） {DoubleLinkedList<Integer> dll = new DoubleLinkedList<Integer>（）;dll.addBeforeHead（2）;dll.addAfterTail（3）;dll.addBeforeHead（1）;dll.display（）;dll.insert（4,4）;dll.insert（5,5）;dll.insert（6,6）;dll.display（）;dll.delete（6）;dll.delete（3）;dll.delete（1）;dll.display（）;System.out.println（"双向链表的长度为:" + dll.getSize（））;}}

作者：csdn博客 zdp072