企业官网建设流程全解析

LinkedList可能是Java集合包里争议最多的类了。网上到处都是“LinkedList插入删除快、随机访问慢”的说法，可真要追问一句：为什么快、为什么慢、快和慢的场景到底是什么？能说清楚的人就很少了。我前阵子把JDK源码里的LinkedList从头到尾逐行读了一遍，边读边在笔记本上画图、做标注，发现不少“常识”其实是一刀切的不准确结论。这篇文章就把我的阅读过程完整复盘一遍：从数据骨架、核心方法实现细节，到迭代器、队列身份、线程安全与选型，尽量把每个“为什么”都拆开讲。如果你也在啃源码但总觉得枯燥、容易忘，这篇也许能帮你建立一套读集合源码的姿势。

1. 读LinkedList源码前，先破除三个流传很广的误解

1.1 “插入删除一定快”——这句话只对了一半

我先说一个很多人都踩过的坑。用LinkedList做中间插入，有人觉得“既然是链表，只要改一下前后指针就能插入，必然是O(1)嘛”。实际上LinkedList的public接口暴露的是int下标，而不是节点引用。你调用list.add(100, element)，它第一步要用node(100)找到第100个节点，这一步本身就是O(n)的遍历；真正链接新节点的那一下linkBefore确实是O(1)。所以中间插入的时间复杂度是O(n)，和ArrayList的System.arraycopy移位没有本质区别，甚至因为node()遍历每次都要走好几个引用，常数还可能更大。

我实际测试过一个场景：往一个10万元素的LinkedList中间循环插入1000次，耗时比同样操作的ArrayList高出不少。原因就是add(index, e)每次都从链表的一端开始走一半距离，1000次就是大量次数的引用跳转，而ArrayList哪怕每次搬移五万个元素，System.arraycopy是底层优化过的内存拷贝，速度极其快。所以以后再看到“LinkedList插入快”，一定先问一句：插哪？如果是从头或尾插入，那确实O(1)；如果是中间插入，别指望它比ArrayList快。

删除也是一样。list.remove(index)要先node(index)定位，同样O(n)。只有removeFirst和removeLast这种明确从两端删除的操作才是O(1)。看清这一点，很多关于LinkedList“性能好”的讨论都可以冷静下来。

1.2 “随机访问慢”——快慢要看从哪儿访问

LinkedList的随机访问慢，严格说是list.get(index)慢，因为每一次get都要从最近的端点往中间找。JDK源码在node(int index)里做了一个方向优化：如果index小于size >> 1，就从first往后走；否则从last往前走。也就是说，访问下标0和下标size-1都是O(1)，访问中间位置大约要n/2步。这里的size >> 1不是二分查找，它只是选了离哪个端点更近，并没有把复杂度从O(n)降下来，但常数上确实省了一半。

所以“随机访问慢”这个结论要修正一下：准确说法是“按下标访问慢，但访问首尾极快”。你在实际项目里，如果确定只操作队列的两端，LinkedList就没什么访问性能问题。很多技术文章把LinkedList整个打成“随机访问慢”的标签，其实掩盖了它有getFirst、getLast、peekFirst、peekLast这些O(1)入口的事实。

1.3 “LinkedList更省内存”——其实恰恰相反

这个误解我以前也有。很多人觉得链表是“需要多少就分配多少”，不像ArrayList要预留容量，所以内存更省。但LinkedList每一个元素都包装在一个Node对象里，一个Node至少包含三个字段：item、next、prev。在64位JVM默认启用压缩指针时，一个Node对象有对象头，再加上三个引用字段，算上对齐，每个Node轻松超过24字节。而ArrayList是Object[]连续数组，引用数组本身按元素数量精确增长，对象头和数组头开销是一次性的。

我算过一笔账：存10万个元素，ArrayList的Object[]大约几十万字节；LinkedList除了业务对象，还要额外再分配10万个Node对象，每个Node至少多占用20多个字节。这一下就是若干兆级别的额外开销。在小内存场景，这个问题会被放大得很明显。所以“链表省内存”只在一个特殊场景下略微成立：你反复在中间插入删除，导致ArrayList需要频繁扩容和搬移时的瞬时内存峰值可能更高。但从稳态内存占用看，ArrayList几乎总是更省。

2. 从三个字段和一个内部类，看懂LinkedList的数据骨架

2.1 Node内部类长什么样

LinkedList不是直接继承AbstractList的随机访问结构，而是自己定义了一个静态内部类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; } }

这个类极简：数据本身、前驱引用、后继引用、一个三参构造器。三参构造器把前驱、元素、后继一次性接好，方便后面各种link方法直接new出一个已经串进链表骨架的节点。注意next和prev都是默认包可见的，LinkedList在内部直接访问，不需要getter/setter，这也是JDK内部代码的一贯风格：内部实现追求效率，不为封装性牺牲简洁性。

2.2 first、last、size三个字段

LinkedList一共只有三个实例字段：

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

size记录元素个数；first指向头节点；last指向尾节点。有趣的是，这三个字段全部用transient修饰，说明它们不参与默认Java序列化，LinkedList自己实现了writeObject和readObject来逐节点序列化。为什么要自己做？因为一个Node对象持有了前后两个引用，如果直接序列化对象图，会顺着next一直递归，序列化出来的东西会包含大量重复的引用关系，而且不同JDK版本内部结构一旦调整，序列化数据也没法兼容。自己写序列化，只把item按顺序写进去，读回来时一个个linkLast，既干净又稳定。

维护first和last两个端点带来的直接好处是：addLast不用遍历链表找尾，addFirst也不用额外记一个哨兵节点。很多教材里写链表会说“带头节点的单链表”，但JDK的LinkedList没有哨兵head，而是用null代表空链表。判断空链表只看first == null，或者说size == 0。这里有一个贯穿全部源码的实现细节值得记住：链表为空时，first和last都是null；链表不为空时，first.prev一定是null，last.next也一定是null。这个不变量被所有增删方法维护，源码里所有边界判断都在围绕它展开。

2.3 为什么必须是双向链表

很多人问：LinkedList为什么不做成单链表，那样Node还能省一个引用？答案分两方面。

第一，Deque接口要求。LinkedList实现了Deque，也就必须支持从尾部向前遍历、从尾部删除节点。如果是单链表，想做removeLast，必须从头走到尾找到倒数第二个节点，复杂度O(n)，完全违背双端队列的设计意图。双向链表让两端操作都是O(1)。

第二，删除任意节点时，双向链表的unlink操作能直接拿到待删节点的prev和next，不需要像单链表那样额外维护一个前驱指针。虽然在按index删除的场景里，node(index)已经帮你走到了位置，但如果代码持有某个Node引用（比如迭代器内部），双向删除的优势就体现出来了。

2.4 字段设计带来的操作复杂度一览

读到这里，其实就可以把LinkedList的能力边界列出来了：

• 头插、头删、尾插、尾删：O(1)
• 按下标插入、删除、访问：O(n)
• 按值查找：O(n)
• 迭代遍历：O(n)，但每次next只是走一个引用跳转

这张表比“插入删除快”的说法精确太多，也是后面选型判断的依据。读源码时先建立这张复杂度表，后面看方法实现就不会晕。

3. 核心方法源码逐段拆解：add、remove、get的完整链路

3.1 添加方法：linkFirst、linkLast与linkBefore

所有添加操作最后的落点，都是三个私有link方法。先看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++; }

linkLast的关键是先把旧last存到局部变量l里，然后创建新节点：新节点的prev指向旧尾，next为null。接着把last更新为新节点。如果l是null，说明链表本来是空的，这时first也要指向新节点，链表从空变成单节点；否则把旧尾的next指向新节点。最后size自增，modCount自增。modCount是AbstractList里定义的结构化修改计数器，后面讲迭代器的时候会再提到。

linkFirst完全对称，只不过操作的是first：

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

linkBefore用于在指定节点succ之前插入新节点：

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的前驱和succ本身；然后更新succ.prev；如果pred为空，说明succ原本是头节点，新节点要顶替first；否则把pred.next接到新节点。三个link方法都完美维护了“first.prev必为null、last.next必为null”的不变量。阅读源码时，我建议把这三个方法并列起来看，你会发现它们的结构几乎一样：先读出边界节点，再创建新节点，再分空表和非空表两种情况修补引用。

3.2 删除方法：unlink的指针清理暗藏GC心思

删除的统一入口是unlink(Node 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; }

这里很多人会忽略的细节是：unlink把被删节点的prev、next、item全部置为null。从纯功能角度看，引用断了链表已经不再包含这个节点，即使不清null也能正常工作。为什么要清？核心原因是帮助垃圾回收。如果某个业务对象被从list里remove，但list内部还残留着对它的引用（比如x.item还指着它），那么这个对象就不会被GC回收，等于变相内存泄漏。JDK开发者在这个细节上相当谨慎，凡是移出容器的元素，都会把容器内部的强引用断开。

另一个值得体会的点是unlink的双分支写法：先处理prev分支，再处理next分支。当头尾边界重叠时（比如链表只有一个节点，prev和next都是null），第一个if把first更新为next，也就是null；第二个if把last更新为prev，也是null，最终first和last双null，链表回到空状态。这个写法不要试图合并成一个if，拆开写反而更清楚，每种边界情况都被显式照顾到了。

3.3 访问方法：node(int index)里的size >> 1

按下标访问的核心是node方法：

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

size >> 1就是size除以2取整。这个判断决定了从头走还是从尾走。它的复杂度仍然是O(n)，但平均访问路径从n缩短到n/2。比如size是100万，访问index 500000时，不管从哪头走都要50万步；但如果经常访问靠前或靠后的数据，这个优化能明显降耗时。node方法被add(index, e)、remove(index)、get(index)、set(index, e)这些所有按下标操作的方法共用，所以它是LinkedList的“心脏”。

看完node方法，就能彻底理解为什么for循环用get(i)遍历LinkedList会出问题：每次get(i)都会执行一次node(i)，从链表头部重新走i步。于是for循环的总步数就是0+1+2+...+(n-1)，约等于n²/2。10万元素就是约50亿次引用跳转，不超时才怪。

3.4 查找与修改：indexOf与set

indexOf是从头顺序比较，本身没有什么花活：

public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }

注意它对null元素单独做了一次循环，避免在循环里判断“o == null ? x.item == null : o.equals(x.item)”这种每轮都要做的三目判断。这种把null查找和正常查找拆成两个循环的做法，在JDK源码里反复出现，比如ArrayList的indexOf也是这么写的。为什么这么麻烦？因为内部循环短一点，JIT编译后少一条分支，高频场景下能省不少指令。读源码时看到这种重复代码，不要觉得啰嗦，这是性能抠到细节的表现。

set(index, element)方法有一个容易被人忽略的副作用：它会返回旧值。实现是先node(index)找到目标节点，再取oldValue，把item换成新值，返回。有人把它当摆设，其实如果业务上需要把旧值拿出来做对比或记录，set返回旧值就省了额外一次get。

3.5 modCount：一个被大多数人忽略的计数器

前面几个方法里都出现了一个modCount++。modCount在AbstractList里定义，记录list结构性修改的次数。结构修改指改变size的操作，比如add、remove、clear；而set只替换item，不算结构修改，不会增加modCount。迭代器创建时会记录当时的modCount为expectedModCount，每次迭代前会检查两者是否一致，不一致就抛ConcurrentModificationException。这个机制叫fail-fast，它不是为了给多线程加锁用的并发安全机制，而是在迭代过程中发现列表被结构性地改了以后，尽快失败，避免脏数据继续跑。

读完这些核心方法，建议自己脑内演算一遍：一个只有3个节点的链表，add(1, x)从空到1个、到两个、再到三个，把边界全部走一遍。源码这东西，光看不过瘾，动手演算一次，记忆会深得多。

提示：读源码时看到modCount++不要直接跳过，它是理解fail-fast和迭代器行为的关键。以后自己写容器类，也应该在结构修改的位置维护一个类似的计数器。

4. 迭代器与遍历效率：为什么LinkedList的for循环成了性能陷阱

4.1 ListItr的实现骨架

LinkedList的迭代器是一个私有内部类ListItr，实现了ListIterator。它维护三个指针：

private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ... }

lastReturned是上一次返回的节点，next是下一次即将返回的节点，nextIndex是next对应的逻辑下标。迭代器的next()做的操作是：先checkForComodification()检查modCount，然后取出next的item，把next向后挪一个节点（如果next为空，说明到底了），再更新lastReturned。整个过程没有node(int index)的下标遍历，所以迭代器遍历LinkedList的总代价是O(n)，这才是遍历LinkedList正确的方式。

ListIterator还提供了previous、add、set、remove这些双向迭代和就地修改能力。特别是previous，它依赖prev指针，这是ArrayList的迭代器做不到的。如果你需要一个前后来回都能走的list遍历器，LinkedList的ListItr是明确优势。

4.2 两种遍历方式的复杂度对比

把两种遍历方式并排看就很明显：

• for (int i = 0; i < list.size(); i++) list.get(i)：O(n²)
• for (E e : list)：内部走iterator，O(n)

为什么很多老代码还是写第一种？因为对ArrayList来说，get(i)是O(1)，for循环完全没问题；用户把ArrayList的遍历习惯无脑带到LinkedList上，就触发了性能陷阱。这其实是一个典型的“抽象泄漏”：面向接口编程时，如果你只声明List，却不知道实现类的遍历成本差异，很容易写出在一种实现上飞快、在另一种实现上慢到无法接受的代码。

如果实在要从for i风格改成iterator风格，又不想大改代码，最简单的做法是把LinkedList先toArray，然后遍历数组。代价是一次O(n)的拷贝，换来后续O(n)的遍历。某些场景下这个改法很实用，尤其适合那种“逻辑不变、底层结构换了”的存量代码。

4.3 实测数据：同样的测试代码，差距有多大

我自己用JMH简单测过一轮，环境是JDK 8、10万条Integer数据。结果大致是这样：

这个数据的绝对数值取决于机器，不值得刻在脑子里；但“数量级差异”是稳定的。LinkedList用for i方式遍历10万个元素，基本要跑好几秒，而用iterator遍历只要个位数毫秒。原因就是前面说的n²次引用跳转。顺带一提，在纯迭代场景下，LinkedList并不比ArrayList明显慢，很多时候还差不多，因为ArrayList需要经过边界检查访问数组元素，LinkedList只是解一个引用，两者常数都在纳秒级。

5. Deque身份：LinkedList的另一副面孔

5.1 一条声明带来两种能力

LinkedList的类声明是：

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

很多教学只把它当List用，忽略了它同时实现了Deque接口。这意味着LinkedList天生就是一个双端队列：既可以从头部插，也可以从尾部插，既可以pop，也可以push，完全可以当栈和队列用。Deque接口里那些offerFirst、offerLast、pollFirst、pollLast、push、pop、peek等一大堆方法，在LinkedList里都有一一对应的实现。实现逻辑并不复杂：offerFirst封装linkFirst，pollFirst封装unlinkFirst，peekFirst就是读出first.item。可以说，Deque的方法本质上是把前面拆解过的link/unlink操作换了一个公开的壳。

5.2 队列操作背后的指针操作

以pollFirst为例：

public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }

unlinkFirst和unlink的差别只在：头节点的prev一定是null，所以不需要处理前驱分支，只需要处理后继分支：

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

你会发现它同样把被删节点的item和next置为null帮助GC，同样维护“first.prev必为null”。顺着这个思路去读removeFirst、removeLast、offerLast等等，会发现彼此只是排列组合。所以读LinkedList源码，不需要每个方法都背，抓住link/unlink这两组私有方法，其余全是它们的调度。

5.3 和ArrayDeque对比，LinkedList输在哪里

既然能当栈和队列，很多人就产生了选择困难：既然LinkedList都能干，为什么还要用ArrayDeque？答案是：ArrayDeque在几乎所有的双端操作上，性能都优于LinkedList，内存也更省。

ArrayDeque内部是一个可变长的Object[]环形数组，它没有Node对象，没有每条元素的额外引用，缓存局部性极好。如果你只是需要一个栈或队列，不需要按下标访问、不需要中间插入，ArrayDeque是最佳选择。LinkedList的Deque身份更多是一个“顺带实现”：因为双向链表天然支持双端操作，JDK作者顺手实现了Deque接口，让它在需要List和Deque双重语义的时候能派上用场。但这种“什么都干”的类，往往在任何一个维度都不是最优的。用一句话说：列表操作优先ArrayList，纯队列栈优先ArrayDeque，LinkedList只在“需要频繁从两端操作且偶尔中间插入删除”的时候才有存在感。

6. 线程安全、内存占用与真实选型

6.1 线程不安全的两个层次

LinkedList和ArrayList一样，完全不是线程安全的。它的所有方法都没有同步保护。更隐蔽的是，即便你在外部加了锁，只要迭代期间有其他线程做了结构性修改，fail-fast机制就会抛异常。这里要说清楚两个层次：

• 普通读写并发问题：两个线程同时add，可能覆盖彼此、size错乱。
• 迭代期间并发修改：抛ConcurrentModificationException，这不是数据损坏，而是快速失败保护。
• 如果确实需要线程安全，不要用Vector这种老古董，而是在使用层加锁，或者干脆换ConcurrentLinkedDeque、ConcurrentLinkedQueue这些并发容器，它们才是为并发设计的。

有人觉得“既然方法不是synchronized，我把它包在Collections.synchronizedList里不就行了？”可以，但那样整个list的操作都被粗粒度锁串行化，头部插入和尾部插入这种互不相关的操作也会互相阻塞。如果并发量高，还是建议选专业的并发容器。这个选型逻辑和ArrayList面对的取舍一模一样，并不是LinkedList独有的问题。

6.2 内存计算：一个Node到底多重

我前面说过LinkedList更费内存，这里精确算一下。假设JVM开启了压缩指针（64位默认开启），一个Node对象有：

• 对象头：约12字节
• item引用：4字节
• next引用：4字节
• prev引用：4字节
• 合计24字节，对齐后还是24字节

这是Node本身的额外开销，还不算item指向的业务对象。10万个节点就是约240万字节。而ArrayList存10万个元素，Object[]数组的开销大概是：数组对象头加对齐，再加上10万乘4字节的引用，总量约40万字节。这个差距接近6倍。这里还没有算ArrayList扩容时的余量，但整体格局已经很明显。可以说在中等规模数据下，LinkedList的内存劣势是实打实的，不是网络上轻描淡写的“略有差异”。

6.3 我现在的选型建议

几年的实际项目做下来，我的选择非常固定：

• 默认用ArrayList。数据连续、缓存友好、按下标访问O(1)、遍历快、内存省。
• 只有当业务明确需要“高频从首尾增删，且几乎不做按下标访问”时，才考虑LinkedList。
• 如果只是实现栈或队列，直接上ArrayDeque，不要用LinkedList和Stack。
• 如果要存大量元素且经常中间插入删除，先重新审视一下业务数据结构，很多时候可以用两个ArrayList拼，或用HashMap做索引，整体复杂度能降一大截。

举一个我印象很深的例子：某个模拟项目里，有一段代码用LinkedList维护一个“最近访问记录”，每来一个请求就把旧记录删掉、新记录加到队尾。这个场景表面看很适合链表，但数据量一上来，contains、indexOf这些O(n)操作不断触发，整个模块成了瓶颈。后来我把记录列表改成HashMap加一个按时间戳排序的数组结构，中间删除改成逻辑删除，性能瞬间就上来了。所以选型不能只看“增删快”这个单一指标，要看全量操作序列的组合成本。

7. 这次阅读源码，我总结的几点实用方法

如果你打算把LinkedList或其他集合源码啃完，我可以分享几个让我少走弯路的方法。

第一，从字段开始读。任何类的源码，先看它的实例字段，再想“这些字段能支撑哪些操作是O(1)”。比如看到first、last，就能推断出首尾操作快；看到size，就明白所有方法都会维护它。字段决定了数据结构，数据结构决定了复杂度，复杂度决定了选型，这是一条完整的推理链。

第二，抓住私有方法，忽略公有外壳。LinkedList真正干活的私有方法就那么几个：linkFirst、linkLast、linkBefore、unlink、unlinkFirst、unlinkLast、node。公开方法只是参数校验加调用私有方法。你把这些私有方法在纸上画一遍，比读两百行公开方法都管用。

第三，画出删除和插入的指针变化图。拿一个只有三个节点的链表，手动模拟add(1, x)和remove(1)，每一步都更新first、last、prev、next。画到第三遍，边界条件就再也不会忘了。我自己的笔记里到现在还留着类似这样的手绘图，每次看都很有收获。

第四，对比着读。把LinkedList和ArrayList对应的add、remove、get放在一起看，你才会明白为什么接口一样但复杂度完全不同；把LinkedList和ArrayDeque放在一起看，你才会知道为什么队列场景要选数组。对比是读源码最有效的方式，比单独顺着方法列表走一遍强得多。

最后再提醒一句：源码里的注释和代码风格也值得学。比如unlink这个命名虽然短，但它准确表达了类的内部“解除节点连接”的统一操作，读代码的人不会对意图产生歧义。我写业务代码时，也开始刻意学习这种“私有方法承担单一职责、公开方法做薄壳”的组织方式，代码的可读性确实好了不少。