我们在单链表中，由于只有后继结点的指针域，所以如果我们需要查找上一个结点的时候，最坏的时间复杂度就是 O(n),因为我们每次都需要从头结点开始遍历。所以在后来者中提出了双向链表来解决单链表的问题。那什么是双向链表呢？双向链表就是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。具体的代码结构如下：

class Node { // 保存结点的数据 private T data; // 保存上一个结点的引用 private Node prev; // 保存下一个结点的引用 private Node next;}

在链表的操作中最重要的操作一般有以下两个：

插入结点

删除结点

下面将详细的告诉大家如何实现以上三种基本操作。

插入结点如何实现

双向链表的插入先需要判断几种情况：

如果为空链表，直接使用尾插法插入结点进入链表中，同时 head 结点和 tail 结点都将指向插入的这个结点。

如果不为空链表，但是插入的索引不合理，比如说小于 1（因为链表都是从 1 开始计数）或者大于链表的长度都是不合理的，这个时候需要输出错误警告信息。

当插入的位置合理时，如果是插入的头结点，直接使用头插法插入结点。

如果不是插入的头结点，假设插入结点为 s,插入索引为 index，则需要先找到 index-1 的结点 p,以及原来链表的 index 位置的结点 q,先将新插入的结点 node 的前驱设置为 p,后继设置为 q,然后再设置 p 的后继为 node, q 的前驱为 node,最后将链表的长度递增即可完成双向链表的插入操作。核心代码如下：

public void insert(T element, int index) { // 如果是空链表直接插入 if (head == null) { add(element); } else { if (index < 1 || index > size) { System.out.println("插入位置不合理"); } else if (index == 1) { addAtHead(element); } else { // 获取插入结点的前一个结点 Node prev = getNodeByIndex(index - 1); // 获取插入点的结点 Node next = prev.next; // 让新结点的 next 引用指向 next 结点， prev 引用指向 prev 结点 Node newNode = new Node(element,prev,next); // 让 prev 的 next 结点指向新结点 prev.next = newNode; // 让 prev 的下一个结点的 prev 指向新结点 next.prev = newNode; size++; } } }

删除结点如何实现

删除结点仍然需要判断以下几种情况:

当双向链表为空链表时当然就无法删除了，需要输出错误警告信息。

当双向链表不为空链表时，这时候就需要判断删除的结点下标是否不合理，不合理的情况和插入链表时一致，这个时候也需要输出错误警告信息。

如果删除的是头结点，只需要将头结点的后一个结点设置为头结点，并且将前驱设置为 null 即可，因为未被使用的结点对象会被 Java 的垃圾回收机制回收。

如果删除的不是头结点，就需要找到删除结点的前一个结点，将这个结点的后继指向为要删除结点的后继结点，然后将要删除结点的后继结点的前驱结点设置为要删除结点的前驱结点，最后将要删除结点的前驱和后继结点都设置为 null,这样 Java 的垃圾回收机制将会回收这个未被使用的结点。核心代码如下：

public void delete(int index) { if (size == 0) { System.out.println("该链表是空链表无法删除"); } else if (index < 0 || index > size - 1) { System.out.println("删除的位置不合法"); } Node node = null; if (index == 1) { node = head; head = head.next; head.prev = null; } else { // 获取删除结点的前一个结点 Node prev = getNodeByIndex(index - 1); // 获得将要被删除的结点 node = prev.next; // 让被删除结点的 next 指向被删除结点的下一个结点 prev.next = node.next; // 让被删除结点的下一个结点的 prev 指向 prev 结点 if (node.next != null) { node.next.prev = prev; } // 将被删除结点的 prev,next 引用赋给 null node.prev = null; node.next = null; } size--; }

总结

双向链表比单链表要复杂挺多的，而且考虑的东西更多，毕竟多了一个指针域，对于删除和插入结点时，需要格外小心，而且双向链表比单链表更占用空间，因为多了一个指针域，不过它的优点就是不只是可以从头结点开始遍历，也可以从尾结点开始遍历，提高了算法的时间性能，总而言之，就是用空间来换取了时间。