LinkedList 源码分析

双向链表,同时实现 List 和 Deque:两端增删 O(1),按下标访问 O(n),非线程安全。
整个类的核心只有三样东西:first/last 两根裸指针、私有的 Node 节点、一组 link*/unlink* 原语——所有公开 API(add/get/offer/poll/push/pop)都是这几个原语的薄包装。

// 基于 JDK 25 (本地 JAVA_Source 仓), java.util.LinkedList —— 骨架与链接/断链原语
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;    // JDK 6 及以前用环形哨兵节点，JDK 7 起改成 first/last 裸指针：空表零分配，代价是每个操作都要判 null

    /**
     * Pointer to last node.
     */
    transient Node<E> last;     // 不变式：size==0 时两者皆 null；否则 first.prev==null 且 last.next==null

    // ... 构造器略：LinkedList() 是空方法体，LinkedList(Collection) 就是 this() + addAll(c)，没有任何"预分配容量"的概念

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;         // 原本是空表：新节点同时是尾
        else
            f.prev = newNode;
        size++;
        modCount++;                 // 结构性修改计数，迭代器 fail-fast 靠它
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;        // succ 是头，插到头前
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Unlinks non-null first node f.
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC   // 摘下的节点可能还被迭代器攥着，不断链会拖住元素不放
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    // ... unlinkLast 与 unlinkFirst 完全对称，略

    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;           // 删的是头
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;            // 删的是尾
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
}

// 基于 JDK 25 (本地 JAVA_Source 仓), java.util.LinkedList —— 下标访问路径（慢的根源）
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;        // 每次 get 都从头/尾重新走链表，没有任何位置缓存
}

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);          // 尾插短路，不走 node()；addAll 也是同样的特判
    else
        linkBefore(element, node(index));   // 贵在定位，接指针本身 O(1)
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {      // 折半：前半段从头走，后半段从尾走，最坏 size/2 步。常数砍半，量级仍是 O(n)
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// 基于 JDK 25 (本地 JAVA_Source 仓), java.util.LinkedList —— Deque 门面与 fail-fast 迭代器
// 当队列用（FIFO）：offer 尾进，poll 头出
public boolean offer(E e) {
    return add(e);
}

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);     // 空表返回 null 不抛异常。坑：LinkedList 允许存 null，返回 null 有歧义
}

// 当栈用（LIFO）：push/pop 都在头部；removeFirst 空表抛 NoSuchElementException
public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;    // 创建时抓拍 modCount，之后每步比对

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);    // 只在构造时定位一次，之后顺指针走——迭代器整趟遍历 O(n) 的关键
        nextIndex = index;
    }

    // ... hasNext / hasPrevious / nextIndex / previousIndex 略

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;           // 直接跟指针，不再调 node()
        nextIndex++;
        return lastReturned.item;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;    // 游标越过末尾时(next==null)从 last 起步：一根游标双向共用
        nextIndex--;
        return lastReturned.item;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;        // previous() 之后删：游标正指着被删节点，要挪开
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;         // 自己删的自己认账：同步计数，所以 Iterator.remove 不触发 fail-fast
    }

    // ... set / add / forEachRemaining 略

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

原理串讲

一次 list.add(e) 的完整链路是 add -> linkLast:拿住旧尾 l,new 一个 Node(l, e, null),把 last 指过去,再视 l 是否为 null 决定改 first 还是 l.next——全程只碰两三个指针,不碰其他节点,所以尾插永远 O(1),头插 addFirst -> linkFirst 完全对称。
真正的分水岭在 get(index):checkElementIndex 之后调 node(index) 从 first 或 last 一格一格走过去。
所以 for (int i = 0; i < size; i++) list.get(i) 是 O(n2);而 listIterator 只在构造时调一次 node(index) 定位,之后 next() 只做 next = next.next,整趟遍历 O(n)——“遍历 LinkedList 必须用迭代器/for-each”是机制问题,不是代码风格问题。
按值删除 remove(Object o) 同理:从头线性扫到第一个匹配节点再 unlink(null 和非 null 分成两个循环写,因为 null 没法调 equals)。

为什么 JDK 7 要把 JDK 6 的环形哨兵 header 节点改成 first/last 裸指针?哨兵能消掉所有 null 分支(头尾永远有”假节点”垫着),但空链表也得常驻一个对象,而且哨兵的 item 恒为 null,和”用户存的 null 元素”搅在一起容易出错。
裸指针版本每个 link/unlink 多两个 if,换来空表零分配和一条极简的不变式——源码里那段注释掉的 dataStructureInvariants 写得明白:size0 时两头皆 null,否则 first.prev </mark> null && last.next == null。

为什么 unlink 要把 item/prev/next 全部置 null,而不是摘下来就完事?节点摘链后本应整体不可达,但迭代器的 lastReturned、外部代码都可能还持有旧节点引用,不断链就会顺着 prev/next 拖住一整串已删除的元素。
clear() 里的原版注释说得更直白:逐个断链能帮助分代 GC(老年代节点引用新生代对象会增加 minor GC 扫描负担),并且保证即便还存在可达的迭代器,内存也照样能释放。

fail-fast 的账本是 modCount:迭代器创建时抓拍到 expectedModCount,之后任何绕过本迭代器的结构修改(包括同一线程在 for-each 里调 list.remove(o))都会让 checkForComodification 抛 ConcurrentModificationException;而 ListItr.remove() 调完 unlink 后手动 expectedModCount++ 把账对平——这就是”遍历中删除必须用 Iterator.remove”的出处。
注意它只是 best-effort 的报警器,不是并发保护。

设计取舍

每个元素一个 Node:两根指针加对象头,内存开销数倍于 ArrayList,且节点散落堆上、缓存命中率差。“链表插入 O(1)“的前提是已经拿到节点,先定位仍要 O(n)。
当纯队列或栈用,ArrayDeque 几乎总是更快(无节点分配、数组连续);LinkedList 的独特价值是同时需要 List 语义和两端 O(1)。
允许 null 元素,代价是 peek/poll 返回 null 分不清”空了”还是”存了个 null”;ArrayDeque 干脆禁 null 来消除歧义。
get/set/add/remove 带下标的版本都要走 node(),中间位置批量操作优先用 ListIterator 原地进行,而不是反复按下标调。
非线程安全,modCount 只报警不保护;并发场景换 ConcurrentLinkedQueue / LinkedBlockingQueue。

LinkedList 源码分析

原理串讲

设计取舍

延伸阅读