链表：从节点连接到 LinkedList 实现

第一次碰到“链表：从节点连接到 LinkedList 实现”，我以为把定义和代码记下来就算学会了。真正动手时才暴露出问题：第一次自己实现链表时，我在头节点、尾节点和空链表之间来回修补，才发现边界处理比节点类本身难得多。这次重学我刻意放慢了速度，先看它为什么出现，再看规则怎样工作，最后才落到实现。

链表不要求元素在内存中连续排列。每个节点除了保存数据，还保存与其他节点的关系。它牺牲随机访问能力，换来了无需整体搬移的连接方式。

它从哪里来

链表在二十世纪五十年代的符号计算与早期人工智能程序中迅速发展。那类程序需要频繁插入、删除不定长符号，连续数组并不方便，于是节点通过地址相连的表示方式成为重要工具，后来又进入 Lisp 等语言与通用集合库。

单向、双向与循环链表

单向链表只有 next，结构简单，适合只向前遍历。双向链表增加 prev，可以从两端移动，也能在已知节点时更方便地删除。循环链表让尾节点重新指向头节点，适合轮询、时间片调度等需要不断循环的场景。

单向、双向、循环链表和反转过程图

图：链表的类型、双向指针与反转过程

手写一个最小双向链表

public final class SimpleLinkedList<E> {
    private static final class Node<E> {
        E value;
        Node<E> prev;
        Node<E> next;

        Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> first;
    private Node<E> last;
    private int size;

    public void addLast(E value) {
        Node<E> oldLast = last;
        Node<E> node = new Node<>(oldLast, value, null);
        last = node;
        if (oldLast == null) first = node;
        else oldLast.next = node;
        size++;
    }

    public E remove(Node<E> node) {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null) first = next;
        else prev.next = next;
        if (next == null) last = prev;
        else next.prev = prev;
        size--;
        return node.value;
    }
}

删除时真正需要维护的是四条关系：前驱的 next、后继的 prev、可能变化的 first、可能变化的 last。边界节点没有前驱或后继，因此空链表、单节点链表、删除头尾必须单独验证。

操作复杂度

操作	复杂度	说明
访问第 k 个元素	`O(n)`	需要沿节点逐个移动
头部插入、删除	`O(1)`	已维护头指针
尾部插入、删除	`O(1)`	双向链表并维护尾指针时
删除已知节点	`O(1)`	前提是已经持有节点引用
按值删除	`O(n)`	先查找，再断开连接

LinkedList 不一定比 ArrayList 插入快

如果业务通过索引插入，LinkedList 先要走到目标位置，定位成本是 O(n)；ArrayList 虽要搬移元素，但连续内存和批量复制很高效。对于中小规模数据，ArrayList 往往仍然更快、更省内存。

LinkedList 更适合两端频繁操作或调用方已持有迭代位置的场景。不过在 Java 中，如果需求只是队列或栈，通常优先选择 ArrayDeque：它没有每个节点的对象和指针开销，缓存局部性也更好。

哨兵节点让边界更简单

双向链表哨兵节点结构图

图：哨兵节点把头尾边界统一成普通的指针重连

不使用哨兵时，插入头部、尾部和中间位置需要分别判断。加入不保存业务值的 head、tail 哨兵后，真实节点始终位于两者之间：

private final Node<E> head = new Node<>(null, null, null);
private final Node<E> tail = new Node<>(head, null, null);

{
    head.next = tail;
}

private void insertBefore(Node<E> next, E value) {
    Node<E> prev = next.prev;
    Node<E> node = new Node<>(prev, value, next);
    prev.next = node;
    next.prev = node;
    size++;
}

这样所有插入都可以归一为“在某节点前插入”，所有删除都可以归一为“连接前驱和后继”。代价是多两个固定节点，但代码分支明显减少。

按索引查找也可以做一半优化

双向链表维护 size 后，查找第 index 个节点可以选择从更近的一端出发：

private Node<E> nodeAt(int index) {
    if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
    if (index < size / 2) {
        Node<E> node = first;
        for (int i = 0; i < index; i++) node = node.next;
        return node;
    }
    Node<E> node = last;
    for (int i = size - 1; i > index; i--) node = node.prev;
    return node;
}

它把最坏遍历步数从接近 n 降到约 n/2，但数量级仍是 O(n)，不能包装成随机访问。

反转链表

单向链表反转的关键是先保存 next，再修改当前节点指向，否则剩余链条会丢失：

static <E> Node<E> reverse(Node<E> head) {
    Node<E> previous = null;
    Node<E> current = head;
    while (current != null) {
        Node<E> next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    return previous;
}

循环不变量是：previous 始终指向已经反转好的前半部分，current 指向尚未处理的第一个节点。

快慢指针与环检测

Floyd 算法让慢指针每次一步、快指针每次两步。若链表有环，两者最终会在环中相遇；若快指针到达 null，则无环。

static <E> boolean hasCycle(Node<E> head) {
    Node<E> slow = head;
    Node<E> fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

进一步把一个指针移回头部，再让两个指针同速前进，相遇位置就是环入口。这个结论来自路程关系，不应只背模板。

如何测试链表不变量

每次结构修改后至少验证：

空表时 first == null && last == null && size == 0。
非空时 first.prev == null、last.next == null。
从头向后和从尾向前遍历数量都等于 size。
对每个相邻节点都有 node.next.prev == node。
删除节点后不再能从头访问到它。

随机生成一组 addFirst/addLast/remove 操作，并与 Java 标准容器的结果对照，比只写几个固定案例更容易发现断链错误。

容易写错的地方

插入第一个节点时忘记同时设置 first 和 last。
删除最后一个节点后没有把头尾都恢复为 null。
先覆盖指针再读取旧的前驱或后继，导致链条丢失。
迭代过程中直接修改结构却不处理并发修改检测。
把“节点删除 O(1)”误解成“按值删除 O(1)”。

适用场景

链表的价值更多体现在组合结构中：LRU 缓存用“哈希表 + 双向链表”同时获得按键定位和顺序调整；HashMap 的桶冲突可能使用链表；邻接表也可以用链式结构保存图的边。

我的判断是：业务代码很少需要从零手写链表，但手写一次非常值得。它训练的不是 API 记忆，而是对引用关系、边界条件和不变量的敏感度。

自测

为什么单向链表无法仅凭当前节点 O(1) 删除它的前驱？
双向链表删除节点后需要保持哪些不变量？
LRU 为什么不能只用链表？
哪些情况下 ArrayDeque 比 LinkedList 更合适？