LinkedList 也是 Java 集合框架里很常见的一个 List 实现，但它和 ArrayList 的思路完全不一样。ArrayList 的核心是“动态数组”，而 LinkedList 的核心是“链表”。如果你把 ArrayList 理解成一排连续编号的格子，那 LinkedList 更像一串节点，每个节点记住自己的值，还记住前一个和后一个节点是谁。

类的整体结构

从源码设计上看，LinkedList 大致是这样：

        public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable

    

这里有两个很重要的信息：

• 它不只是 List
  它还实现了 Deque，所以天然支持双端队列操作。
• 它继承的是 AbstractSequentialList
  这个名字就已经说明定位了：顺序访问友好，不是随机访问友好。

这和 ArrayList 很不一样。ArrayList 更偏随机访问，LinkedList 更偏顺序结构操作。

底层核心字段

LinkedList 最重要的字段通常就是这几个：

        transient int size = 0;
transient Node<E> first;
transient Node<E> last;

    

含义分别是：

• size
  当前链表里有多少个元素
• first
  指向头节点
• last
  指向尾节点

你可以把一个链表理解成：null <- A <-> B <-> C -> null

这时：

• first 指向 A
• last 指向 C
• size 等于 3

这三个字段几乎决定了 LinkedList 的整体行为。

节点 Node 是什么

LinkedList 的真正存储单元不是元素本身，而是 Node。

源码思路大致像这样：

        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;
    }
}

    

这说明每个节点保存三样东西：

• item
  当前节点的值
• next
  下一个节点是谁
• prev
  上一个节点是谁

这就是“双向链表”的本质。 比如链表中间一个节点 B： A <-> B <-> C

那么：

• B.prev = A
• B.item = B 的值
• B.next = C

所以 LinkedList 的数据不是连续摆在一起的，而是一个个节点通过引用连起来。

为什么说它是双向链表

因为每个节点既知道前一个节点，也知道后一个节点。

这带来两个直接好处：

• 可以从头往后找
• 也可以从尾往前找

这也是为什么 LinkedList 在源码里查找某个 index 时，不一定总从头开始，而是会根据位置选择从 first 或 last 出发。

空链表长什么样

空链表时：

• size = 0
• first = null
• last = null 这很重要，因为很多插入删除逻辑都要分两种情况：
• 链表原来为空
• 链表原来不为空

源码里很多判断，都是围绕这个状态展开的。

头部插入 linkFirst

头插是 LinkedList 最典型的源码逻辑之一。思路大致是：

        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++;
}

    

把它拆开理解：

• 先记住旧头节点 f
• 创建一个新节点 newNode
  新节点的 prev 是 null，因为它要成为新的头
  新节点的 next 指向旧头 f
• first 指向新节点
• 如果原来链表为空
  说明旧头 f 是 null，此时 last 也要指向这个新节点
• 如果原来不为空
  让旧头的 prev 指向新节点
• size 加 1
• modCount 加 1

这个过程的关键点是： 头插不需要搬动其他元素，只改几个引用就行。

尾部插入 linkLast

尾插也类似：

        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++;
}

    

逻辑和头插对称：

• 先记住旧尾节点 l
• 新节点 prev 指向旧尾
• 新节点 next 是 null，因为它要成为尾节点
• 更新 last
• 如果原来为空，first 也指向它
• 否则让旧尾的 next 指向它
• 更新 size 和 modCount

这就是为什么 LinkedList 做尾插也很自然。

中间插入 linkBefore

如果不是头插或尾插，而是在某个节点前面插入，源码思路大致是：

        void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

    

这里的关键是 succ，表示后继节点，也就是“我要插在谁前面”。

假设原来：A <-> B <-> C

现在要在 B 前面插 X。

那么：

• succ 就是 B
• pred 就是 A
• 新节点 X 的 prev = A
• 新节点 X 的 next = B
• A.next 改成 X
• B.prev 改成 X

结果就变成：A <-> X <-> B <-> C

真正改动的只是几个引用。

删除节点 unlink

删除也是链表源码的重点。删除一个已知节点 x，思路通常是：

        E unlink(Node<E> x) {
    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;
}

    

这个方法非常关键，建议你彻底理解。

假设删除中间节点 B：A <-> B <-> C

删除后要变成：A <-> C

源码上做的事情是：

• 找到 B 的 prev，也就是 A
• 找到 B 的 next，也就是 C
• 让 A.next = C
• 让 C.prev = A

这样 B 就从链上被摘掉了。

然后源码还会做几件很重要的事：

• x.prev = null
• x.next = null
• x.item = null

目的主要是帮助 GC 更快回收，避免保留无意义引用。

为什么删除已知节点很快

因为不需要像 ArrayList 一样整体搬移元素。

数组删除时，后面元素要整体前移。 链表删除时，只要把前后节点重新接起来即可。

所以如果你已经拿到了要删的节点，删除本身是 O(1)。

但这里有一个非常重要的前提： 你得先拿到那个节点。

如果你是 remove(index)，那在删除之前还要先定位到第 index 个节点，这个定位过程通常是 O(n)。

所以源码层面真正准确的说法是：

• 节点断链是 O(1)
• 定位节点通常是 O(n)
• 所以按下标删除总体是 O(n)

按下标访问为什么慢

这要看 node(index) 这个方法。它是 LinkedList 的关键源码之一。

思路大致是：

        Node<E> node(int index) {
    if (index < (size >> 1)) {
        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;
    }
}

    

这个方法的含义是：

• 如果 index 在前半段
  从头开始往后找
• 如果 index 在后半段
  从尾开始往前找

举个例子： 假设 size = 100，要找 index = 80。

源码不会从 first 一直走 80 步，而是从 last 反向找，只走 19 步左右。

这是一个优化，但本质没变： 它还是线性查找，不是数组那种 O(1) 定位。

所以 LinkedList 的 get(index)、set(index)、add(index, e)、remove(index) 都会受 node(index) 影响。

get、set、add、remove 在源码里的本质

可以把这些常用方法压缩理解。

• get(index)

        public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

    

先检查下标，再调用 node(index) 找节点，再取 item。

性能瓶颈在 node(index)。

• set(index, element)

        public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

    

修改本身很快，但找到节点慢，所以总体还是 O(n)。

• add(index, element)

        public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
    linkLast(element);
    else
    linkBefore(element, node(index));
}

    

如果是在末尾加，直接 linkLast。 否则先 node(index) 找到位置，再 linkBefore。

• remove(index)

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

    

先找到节点，再断链。

你会发现，几乎所有按下标操作的瓶颈都不是“改动动作本身”，而是“找节点”。

为什么 LinkedList 不适合随机访问

源码原因非常直接：

它没有数组下标直接寻址能力 它只能沿着 next 或 prev 一步步走 每次 get(index) 都可能从头或尾重新找 所以如果你写这种代码：

        for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

    

对 ArrayList 问题不大。 对 LinkedList 就可能非常差，因为每次 get(i) 都要走链，整体可能接近 O(n²)。

所以遍历 LinkedList 更推荐：

• for-each
• Iterator
• 顺序从头到尾遍历

而不是反复按下标读取。

Deque 能力为什么天然适合它

LinkedList 实现了 Deque，这很符合它的结构特点。

比如这些方法：

• addFirst
  本质调用 linkFirst
• addLast
  本质调用 linkLast
• removeFirst
  本质删除 first
• removeLast
  本质删除 last
• peekFirst
  返回 first.item
• peekLast
  返回 last.item

因为它天生就维护头尾节点，所以作为双端队列用起来非常顺手。

这也是 LinkedList 比较典型的源码设计价值之一： 它不只是 List，更适合做双端队列。

迭代器为什么能顺序遍历

LinkedList 内部有一个 ListItr 之类的迭代器实现。它通常会维护：

• next
  下一个要返回的节点
• lastReturned
  上一个返回过的节点
• nextIndex
  当前迭代位置
• expectedModCount
  创建迭代器时记录的修改版本号

它的 next() 本质上就是：

检查并发修改 返回当前节点值 指针移动到下一个节点 由于链表本身就是顺序连接的，所以迭代器顺着 next 一路走即可。

modCount 和 fail-fast 机制

这也是源码里的高频点。

LinkedList 继承体系里有一个 modCount 字段，表示结构修改次数。每次发生这些操作时通常会增加：

• add
• remove
• clear

其他结构变化 而迭代器创建时会记录一个 expectedModCount。

之后每次迭代时都会检查：

当前 modCount 是否等于 expectedModCount 如果不等，说明迭代过程中链表被外部改了，于是抛出 ConcurrentModificationException。

这就是 fail-fast 机制。

它的目的不是线程安全，而是尽早暴露错误用法。

比如你一边用迭代器遍历，一边直接调用 list.remove()，就可能触发这个异常。

一个极简版源码思维模型

        class MyLinkedList<E> {
    Node<E> first;
    Node<E> last;
    int size;

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

    

用途

作为普通 List 的方法：

• add
• get
• set
• remove
• size

作为队列的方法：

• offer
• poll
• peek

作为双端队列的方法：

• offerFirst
• offerLast
• pollFirst
• pollLast
• peekFirst
• peekLast

作为栈的方法：

• push
• pop
• peek

它做的所有事，无非就是：

• 头插：改 first 和旧头的 prev
• 尾插：改 last 和旧尾的 next
• 中间插：把前驱、新节点、后继串起来
• 删除：把目标节点前后重新连起来
• 按下标访问：从头或尾走链找到节点
• 迭代器：顺着 next 逐个访问