双向链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从头节点依次顺序地向后遍历。要访问某个结点的前驱节点（插入、删除操作时），只能从头开始遍历，访问后继节点的时间复杂度为 $O(1)$ ，访问前驱节点的时间复杂度为 $O(n)$ 。

为了克服这个问题，引入了双向链表。双向链表有两个指针，一个指针指向本节点的直接后继节点，一个指针指向本节点的直接前驱节点。其结构如下图所示。

注意

也许在其他文章中会有下图的画法，图中的箭头都指向了数据区，但是指针的实际指向是节点。

为了避免误解，后续的文章中的配图都采用第一种画法。

在后续的图示中如果前驱指针和后继指针没有指向，则表示指针指向了 NULL。 不再单独在图上指示其指向了 NULL。

提示

在阅读本章之前请先阅读《单向链表》章节，一些链表的共同特性在单向链表章节提到过的，一般在后续章节会忽略或一笔带过。

节点存储结构

一个双链表的节点包括了一个数据域，和两个指针域，一个指针指向直接后继节点，一个指针指向直接前驱节点。其 Java 定义如下：

@NoArgsConstructor
@Data
public class Node<T> {
    /**
     * 数据
     */
    private T data;
    /**
     * 指向后继节点的指针
     */
    private Node<T> next;
    /**
     * 指向前驱节点的指针
     */
    private Node<T> pre;

    public Node(T data) {
        this.data = data;
    }
}
java

同样的双向链表有着与单向链表相同的问题，即无法随机访问。而且双向链表比单向链表需要更多的存储空间（因为多了一个指针）。

基本操作

首先需要定义双向链表的顺序表结构，该结构中包含头指针，尾指针和链表大小。代码如下：

public class DoubleLinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;
}
java

添加元素

双向链表添加元素同样有头插法和尾插法两种，但是因为需要操作两个指针，因此与单向链表的实现略有不同。

头插法

双向链表头插法的步骤如下：

将新节点的后继指向头节点
将头节点的前驱指向新节点
头指针指向新节点

代码实现如下：

    public void addFirst(T data) {
        Node<T> node = new Node<>(data);
        if (head == null) {
            head = tail = node;
        } else {
            node.setNext(head);  1
            head.setPrev(node);  2
            head = node;         3
        }
        size++;
    }
java

添加节点时首先判断头节点是否存在。如果不存在说明链表是空的将头指针和尾指针都指向这个新的节点。头节点存在时说明链表不为空，则按照上面的进行处理。操作图示如下：

当 ③ 执行完后，头指针由原来指向 a0 变为指向 new_node。①、② 顺序可互换。

尾插法

双向链表的尾插法步骤如下：

将尾指针的后继指针指向新节点；
将新节点的前驱指针指向尾节点；
将尾指针指向新节点。

代码实现如下：

public void addLast(T data) {
    Node<T> node = new Node<>(data);
    if (tail == null) {
        head = tail = node;
    } else {
        tail.setNext(node);  1
        node.setPrev(tail);  2
        tail = node;         3
    }
    size++;
}
java

操作图示如下：

①、② 顺序可互换。

插入元素

插入元素的流程与单向链表类似，此处不再赘述。具体实现代码如下：

public void add(int index, T data) {
    if (index < 0 || index > size) return;
    if (index == 0) {
        addFirst(data);
    } else if (index == size) {
        addLast(data);
    }else {
        Node<T> node = new Node<>(data);
        Node<T> next = get(index);    1

        node.setPrev(next.getPrev()); 2
        node.setNext(next);  3
        next.getPrev().setNext(node); 4
        next.setPrev(node);  5

        size++;
    }
}

public Node<T> get(int index) {
    if (index < 0 || index >= size) return null;
    Node<T> node = head;
    for (int i = 0; i < index; i++) {
        node = node.getNext();
    }
    return node;
}
java

代码图示如下：

注意

其中 24 步骤可以互换，并且必须在第 5 步之前。因为 2 和 4 还需要通过 next 获取上一个节点，当 5 执行完后 next 的上一个节点会变成新节点。如果先执行了第 5 步，会导致后续节点的链接错误。3可以在 1 之后的任意位置。这里一定要注意执行顺序。

删除元素

删除头部节点

双向链表的删除与单向链表也略有不同，单向链表只需要改头指针位置即可，双向链表除了需要改头指针外，还需要修改新指向的头节点的前驱指针为 null。具体代码如下：

public Node<T> removeFirst() {
    if (head == null) return null;
    Node<T> node = head;
    head = head.getNext(); 1
    node.setNext(null);    2
    head.setPrev(null);    3
    size--;
    if (size == 0) {
        tail = null;
    }
    return node;
}
java

修改头指针指向下一个节点
将原头节点的后继指针置空
将新头节点的前驱指针置空

图示如下：

删除尾部节点

在前面的单向链表章节讲到过，单向链表删除尾部节点的时间复杂度是 $O(n)$ ，因为单线链表无法直接通过尾节点获取到上一个节点。而双线量表可也通过尾节点获取到上一个节点，无需遍历整个链表。因此双向链表的删除尾部节点操作的时间复杂度是 $O(1)$ 。

public Node<T> removeLast() {
    if (tail == null) return null;
    Node<T> node = tail;
    tail = tail.getPrev(); 1
    node.setPrev(null);    2
    tail.setNext(null);    3
    size--;
    if (size == 0) {
        head = null;
    }
    return node;
}
java

尾指针指向其前驱节点
原尾节点的前驱指针置空
新尾节点的后继指针置空

图示如下：

删除指定位置的元素

删除指定位置的元素与单向链表的实现略有差异，单向链表需要获取到要删除节点的上一个节点。而双向链表可以直接获取要删除的节点，通过要删除节点的直接前驱指针和直接后继指针获取到其前后节点，然后将这两个节点连接起来。

public Node<T> remove(int index) {
    if (index < 0 || index >= size) return null;

    if (index == 0) {
        return removeFirst();
    }
    if (index == size - 1) {
        return removeLast();
    }

    Node<T> node = get(index);
    node.getPrev().setNext(node.getNext());  1
    node.getNext().setPrev(node.getPrev());  2
    node.setNext(null);
    node.setPrev(null);
    size--;
    return node;
}
java

代码图示如下：

查找元素、遍历元素

查找和遍历元素与单链表相同，此处省略。

但是要注意的是双向链表可以从尾部向前遍历，因此如果要反序遍历链表，只需要从尾部开始向前遍历即可。这一点是单向链表做不到的。

总结

双向链表相关操作的算法的时间复杂度与单向链表大致相同，如下：

算法	时间复杂度
插入元素（头插法）	$O(1)$
插入元素（尾插法）	$O(1)$
插入元素（按索引）	$O(n)$
查找元素	$O(n)$
删除头部元素	$O(1)$
删除尾部元素	$O(1)$
删除指定位置元素	$O(n)$

双向链表只有 删除尾部元素 算法与单向链表的时间复杂度不一样，有单向链表的 $O(n)$ 变为 $O(1)$ ，其他操作时间复杂度都一样。

节点存储结构​

基本操作​

添加元素​

头插法​

尾插法​

插入元素​

删除元素​

删除头部节点​

删除尾部节点​

删除指定位置的元素​

查找元素、遍历元素​

总结​