LinkedList源码解析：双向链表如何实现栈、队列与Deque

1. 为什么说 LinkedList 是集合框架里的“多面手”

很多刚接触 Java 集合框架的人，最早背的就是 ArrayList 和 LinkedList 的区别：一个“查询快、增删慢”，一个“增删快、查询慢”。这个结论没错，但如果你对自己的要求只是背下这句话，那面对稍微绕一点的面试题或者实际业务场景，基本就露馅了。比如“LinkedList 和 ArrayDeque 谁能当队列用”“LinkedList 的 node(int index) 是怎么找下标的”“为什么 LinkedList 实现了 Deque 接口却不建议用它做栈”——这些问题，只有真正把它的底层结构弄明白，才能答得透。

从 Java 源码来看，LinkedList 是一个同时实现了 List 接口和 Deque 接口的双向链表。这意味着它既能当列表用，也能当队列用，还能当栈用，是集合框架里少见的“多面手”。我最初看源码的时候也很疑惑，为什么一个看似简单的链表类要背上这么多接口。后来在实际开发里写缓存队列、实现 LRU 淘汰、处理撤销操作时才发现，这个“多面手”的设计其实非常实用，尤其在小数据量的场景下，往往一个 LinkedList 就能解决两三个数据结构的问题，省得再专门引入别的容器。

这篇文章不是教科书式的源码注释，而是基于我对 LinkedList 源码的阅读和实际项目中的使用经验，把“链表怎么存数据”“栈和队列怎么用 LinkedList 实现”“性能瓶颈到底在哪”“哪些坑是网上没人明说的”这些点从头到尾捋一遍。适合两类人：一是准备面试、想深入掌握集合框架的求职者，二是在项目中经常做数据暂存、需要灵活选择容器的开发者。你不需要提前读过源码，跟着文章的思路走，看完就能直接上手用，也敢跟别人聊底层了。

2. 链表的设计思路：用“节点”把数据串起来

2.1 节点结构：一前一后两个指针搞定了什么

LinkedList 的底层不是数组，而是一串“节点”。每个节点（源码里叫 Node）只有三个字段：item（存放的数据）、prev（指向前一个节点的引用）、next（指向后一个节点的引用）。你可以把节点想象成火车车厢，每节车厢里放着货物（item），车厢之间通过挂钩（prev 和 next）连在一起。整列火车不需要一段连续的轨道，只要有路，每一节车厢都能找到下一节。

// JDK 源码中 LinkedList 节点的简化表示 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; } }

正因为这个结构，LinkedList 才能做到“增删不掉性能”——它不需要像 ArrayList 那样在中间插元素时把后面的元素整体搬移，只需要修改前后两个节点的引用即可。同样是插入一个元素，ArrayList 的时间复杂度是 O(n)，LinkedList 修改指针是常数时间，只是定位到插入位置本身的代价需要另算。

整个 LinkedList 类本身维护三个核心字段：size（元素个数）、first（头节点）、last（尾节点）。头尾节点是链表操作的“锚点”，无论是 addFirst 还是 addLast，都是在锚点位置附近做指针调整。这也是为什么 LinkedList 在头部和尾部插入元素特别快——它根本不需要遍历，直接改引用就行。理解了这三个字段，后面再看 add、remove、get 这些方法的源码，思路会清晰得多。

2.2 相比数组，链表的优势与代价

设计上，数组是一块连续内存，按下标访问可以直接通过“起始地址 + 下标 x 元素大小”算出内存位置，所以随机访问是 O(1)。链表则把数据分散在内存各处，每个节点通过引用相连，所以访问第 n 个节点必须从头一个一个跳过去，这是 O(n)。

但分散存储带来的好处是插入和删除不用大量搬移内存。ArrayList 在中间插入元素时，要 System.arraycopy 把后面的元素往后挪，数据量大的时候这个开销是很可观的。LinkedList 只需要断开两个引用、接上两个引用，理论上和列表长度无关。

代价也很明显：每个节点要额外存两个引用，内存占用比数组高。而且节点在内存里不是连续的，CPU 缓存的局部性差，遍历时容易频繁访问不同的内存页，实际速度往往比理论值更慢。所以 LinkedList 绝不是“增删一定快”的银弹，它只有在“已经站在目标位置附近”或者“只操作头尾”的时候，增删优势才真正体现出来。关于这个细节，后面专门有一节讲性能实测，先记住结论：小数据量场景用 LinkedList 很方便，大数据量场景要慎重。

2.3 Deque 接口的引入：为什么链表天然适合做栈和队列

LinkedList 从 Java 1.6 开始实现了 Deque 接口（Double Ended Queue，双端队列）。Deque 的意思是“两端都能进出”，既能队头操作，也能队尾操作。双端队列天然涵盖了栈和队列的所有操作，因为它既有 push/pop（栈的操作方法），也有 offer/poll（队列的操作方法）。

为什么偏偏是 LinkedList 来实现 Deque？因为双向链表的头尾操作都是 O(1)，只需要改 first/last 的引用。而如果用一个普通的数组结构做双端队列，头尾操作也可以很快，但容量固定后扩容会比较麻烦，而且从头部弹出元素时如果不做环形设计，就要移动整个数组。双向链表则天然没有容量上限，头部弹出的同时只需要更新 first 引用，没有任何数据搬移。

JDK 还有一个专门的 ArrayDeque 类也实现了 Deque，环型数组结构，性能甚至更好。但 LinkedList 的优势在于“同时还是个 List”，你既可以在这个数据结构上调用 List 的方法，也可以调用 Deque 的方法，非常灵活。具体用哪个，后面也会有分析。

3. 核心操作全解析：从源码角度看 add、remove、get

3.1 添加元素：头插、尾插、中间插各自经历了什么

LinkedList 的 add(E e) 方法默认是尾插。源码逻辑很简单：把当前尾节点记为 l，创建一个新节点（prev 指向 l，next 为 null），然后把 last 指向新节点。如果链表本来就是空的，那 first 也指向新节点；否则把 l 的 next 指向新节点。最后 size 加一，modCount 加一（modCount 是用于 fail-fast 机制的修改计数器，后面讲遍历时会提到）。

// JDK 源码中 add(E e) 的等价逻辑 public boolean add(E e) { linkLast(e); return true; } private 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++; }

addFirst(E e) 则是头插，逻辑是对称的：把当前 first 记为 f，创建新节点（next 指向 f，prev 为 null），把 first 指向新节点，如果链表为空则 last 也指向新节点，否则把 f 的 prev 指向新节点。这两个操作都不涉及循环，时间复杂度是真正的 O(1)。

中间插入 add(int index, E e) 麻烦一些，因为要先判断 index 是否越界（越界会抛 IndexOutOfBoundsException），再判断 index 是不是正好等于 size（等于就尾插，那可以直接走 linkLast 的快速路径），否则就要用 node(int index) 方法先找到那个位置的节点，再在它前面插入。这个“找节点”的过程就是链表随机访问的硬伤，后面单独说。

3.2 删除元素：解除引用比想象中的更讲究

remove() 不带参数，默认删除头节点，等价于 removeFirst()。源码里会先拿到 first，如果为空则抛 NoSuchElementException，否则把 first.item 置为 null（帮助 GC 回收），把 first.next 变成新的 first，同时把新 first 的 prev 置为 null。还要注意一个细节：被移除节点的 next 也要置为 null，否则它仍然会指向链表中的下一个节点，形成一条多余的引用链，导致内存无法被完全回收。这种细节在面试里拿出来讲，比单纯背“删除复杂度 O(1)”要有说服力得多。

// 删除头节点的等价逻辑 private E unlinkFirst(Node<E> f) { final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }

删除指定位置的 remove(int index) 也有 O(n) 的定位成本：先 checkElementIndex 判断，再 node(index) 找到目标节点，再 unlink(Node x)。unlink 的过程就是把前后节点的引用都绕过当前节点，同时把当前节点的 item、prev、next 全置为 null，保证链表断链干净。

有一点要提醒：LinkedList 支持删除 null 元素。remove(Object o) 会从头开始遍历，找到第一个 equals(o) 的节点（如果 o 是 null，则找 item 为 null 的节点），然后 unlink 它。如果你维护的数据不允许 null，最好在入队前就做非空校验，否则可能删错了才发现数据不符合预期。

3.3 查询元素：为什么 get(index) 是 O(n) 的重灾区

get(int index) 底层调用 node(int index) 方法。这个方法是链表性能分水岭：它先把 index 和 size >> 1（size 右移一位，即一半）比较，如果 index 更小，就从 first 往后遍历；如果 index 更大，就从 last 往前遍历。这就是一个经典的“二分方向优化”，说它“二分”不太准确，正确叫法是“折半查找方向优化”。

// 核心定位逻辑，面试常问 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; } }

这样设计很聪明，但无论从哪头开始，平均还是要遍历 n/4 次。比如 size 是 1 万，取中间位置大概要跳 2500 次。一次两次无所谓，但如果放进 for 循环里频繁调用，比如 for (int i = 0; i < list.size(); i++) list.get(i)，复杂度就变成 O(n^2) 了，数据量稍微大一点，程序直接卡到你怀疑人生。这个问题在后面“常见问题与排查”里会再拎出来详细说。

关于查询，还有一个高频操作是 indexOf(Object o)，它同样需要从头遍历，返回第一个匹配项的索引。你要是对一个百万级数据的 LinkedList 调 indexOf，就得有等待的心理准备，这个接口的设计本意就是给链表用的，O(n) 是绕不开的。

3.4 迭代器的秘密：为什么它有 fail-fast 行为和 ListIterator

LinkedList 的迭代器不只是简单遍历，它还支持反向遍历、边遍历边插入、边遍历边删除。ListIterator 提供了 previous()、hasPrevious()、add(E e)、set(E e) 等方法，这对“反向遍历的同时修改元素”的场景特别友好。前面提到的 modCount 在这里就发挥作用：迭代器在创建时会记录 expectedModCount = modCount，每次调用 next/previous 前会检查两者是否一致，不一致就抛 ConcurrentModificationException。

// 迭代器检查修改冲突的关键逻辑 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); }

这个机制叫 fail-fast，意思是“一旦检测到并发修改，立刻失败，而不是继续往下走导致未知行为”。它不是为了解决并发问题，而是为了快速暴露bug。所以你在迭代 LinkedList 的过程中，绝对不能调用 list.add()、list.remove() 这类结构性修改方法，否则就会触发异常。正确的做法是用迭代器自己的 add() 和 remove()，因为它们会把 expectedModCount 同步更新。

ListIterator 还有一点很实用：listIterator(int index) 可以指定从某个位置开始遍历。由于双向链表的特性，这个“从指定位置开始”并不是直接跳过去的，而是调用 node(index) 先定位到那个节点，再以它为起点。源码里的 ListItr 构造器就是这么干的：LinkedList.this.node(index) 赋值给 next。定位本身是 O(n)，好在定位之后“向前/向后”都是 O(1)。

4. 用 LinkedList 实现栈和队列：正确姿势与性能对比

4.1 栈操作：push/pop/peek 的源码级玩法

栈的特点是后进先出（LIFO）。LinkedList 的 Deque 接口里正好有 push（压栈）、pop（出栈）、peek（看栈顶）。你可以直接用 addFirst 和 removeFirst 理解它的实现逻辑，其实 push 就是 addFirst，pop 就是 removeFirst，peek 就是 getFirst。

// 用 LinkedList 当栈使用 LinkedList<String> stack = new LinkedList<>(); stack.push("第一层"); stack.push("第二层"); stack.push("第三层"); System.out.println(stack.pop()); // 输出：第三层 System.out.println(stack.peek()); // 输出：第二层（只看不弹）

这里有一个细节值得注意：Java 还有一个遗留类 Stack ，老祖宗，能不用尽量别用。原因很简单——它继承了 Vector，所有方法都加了 synchronized，性能有额外开销。更尴尬的是它居然还继承了 Vector 的 get(int index) 这样的随机访问方法，导致“栈”不纯粹，随时能从中间捞元素。所以无论是《Java 编程思想》还是实际项目里的代码规范，都推荐用 ArrayDeque 或 LinkedList 来实现栈。LinkedList 在“栈”这个角色上的优势和劣势一样明显：优势是方便，劣势是内存占用大，每个元素都要包两层引用。

如果只是在同一个线程内做深度优先遍历、回溯之类的操作，LinkedList 足够好用。但如果确定要频繁 push/pop 且数据量较大，ArrayDeque 的内存效率更高，后面会给数据对比。

4.2 队列操作：offer/poll/element 的取舍逻辑

队列的特点是先进先出（FIFO）。LinkedList 作为队列，最常用的三个方法是 offer（尾部入队）、poll（头部出队）、peek（查看头部不删除）。add 方法和 offer 方法的区别在于：队列满时（比如有界队列）add 会抛异常，offer 会返回 false。LinkedList 是无界的，这两个方法其实不会因为容量问题报错，但为了语义统一，建议用 offer/poll/peek，因为这组方法在队列接口里是标准玩法，代码可读性更好，未来换成 ArrayBlockingQueue 之类有界队列时也不需要改调用逻辑。

// 用 LinkedList 当 FIFO 队列 LinkedList<Task> queue = new LinkedList<>(); queue.offer(new Task("任务A")); queue.offer(new Task("任务B")); Task first = queue.poll(); // 取出任务A并删除 Task next = queue.peek(); // 查看任务B，但队列里仍保留

队列场景中，LinkedList 的 addLast/removeFirst 都是 O(1) 操作，只需要改 first 和 last 的引用，性能非常稳定。它适合做“任务队列”“延迟队列（配合定时扫描）”“日志缓冲队列”等实现。数据量小的时候你用 LinkedList 和 ArrayDeque 体感没什么差别，数据量大时 ArrayDeque 明显更省内存。但是 ArrayDeque 不允许存 null，如果你有存 null 的奇怪需求，LinkedList 反而是更宽松的选择。

4.3 与 ArrayDeque 的实战对比：数据说话

很多人问我：为什么网上说“Stack 别用，队列尽量用 ArrayDeque”？我用一个简单的内存对比实验来说清楚。假设存 100 万个 Integer 对象，ArrayDeque 只需要一个 Object[] 数组存引用，数组容量是 2 的幂，刚好 2^20 = 1,048,576 个引用，加上少量头尾索引字段，内存开销大约数组大小 × 8 字节（引用在 64 位 JVM 上），大概 8MB 多些，容量不满时还要考虑扩容产生的额外空间。LinkedList 则每个元素额外携带两个 Node 引用和一个 Node 对象头，一个 Node 对象在 64 位 JVM 里大概是 24 字节（对象头 + item + prev + next 对齐），100 万个节点光是对象头就有 2400 万字节，即约 24MB，再加上实际数据的引用，轻松超过 30MB。也就是说，同样的队列数据，LinkedList 的内存占用通常是 ArrayDeque 的 3 到 5 倍，这还不算 CPU 缓存局部性的差距。

下面用一张表对比几个关键维度：

结论很清晰：如果只是想用“栈”或“队列”的语义，ArrayDeque 是更好的默认选择；但如果你需要同一个对象既支持按索引存取（List 行为），又支持头尾操作（Deque 行为），那 LinkedList 是唯一选择。很多实际业务场景里，数据量也就几百上千，LinkedList 完全够用，不需要为了理论上的性能优势把代码结构搞复杂。

5. 手写一个极简双向链表：把原理变成肌肉记忆

5.1 手写结构：只保留最核心的增删查

看完源码之后，真正能检验你理解程度的做法，是自己在理解的基础上手写一个简化版的双向链表。不需要把泛型、迭代器那些东西写全，只保留 addLast、addFirst、removeFirst、get 这几个操作，就足以让你把 node(index) 的定位逻辑、unlink 的断链逻辑、linkLast 的接链逻辑全部串起来。

下面是我用手写方式整理的一个 Demo。它不是生产级代码，但能让你看到 LinkedList 最核心的运行骨架：

public class MyLinkedList<E> { private Node<E> first; private Node<E> last; private int size; private static class Node<E> { E item; Node<E> prev; Node<E> next; Node(Node<E> prev, E item, Node<E> next) { this.prev = prev; this.item = item; this.next = next; } } public void addLast(E e) { Node<E> l = last; Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) { first = newNode; } else { l.next = newNode; } size++; } public void addFirst(E e) { Node<E> f = first; Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) { last = newNode; } else { f.prev = newNode; } size++; } public E removeFirst() { if (first == null) { throw new NoSuchElementException(); } E item = first.item; Node<E> next = first.next; first.item = null; first.next = null; first = next; if (next == null) { last = null; } else { next.prev = null; } size--; return item; } public E get(int index) { checkIndex(index); return node(index).item; } private 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; } } private void checkIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("index: " + index + ", size: " + size); } } }

写完之后你会明显感受到，LinkedList 的代码逻辑其实并不复杂，关键就是别搞乱 prev 和 next 的方向。尤其在 addFirst 和 removeFirst 的时候，稍微一走神就容易把 first 和 last 的更新条件写反。我自己手写的时候，在“空链表插入第一个节点”和“删除最后一个节点”这两个极端情况上各踩过坑，你写的时候也可以多测测这两种边界。

5.2 和 JDK 源码的差异在哪：modCount 等细节的作用

手写版和 JDK 源码之间的差距主要在细节处理上。JDK 的 LinkedList 增加了 modCount 计数器用于 fail-fast 迭代保护；增加了 node(int index) 的折半查找优化；对 add(int index, E e) 做了 index == size 时走 linkLast 快速路径的特判；对 remove(Object o) 分了 o == null 和 o != null 两种情况遍历；还重写了 toString、clone、toArray 等方法。

这些细节单独看都“可有可无”，但合在一起就是工程级代码和教学代码的本质区别。手写时你可能觉得“不检查 modCount 也没事”，可一旦这个集合在迭代过程中被其他线程修改，你拿到的数据就可能出现前后矛盾、元素丢失甚至死循环。modCount 的设计就是用一次快速异常来兜底不确定的行为。建议你在手写版本上把 modCount 加上，然后试着在迭代中调用 add，看看那个异常是怎么触发、怎么帮你定位问题的，体会会更深。

6. 实战场景：LinkedList 在算法题和业务开发中的典型用法

6.1 经典场景一：链表反转（迭代与递归思路）

链表反转是面试里的“熟面孔”，它的核心操作就是反复修改节点的 next 方向。LinkedList 自带的 DescendingIterator 确实能实现反向遍历，但“真正反转一个链表”这个操作，JDK 没有直接提供现成方法，你需要自己写。这也是很多面试官喜欢让你手写的原因，它能检验你是否真的理解指针调整。

迭代法反转的核心思路：用一个 prev 变量记录当前节点的前一个节点，遍历时先保存当前节点的 next，然后把当前节点的 next 指向 prev，接着把 prev 移动到当前节点，当前节点移动到刚才保存的 next。

// 反转一个单向链表（伪代码风格便于理解） public Node<E> reverse(Node<E> head) { Node<E> prev = null; Node<E> current = head; while (current != null) { Node<E> next = current.next; current.next = prev; prev = current; current = next; } return prev; }

递归法写起来很简洁，但如果链表很长，递归深度过大会导致栈溢出。所以实际生产环境里，我更喜欢用迭代法。LinkedList 的节点是私有静态内部类，你没法直接从外部拿到 Node 来反转，所以刷题时一般自己定义一个单链表节点结构，或者用现成的集合转成数组再操作。但理解反转的指针变化过程，绝对能帮你更好地理解 ArrayList、LinkedList 的差异。

6.2 经典场景二：LRU 缓存的简易实现

LRU（Least Recently Used，最近最少使用）缓存实际上很适合用 LinkedList 配合 HashMap 来实现。Java 官方的 LinkedHashMap 本身就是“HashMap + 双向链表”的结构，能实现访问顺序记录。但如果你不想用 LinkedHashMap，或者想理解 LRU 的原理，LinkedList 也能自己搭一个简化版。

思路如下：用一个 HashMap 存储 key 到 Node 的映射，用 LinkedList 维护访问顺序。每次 get 时，如果 key 存在，就把对应节点移动到链表尾部（表示最近使用）；每次 put 时，如果容量满了，就移除链表头部的节点（最久未使用），然后插入新节点到尾部。

LinkedList 在这里面的作用是维护“顺序信息”。数组能做到类似的事，但插入和删除时要搬移元素，而 LinkedList 的 addLast 和 removeFirst 都是 O(1)，配合 HashMap 的 O(1) 定位，整体效率很高。当然 JDK 已经帮你封装好了 LinkedHashMap，实际项目直接用它更省事。但通过手写这个逻辑，你能深刻理解“哈希表提供查找速度，链表维护访问顺序”这个黄金组合的底层协作方式，面试的时候讲清楚这段，比简单地说“我用了 LinkedHashMap”要加分不少。

6.3 业务场景：任务队列与撤销栈的选型思考

在真实的业务代码里，我经常用 LinkedList 做“任务缓冲队列”。比如一个数据导入服务，后台线程从文件里读出一批任务，丢到 LinkedList 里当作 FIFO 队列，再由消费线程通过 poll 不断取出执行。这个场景下两个线程一个写一个读，如果只用最基础的 LinkedList，会面临线程安全问题。正确做法是每次操作都加 synchronized，或者用 Collections.synchronizedList 包装一下，又或者直接换成 ConcurrentLinkedQueue。

这里要单独提醒一下：LinkedList 在多线程环境中不具备线程安全性。它的所有方法都没有同步锁保护，多个线程同时 add 和 remove 时，链表结构可能会在节点引用的更新过程中出现互相覆盖，轻则丢数据，重则链表成环导致死循环。如果你对线程安全有要求，优先考虑 ConcurrentLinkedQueue（无锁并发队列）或 LinkedBlockingQueue（有界阻塞队列）。

撤销操作（undo）也很适合用 LinkedList 来实现。每执行一步操作，就把操作记录 push 到“撤销栈”；需要撤销时 pop 出最近的一条并执行反向操作。同时为了“重做”功能，再准备一个 LinkedList 做“重做栈”，这样来回弹栈效率高，代码也直观。

7. 常见问题与排查技巧：那些年踩过的 LinkedList 的坑

7.1 越用越慢：for 循环 + get(i) 为什么会卡死

这是我在性能排查里见过最高频的问题。有人写了一个 for 循环从头到尾遍历 LinkedList，结果数据量从几万涨到几十万之后，程序延迟从毫秒级变成了秒级。原因我们前面说过：每次 get(i) 都要从头（或者从尾）遍历节点，循环 n 次就是 O(n^2) 的总复杂度。

代码问题出在这儿：

LinkedList<Integer> list = buildBigList(); // 假设有 10 万个元素 int sum = 0; for (int i = 0; i < list.size(); i++) { sum += list.get(i); // 这里每次调用 get(i) 都是 O(i) }

正确做法有两种：一种是老老实实用增强 for 循环，底层走迭代器，每次移动一步，总复杂度 O(n)；另一种是转成数组再遍历，但转数组本身也要 O(n) 的遍历成本，适合需要随机访问的场景。我实测过：10 万条数据的 LinkedList，用迭代器遍历只需几毫秒，用 get(i) 遍历可能需要几百毫秒甚至更多，差距大得非常明显。

7.2 并发修改：ConcurrentModificationException 的触发与规避

“我在遍历的时候往链表里加了一个元素，结果抛 ConcurrentModificationException 了。”这个问题新手几乎都会遇到。本质就是迭代器里的 expectedModCount 和 LinkedList 的 modCount 不一致了。任何通过 list.add()、list.remove()、list.clear() 修改集合结构的操作，都会让 modCount 自增，而迭代器不知道这个变化，于是下一次 next() 检查时直接抛异常。

规避方式有几种：

1. 用迭代器自己的 add()/remove() 方法修改集合，它们会同步更新 expectedModCount。
2. 如果需要大量增删，先收集到一个临时数组或其他集合里，遍历完成后再统一处理。
3. 使用 listIterator()，在遍历过程中用 ListIterator.add() 插入元素，它会把新元素插入到当前位置之前，并且不会破坏遍历进度。

这里有个容易忽略的点：fail-fast 机制只保证“尽量快速失败”，不保证一定发现。在多线程场景下，两个线程同时修改 modCount，有可能恰好都在自增，计数器没变化，那异常就不会触发。所以不要以为“没抛异常就等于安全”，该加同步锁还得加。

7.3 空间浪费：大对象缓存中的内存开销实测

我在一个日志缓冲场景中曾经用 LinkedList 暂存几十万条日志对象，结果 JVM 老年代占用高得吓人。后来一查，LinkedList 的节点对象开销占了接近一半的内存。如果你也是拿 LinkedList 做大量数据暂存，建议多做一步内存估算：节点数量 × 24 字节（Node 对象头 + 两个引用）+ 元素本身的大小。

数据量大时，换用 ArrayDeque、ArrayList 或者自定义的环形数组队列，内存都能下来不少。但另一方面，如果数据量也就几千条、几万条，这种内存差异对服务器来说几乎可以忽略。选型永远是“结合场景”而不是“迷信某个数据结构”，这是我在实战里最大的体会。

7.4 不要用 API 去“猜”性能：remove(Object) vs remove(int)

还有一个隐蔽的坑：remove(Object o) 和 remove(int index) 都叫“remove”，但干的事完全不同。remove(Object o) 是遍历找元素然后删除，时间复杂度 O(n)；remove(int index) 是先定位再断开，也是 O(n)。如果你调用的是 list.remove(i)，而 i 恰好是一个 Integer 对象，Java 会自动把它装箱成 Integer 重载到 remove(Object)，那就会变成按值删除而不是按下标删除。在 LinkedList 上执行 remove(2)，想删下标 2 的元素，结果可能删掉“值等于 2 的元素”。这个坑在代码审查时经常被揪出来，我自己也中过一次招。解决方案是先转成 int 再调用：list.remove((int) 2)，或者用 list.remove(2) 时注意上下文类型。

7.5 null 元素带来的隐患

LinkedList 允许存储 null，但 null 存在于链表中会有两个隐患：一是调用 remove(null) 时会删掉第一个值为 null 的元素，如果你本想删一个具体对象，却因为某个字段没赋值导致匹配到了 null，就会删错；二是迭代遍历时如果没做空值判断，后续逻辑直接调方法就会抛 NullPointerException。空值检查虽然不是 LinkedList 本身的问题，但在业务代码里一定要养成习惯，队列服务中入队前先做参数校验，能省下很多排查时间。

8. 性能对比的补充实验：ArrayList vs LinkedList 到底差多少

很多人对“ArrayList 查询快、LinkedList 增删快”这个说法深信不疑，但实际性能测试往往会给出更复杂的结论。我写了一个简单的 JMH 基准测试思路，在 JVM 默认参数下，分别对这两个集合做了 10 万条数据的头插、尾插、中间插、随机访问测试，结果如下（基于我的测试环境，数据仅供趋势参考）：

解释一下：尾部追加两者都很优秀，ArrayList 在扩容后的 System.arraycopy 效率很高，LinkedList 改引用也不慢，但 ArrayList 略优。头部插入是 LinkedList 的绝对主场，ArrayList 每次都要搬移全部元素，差距巨大。中间插入要看位置定位成本，如果 index 靠近头部或尾部，LinkedList 的定位反而快；但 index 居中时，LinkedList 的定位开销增加，优势会被吃掉。随机访问则完全一边倒，ArrayList 即使访问 100 万次也很快，LinkedList 则几乎不可接受。

所以正确结论是：如果你的操作模式是“只在头部/尾部增删 + 不需要随机访问”，LinkedList 是合理的；如果涉及“按下标访问”“按索引修改”，ArrayList 几乎总是更好。而“中间插入谁更快”其实要看具体场景，数据量小的时候两者差异不明显，数据量大时定位成本会显著拖累 LinkedList。

9. 一些容易被忽略的源码设计细节

源码读得越细，越能发现一些“面试里高频、文档里不写”的小设计：

• LinkedList 的 first 和 last 在链表为空时都为 null，此时调用 getFirst() 或 getLast() 会抛 NoSuchElementException。
• element() 方法等价于 getFirst()，在队列语义中用来获取头部元素但不删除，如果为空会抛异常，而 peek() 则返回 null。这两者手感完全不同。
• descendingIterator() 方法返回了一个从尾到头遍历的迭代器，但其实现是 ListIterator 的 previous 方向的封装。你可以用它在 O(n) 时间内完成反向遍历，而不需要先反转列表。
• clone() 方法是浅拷贝：拷贝出新的 LinkedList，但里面的元素对象引用和原集合指向相同。也就是说克隆后的集合修改了元素对象的内部状态，原集合也会跟着变。
• toArray() 返回的是元素数组，顺序是从 first 到 last。如果数组中元素太大，toArray(T[] a) 在数组容量足够时会直接使用传入的数组，否则会新建数组并反射构造同类型数组。

这些细节你可能平时用不到，但在写工具类、做集合转换、做深浅拷贝决策时会有帮助。多读几遍源码，你会发现它远比想象中“优雅”：每个方法都尽量复用核心的 link/unlink 逻辑，代码结构非常干净。

10. 最后的个人体会：什么时候我可以毫无顾虑地选择 LinkedList

就我个人的使用经验来说，LinkedList 不是“性能猛兽”，而是“方便之王”。在小数据量（比如几千条以内）、需要频繁头尾操作、并且希望同一个对象既支持索引操作又支持队列/栈操作的情况下，LinkedList 是最直接的答案。比如在一个后台管理系统的“最近访问记录”模块里，我用 LinkedList 保存用户最近浏览的 20 条商品 ID，既能快速 addFirst 插入最新记录，也能通过迭代器反向展示，还能顺便实现“超过 20 条就 removeLast 淘汰最旧记录”的逻辑。就这个场景而言，ArrayList 和 ArrayDeque 也能做，但代码都没有 LinkedList 来得直观。

另外一个建议是：源码阅读不要只看结论，建议挑一个周末下午，把 LinkedList 的 add、remove、node、listIterator 几个方法的源码自己走一遍，再对照这篇文章里说的逻辑，亲手 debug 一遍各类操作的前后指针变化。这个动作比背十遍“增删快、查询慢”管用得多。等你真的有一次“哇，原来 node(index) 是从尾部往前找的”这种顿悟时刻，以后面试里再聊集合框架，你就不再是背概念的人，而是真正理解数据结构的人和面试官对话的人了。