LinkedList源码解析：双向链表、栈队列语义与ArrayList选型边界

大部分刚接触 Java 集合框架的同学，都会在LinkedList身上栽过跟头。课本上白纸黑字写着“链表适合频繁增删”，于是写业务代码时但凡遇到插入删除，就习惯性new LinkedList<>()。等到真去跑性能、看源码，才发现这句话的适用范围窄得惊人。今天这篇我会把LinkedList一次讲透：它底层怎么用节点串成链表、为什么天然支持栈和队列语义、和ArrayList竞争时真正的优势边界在哪、遍历时又有哪些能让人血压升高的坑。

整篇文章适合三类人：准备面试、想搞懂集合源码的读者；工作中纠结ArrayList和LinkedList怎么选型的开发者；以及已经踩过LinkedList性能坑、想知道“到底什么时候能用它”的实践派。我尽量不堆术语，每一段都会给原理和代码，读完你再去翻 JDK 源码，应该会顺畅很多。

1. LinkedList的底层真容：节点结构就是这么串起来的

1.1 三个字段和一个私有内部类

打开 IDE 里 JDK 自带的LinkedList.java，你会发现这个类内部并不像ArrayList那样维护一个Object[]数组，而是靠一个叫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指向前一个节点。因为有prev，所以这是一个双向链表，不是教科书里那种只能从头部一路往后的单链表。

类本身还维护了两个引用：first指向头节点，last指向尾节点。很多刚看源码的人会疑惑，既然有head为什么还要tail？因为在双向链表里，没有尾指针的话，尾部追加元素就得从头遍历到末尾，复杂度直接变成 O(n)。有了first和last两个“哨兵”，头尾两端操作都能做到 O(1)。

1.2 尾部加一个元素，底层做了哪几件事

我们平时调用add(E e)，JDK 源码真正执行的是linkLast(E e)，核心逻辑非常短：

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

步骤拆开其实是四步：

1. 记录当前尾节点l；
2. 构造新节点：prev指向l，next为null；
3. 把last更新为新节点；
4. 判断原链表是否为空：为空则first也指向新节点；否则让原尾节点的next指向新节点。

modCount++是给迭代器的快速失败机制用的，后面专门讲。

从这段代码你可以直观看出，LinkedList的尾部插入不需要扩容、不需要搬动已有元素，这是它区别于ArrayList的结构性优势。但代价是每次 add 都要new一个Node对象，这个对象分配开销在极端高频插入场景下不可忽视。

1.3 删除一个节点，unlink 是怎么整理的

删除操作对应unlink(Node<E> x)，虽然方法名叫 unlink，但实际做的是把节点从链条上“摘下来”。以删除中间节点为例：

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

看源码时注意一个细节：源码把x.prev、x.next、x.item都置为null。为什么不直接不管？因为原节点还占用对象引用，如果不切断引用，在 GC 分代回收时可能影响可达性分析，造成这些对象不能及时回收。教科书里不会提这种“断链”细节，但 JDK 作者在内存清理上处理得很细致。

删除某个已持有引用的节点，unlink是 O(1) 的；但如果你只知道下标，想删list.remove(index)，那就得先node(index)遍历找节点，这部分是 O(n)。很多网文只告诉你“链表删除快”，却默认你已经知道目标节点在哪，这个前提在实际编码里很难满足。

2. 与ArrayList的选型之争：内存、缓存和随机访问的账

2.1 内存布局差异，决定了缓存命中率的天壤之别

ArrayList的底层是连续数组，元素在内存里紧挨着。CPU 在读取某一块内存时，会把相邻的内存一起加载进缓存，这就是局部性原理。顺序遍历一个ArrayList，绝大多数数据都能从 L1/L2 缓存里直接命中，速度极快。

LinkedList就不一样了。每个Node都是独立对象，new出来的内存位置分散在堆的各处，next指向的可能是完全不相邻的内存页。顺序遍历时，每到一个新节点基本都会触发一次缓存未命中，被迫从主内存拉数据。尽管理论上遍历都是 O(n)，但实际耗时差距非常明显。

打个比方：ArrayList像一列按顺序停靠的动车，你沿站台走过去就行；LinkedList像散落在城市各处的驿站，你每去一个驿站都要重新导航。同样的路程，时间就是长。

我用一个最简单的实验验证过：对 10 万个字符串元素做一次 foreach 遍历，ArrayList大概需要十几毫秒，LinkedList可能需要几十毫秒甚至上百毫秒。不同机器差异会很大，但趋势永远一致。

2.2 随机访问不是慢，是灾难级的慢

LinkedList.get(i)的实现是node(int index)：

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

JDK 做了一点优化：不是每次从头开始，而是判断目标索引离头部近还是离尾部近，选择较近的方向遍历。即便如此，单次get(i)的平均复杂度仍是 O(n)。

真正的灾难是把它放进 for 循环里：

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

每次循环都从头/尾重新数到目标索引，于是总代价是 1 + 2 + 3 + ... + n，也就是 O(n²)。数据量到 5 万以上，这种写法就能卡到肉眼可见。我见过有人把LinkedList传进一个通用工具方法，方法内部用 get 遍历，结果 10 万条数据跑了 8 秒多。换成ArrayList后，同样的逻辑不到 10 毫秒。

2.3 增删操作也分情况，头尾和中间完全是两码事

如果你只往头部插入，LinkedList.addFirst是 O(1)，因为只动first指针；ArrayList.add(0, x)却是 O(n)，因为所有现有元素都要往后搬。

如果你只往尾部追加，两者都是均摊 O(1)，但ArrayList偶尔扩容会复制数组，而LinkedList每次都要newNode。实测下来，大对象频繁追加时，差距没有想象中那么大。

真正的区别在中间插入。ArrayList插入中间需要搬动后半段元素；LinkedList插入中间需要先node(index)遍历定位。所以：

• 知道目标节点引用，插入/删除：LinkedList完胜；
• 按下标在中间插入/删除：两者各有代价，ArrayList的平移和内存复制反而在不少场景下更快；
• 只在两端操作：LinkedList有天然优势，但若不需要 List 接口，ArrayDeque可能更合适。

这也是网文“LinkedList 适合频繁增删”误导人的地方。这句话成立的前提极其苛刻，至少得是“两端增删”或“持节点引用操作”，而不是“随便一个位置删插”。

3. 把LinkedList当栈用：push/pop背后的源码与边界

3.1 Deque接口提供的栈语义

初学 Java 时，很多人会问：Stack类不是已经实现栈了吗？为什么还要用LinkedList？答案很简单：java.util.Stack继承了Vector，所有方法都带锁，性能一般且设计老旧。现代 Java 推荐用Deque接口来表现栈，而LinkedList恰好实现了Deque。

Deque接口里与栈相关的方法就两组：

• push(E e)：等价于addFirst(e)，把元素压到栈顶；
• pop()：等价于removeFirst()，弹出栈顶元素。

在LinkedList里，addFirst调用的是linkFirst：

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

新增节点直接接在first前面，不需要遍历，O(1)。

pop()调用的则是unlinkFirst，同样只动头指针。整个过程只涉及两三个引用替换，代码量很小，性能非常稳定。

3.2 一个标准的 LIFO 演示

写一段极简代码：

Deque<String> stack = new LinkedList<>(); stack.push("A"); stack.push("B"); stack.push("C"); while (!stack.isEmpty()) { System.out.println(stack.pop()); }

输出必然是C B A。因为每次push都把新元素放到最前面，pop永远拿第一个。

用LinkedList当栈，最大的心理障碍是“它同时也是一个 List”。你可能会下意识用get(0)去看栈顶，这在 LinkedList 上恰好是 O(1)，没问题；但如果你写get(size()-1)想模拟查看栈底，那就是 O(n) 了。栈的操作接口既然叫Deque，就尽量只用push/pop/peek，别把它当 List 瞎用。

3.3 空栈操作的注意点与替代方案

pop()在栈为空时会抛NoSuchElementException。如果你不确定栈里有没有东西，用peek()先看一眼，返回null表示空栈；或者先isEmpty()判断再pop。

另外提醒一句：LinkedList不是线程安全的。多线程环境下用它当栈，必须在外部加锁，或者换成ConcurrentLinkedDeque。这里没有什么魔法可解，push/pop组合本身不具备原子性，多个线程同时操作很可能出现数据错乱。

如果你对栈的性能有要求，且不需要 List 语义，更倾向推荐ArrayDeque而不是LinkedList。ArrayDeque底层是环形数组，连续内存空间，栈操作同样是 O(1)，但缓存命中率更高，内存占用也更小。JDK 文档也公开建议：需要栈或队列时优先考虑ArrayDeque。LinkedList当栈的真正价值在于：你希望这个对象既能当栈用，又能通过 List 下标去访问，或者需要迭代删除某些元素。

4. 把LinkedList当队列用：Queue接口设计的两套方法组

4.1 为什么 Queue 接口有两套语义不同的方法

Deque继承了Queue，Queue接口定义了add/offer/remove/poll/element/peek三对方法。很多初学者背不下来，其实关键是记住：两套方法在失败时的行为不同。

为什么设计两套？因为队列本身有两种形态：无界队列和有界队列。无界队列调用add几乎不会失败，抛异常反而能快速暴露 bug；有界队列容量满了之后，offer返回false比抛异常更温和，让调用方自己决定是等待、重试还是放弃。

LinkedList是无界队列，所以它的offer方法实现非常简单：

public boolean offer(E e) { return add(e); }

内部就是linkLast，永远返回true。poll()则直接走到unlinkFirst，空队列时返回null而非抛异常。

4.2 FIFO 队列的入队与出队路径

把LinkedList当队列用，标准姿势是：尾部进、头部出。

Queue<String> queue = new LinkedList<>(); queue.offer("A"); queue.offer("B"); queue.offer("C"); while (queue.peek() != null) { System.out.println(queue.poll()); // A B C }

offer走linkLast，poll走unlinkFirst，头尾两个指针都在手上，所以都是 O(1)。这也是LinkedList作为队列最干净利落的场景：不需要扩容、不需要数组搬移、不需要考虑数组环形取模。

当然，还是那句老话：如果只需要 FIFO 队列而不管 List 语义，ArrayDeque性能通常更好。LinkedList的优势场景是“同一个对象，既要用队列操作，又要偶尔用 List 的下标去定位元素”，这时候一个对象身兼两职，代码上的便利比那点性能差值更有价值。

4.3 Deque 扩展出的双端能力

除了标准的Queue方法，Deque还提供双端操作组：

• addFirst/addLast
• removeFirst/removeLast
• getFirst/getLast
• pollFirst/pollLast
• peekFirst/peekLast

这套 API 让你可以把它当作“双端队列”使用：既能头部进头部出，也能尾部进尾部出。比如实现一个滑动窗口，需要从尾部加入新元素、从头部淘汰旧元素，LinkedList的addLast+pollFirst组合就非常顺手。

写队列代码最容易踩的坑，是混用 remove 系和 poll 系方法时没有统一失败语义。比如有人习惯写queue.remove()，一旦队列空就抛异常，程序崩溃的地方没有明显上下文。如果你追求稳健，尽量统一用poll/offer/peek，让空队列返回null，把判断逻辑写到业务里。

5. 遍历LinkedList最容易踩的雷：O(n²)陷阱与快速失败

5.1 for-i 随机访问为什么会慢到离谱

很多人拿到一个LinkedList，第一反应就是：

for (int i = 0; i < linkedList.size(); i++) { String item = linkedList.get(i); // 处理 item }

这个写法在ArrayList上没任何问题，但放在LinkedList上就是灾难。原因我在第 2 节已经讲过：每次get(i)都是独立的 O(n) 遍历。整体算下来 O(n²)。数据量小还好，一旦到几十万级，你会明显感觉程序像“冻住”了一样。

修正方式一句话：用增强 for、迭代器或ListIterator，让元素一个接一个顺着 next 指针走。

for (String item : linkedList) { // 处理 item }

增强 for 在编译后会转换成迭代器，底层每次通过next()取当前节点的item，再向后移动一位，整体是 O(n)。

5.2 modCount 与 ConcurrentModificationException

LinkedList里有个字段modCount，专门记录结构修改次数。所谓结构修改，包括增加节点、删除节点、调整大小，但不包括修改已有节点的 item 值。

迭代器在创建时会保存当前的modCount，每次调用next()或hasNext()时检查内部记录是否等于expectedModCount，不等就抛ConcurrentModificationException。

最容易触发这个异常的写法是：遍历过程中直接调用list.remove(element)。

Iterator<String> it = list.iterator(); while (it.hasNext()) { String s = it.next(); if (s.equals("needRemove")) { list.remove(s); // 修改了 modCount，迭代器无法感知，立刻抛异常 } }

正确做法是用迭代器自己的remove()：

Iterator<String> it = list.iterator(); while (it.hasNext()) { String s = it.next(); if (s.equals("needRemove")) { it.remove(); // 内部会把 expectedModCount 同步更新 } }

it.remove()之所以不抛异常，是因为迭代器内部维护了一个expectedModCount，在remove()方法里执行完真正的 unlink 后，会把expectedModCount重新赋值为最新的modCount，两者保持一致。

如果你在遍历时还要做“拿一个元素的同时往队列里加新任务”这种操作，那真正的解决方案是用Deque的poll循环，而不是迭代器：

while (!queue.isEmpty()) { String s = queue.poll(); // 处理过程中可以随时 offer 新任务 }

这种模式在实现 BFS 或任务调度时极其常用，也正是LinkedList作为队列的杀手锏场景。

5.3 反向遍历用 ListIterator，别 reversed 之后再 get

因为LinkedList是双向链表，JDK 提供了一个非常方便的能力：ListIterator可以往反方向走。

ListIterator<String> it = list.listIterator(list.size()); while (it.hasPrevious()) { String s = it.previous(); // 反向处理 }

如果你不知道这个 API，可能会写出先Collections.reverse(list)再遍历的蠢办法。reverse本身也是 O(n) 且会修改原集合顺序；或者更糟，用get(size() - i - 1)去循环。后者回到 O(n²) 老路上了。

顺带一提，listIterator(int index)的定位也是靠node(index)从最近端遍历，初始定位是 O(n)，但定位完成后的反向遍历是 O(n)，整体仍是线性复杂度，可以放心用。

6. 实战取舍：到底什么时候 LinkedList 能真正赢

6.1 真正适合 LinkedList 的场景清单

结合源码和实测，我平常会建议把LinkedList的使用场景严格收窄到以下几类：

1. 需要维持 List 语义又要高频两端操作。比如一个“最近访问列表”，既要能按 List 下标查看历史记录，又要不断在头部插入新记录；或者需要在头部插入的同时从尾部淘汰最旧数据。ArrayList的头部插入是 O(n)，LinkedList的addFirst/removeLast组合才是对的。

2. 删除时你已经持有目标节点。典型场景是结合ListIterator遍历并删除一部分元素，删除过程不依赖下标，LinkedList的迭代器删除是 O(1)，而ArrayList的迭代器删除依然要搬运数组剩余部分。数据量大、删除比例高时，LinkedList可能反超。

3. 需要一个可无限增长的队列且希望同一个引用还能被当作 List 传给旧接口。老系统接口签名写死了List，但内部逻辑需要 FIFO。这种“既要又要”的妥协场景，LinkedList是很好的桥接。

6.2 果断放弃 LinkedList 的时刻

反过来，下面这些情况就不用犹豫，换掉LinkedList更快：

• 读多写少、按下标访问多：直接ArrayList，没有悬念；
• 只要栈/队列，不要 List 功能：用ArrayDeque，内存连续、缓存友好、避免 Node 对象分配；
• 需要线程安全：用ConcurrentLinkedDeque或ConcurrentLinkedQueue，不要在外面裸加锁；
• 任意位置频繁插入，但索引是随机给的：比如list.add(randomIndex, x)。这种场景LinkedList和ArrayList都 O(n)，实测往往ArrayList反而更快，因为数组搬运在底层是System.arraycopy，是高度优化的内存块复制，比逐个new Node+ 遍历指针更快。

很多人以为LinkedList是“万能的增删神器”，实际上 JVM 的数组复制非常快，而指针遍历和对象分配的代价会被很多人低估。我在一个内部模拟项目里测过：10 万条数据的中间位置随机插入 5000 次，ArrayList用时约几十毫秒，LinkedList反而要几百毫秒。所以每次想用LinkedList之前，都先问自己三个问题：我需要随机访问吗？我是按下标定位吗？我真的只需要两端操作吗？

6.3 从头到尾的一句话总结

LinkedList是一个双向链表，它同时实现了List和Deque，所以能当链表看、当栈用、当队列使。它的 O(1) 优势只存在于持有节点引用的删除、以及头尾两端的增删；它的随机访问是 O(n)，中间定位插入删除也逃不开 O(n)。日常默认选ArrayList，纯栈队列场景选ArrayDeque，当你明确需要“List + 双端操作”这个复合能力时，LinkedList才是正解。

我个人在实际项目里的体会是：面试时能准确说出LinkedList的适用边界，比背下“适合频繁增删”这句话有用得多。把源码里linkFirst、unlinkLast、node(index)这几个方法看明白，很多关于它性能的争论都会自动平息。最后再送你一个习惯：看到LinkedList的第一反应，先看它是以List身份出现还是以Deque身份出现，不同身份决定了你该用哪套方法，也决定了代码最终是跑在毫秒级还是秒级。