数据结构与算法 / 系统课时

双向链表

双向链表

双向链表在每个节点中同时保存前驱与后继引用,使遍历可以双向进行,也让已知节点附近的插入和删除无需从头寻找前驱。本课将实现一个可运行的双向链表,并准确区分“定位节点”和“修改指针”的成本。

学习目标

  • 理解 prev、next、head 与 tail 的协作关系。
  • 掌握头部、尾部和中间位置的插入与删除规则。
  • 能够分析双向链表的访问、修改和空间复杂度。

核心原理

单向链表只能沿 next 向后移动,双向链表则在节点中增加 prev。因此,从尾部向前遍历、删除已知节点、在已知节点前插入等操作更直接,但每个节点需要额外保存一个引用,维护指针时也必须保证两个方向一致。

双向链表节点与指针关系

插入新节点时,需要同时建立 newNode.prev、newNode.next,再修改相邻节点指向新节点。删除节点时,需要让前驱跳过目标节点指向后继,同时让后继反向指向前驱。若目标位于边界,还要更新 head 或 tail。非空时首节点的 prev、尾节点的 next 都应为空;空时两个端点都为空。相邻节点的两个链接要互相指回,并保持可达节点数等于 size。

完整可运行示例

下面的 Java 17 示例支持尾部追加、按下标插入、按下标删除,以及正向和反向遍历。nodeAt 会从距离目标更近的一端开始查找。

java
public class DoublyLinkedListDemo {

    private static final class Node {
        private final int value;
        private Node prev;
        private Node next;

        private Node(int value) {
            this.value = value;
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public void addLast(int value) {
        Node newNode = new Node(value);

        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }

        size++;
    }

    public void insert(int index, int value) {
        checkPositionIndex(index);

        if (index == size) {
            addLast(value);
            return;
        }

        Node target = nodeAt(index);
        Node predecessor = target.prev;
        Node newNode = new Node(value);

        newNode.prev = predecessor;
        newNode.next = target;
        target.prev = newNode;

        if (predecessor == null) {
            head = newNode;
        } else {
            predecessor.next = newNode;
        }

        size++;
    }

    public int remove(int index) {
        Node target = nodeAt(index);
        Node predecessor = target.prev;
        Node successor = target.next;

        if (predecessor == null) {
            head = successor;
        } else {
            predecessor.next = successor;
        }

        if (successor == null) {
            tail = predecessor;
        } else {
            successor.prev = predecessor;
        }

        // 断开被删除节点,便于调试并避免继续误用旧链接。
        target.prev = null;
        target.next = null;
        size--;

        return target.value;
    }

    public String forward() {
        StringBuilder result = new StringBuilder();
        Node current = head;

        while (current != null) {
            if (result.length() > 0) {
                result.append(" <-> ");
            }
            result.append(current.value);
            current = current.next;
        }

        return result.toString();
    }

    public String backward() {
        StringBuilder result = new StringBuilder();
        Node current = tail;

        while (current != null) {
            if (result.length() > 0) {
                result.append(" <-> ");
            }
            result.append(current.value);
            current = current.prev;
        }

        return result.toString();
    }

    public int size() {
        return size;
    }

    private Node nodeAt(int index) {
        checkElementIndex(index);

        if (index < size / 2) {
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current;
        }

        Node current = tail;
        for (int i = size - 1; i > index; i--) {
            current = current.prev;
        }
        return current;
    }

    private void checkElementIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(
                    "index=" + index + ", size=" + size
            );
        }
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException(
                    "index=" + index + ", size=" + size
            );
        }
    }

    public static void main(String[] args) {
        DoublyLinkedListDemo list = new DoublyLinkedListDemo();

        list.addLast(10);
        list.addLast(20);
        list.addLast(30);

        System.out.println("初始正向: " + list.forward());
        System.out.println("初始反向: " + list.backward());

        list.insert(1, 15);
        System.out.println("插入后: " + list.forward());

        int removed = list.remove(2);
        System.out.println("删除值: " + removed);
        System.out.println("删除后正向: " + list.forward());
        System.out.println("删除后反向: " + list.backward());
        System.out.println("size = " + list.size());
    }
}

运行命令

将代码保存为 DoublyLinkedListDemo.java,然后执行:

bash
javac -encoding UTF-8 DoublyLinkedListDemo.java
java DoublyLinkedListDemo

预期输出

text
初始正向: 10 <-> 20 <-> 30
初始反向: 30 <-> 20 <-> 10
插入后: 10 <-> 15 <-> 20 <-> 30
删除值: 20
删除后正向: 10 <-> 15 <-> 30
删除后反向: 30 <-> 15 <-> 10
size = 3

复杂度与易错点

操作 时间复杂度 说明
访问第 index 个节点 O(n)O(n) 从较近一端出发,走 min(index, size−1−index) 条链接,最坏仍为线性
已知节点后的插入 O(1)O(1) 不包含定位节点的时间
已知节点的删除 O(1)O(1) 必须同时修复前后两个方向
按下标插入或删除 最坏 Θ(n)\Theta(n) 首尾操作可常数完成,中间位置需要定位
保存全部节点 O(n)O(n) 每个节点额外保存一个 prev 引用

最常见的错误是只修改一个方向。例如删除中间节点时只执行 predecessor.next = successor,却忘记 successor.prev = predecessor,正向遍历可能正常,反向遍历却会返回已删除节点。另一个易错点是空链表和单节点链表:删除唯一节点后,head 与 tail 都必须变为 null。

调试时应验证正反向的节点身份顺序和 size,尤其在存在重复值时,值序列一致还可能掩盖错误链接。常数时间的已知节点修改假定调用方已定位到该链表中的合法活节点。这里的公开接口仍按下标定位。

本课练习

  1. 为示例增加 addFirst(int value),并验证空链表与非空链表两种情况。验收条件是正向遍历从新值开始,反向遍历以新值结束,size 正确增加。
  2. 增加 removeValue(int value),只删除第一次出现的目标值。输入链表为 10 <-> 20 <-> 20 <-> 30 时,删除 20 后应得到 10 <-> 20 <-> 30,且双向遍历结果一致。

本课总结

  • 双向链表用额外的 prev 引用换取双向遍历和更直接的局部修改。
  • 已知节点时插入和删除为 O(1)O(1),按下标操作通常仍因定位节点而达到 O(n)O(n)。
  • 每次结构修改都要同步维护 head、tail、prev、next 与 size。

下一课预告

下一课将学习“栈”,理解后进先出的访问约束,并用入栈、出栈和栈顶操作解决括号匹配等问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

双向链表

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通