企业官网建设流程全解析

LinkedList这个类，几乎是每个Java开发者必读的源码之一。不管你是在准备面试还是想提升内功，它都是绕不开的“八股文”主角，但说实话，很多人对它的理解停留在“双向链表、插入删除快、查询慢”这个层面。我当年也一样，直到真正把源码一行行抠过之后，才发现里面的设计细节远比背概念要有意思得多。

这篇文章我就从源码角度把LinkedList彻底讲透，包括它的数据结构、核心方法实现、迭代器原理、性能表现，还有那些面试官常挖的坑。你可以把它当作一篇源码导读，也可以当作面试复习提纲。不管你是刚开始学Java基础，还是已经在准备Java面试，我相信读完都会对LinkedList有一个更立体的认识。注意，案例基于JDK 8版本的源码，也是应用最广泛的版本。

1. LinkedList整体架构与设计思路

1.1 从类定义看LinkedList的多重身份

先看一下LinkedList的类声明，这是一切的起点：

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

这个声明信息量非常大。它继承了AbstractSequentialList，说明这是个“顺序访问”的列表，和ArrayList那种随机访问的AbstractList是有本质区别的。更关键的是它实现了Deque接口，这意味着LinkedList不仅仅是个List，它还是一个双端队列。

这一点在面试里经常被问到：LinkedList和ArrayList的第一个区别是什么？很多人的答案是“一个基于数组，一个基于链表”，这没错，但不够完整。LinkedList实现的是Deque，所以它天生支持在头部和尾部都进行高效的插入和删除操作，而ArrayList只能通过System.arraycopy这种挪移方式来处理头部操作。

这种多重身份决定了LinkedList的很多设计选择。比如它既有get(int index)这种List的方法，又有addFirst(E e)、removeLast()这种Deque的方法，甚至还专门实现了removeFirstOccurrence(Object o)和removeLastOccurrence(Object o)这种只在Deque接口里定义的方法。所以读源码的时候，看到这类方法不要觉得突兀，那是它在履行Deque职责。

1.2 为什么是双向链表而不是单向

本质原因用一张图讲清楚。如果LinkedList是单向链表，每个节点只存指向下一个节点的指针，那它确实能实现add(int index, E element)这种方法，但代价是：在尾部插入元素时，每次都要从头遍历到最后一个节点，时间复杂度是O(n)。这样一来，尾插法就退化成了灾难。

双向链表则不同，每个节点额外保存了指向它前一个节点的指针。LinkedList内部维护了first和last两个引用，分别指向链表的头节点和尾节点。这样一来，头插和尾插都是O(1)操作，完全不需要遍历。

这个设计决策直接回应了Deque接口的需求。要知道Deque作为“double-ended queue”，最基本的功能就是两端都能高效出入。如果LinkedList不是双向链表，它是没有资格实现Deque的。所以源码选择双向链表不是拍脑袋，而是由接口契约倒推出来的必然。

顺带说一句，看懂了这个设计，面试题“为什么LinkedList比ArrayList适合在头部插入”就能答得更加透彻。ArrayList头部插入需要把原有数组全部后移，复杂度O(n)；LinkedList头部插入就是创建一个节点然后调整两个指针，复杂度O(1)。数据量越大差距越明显。

1.3 LinkedList适合什么场景

单纯从数据结构角度看，LinkedList适合的场景集中在“频繁在两端或已知位置插入删除”且“几乎不随机访问”的情况。比如实现队列、栈、双端缓存时，LinkedList天然就是一个非常合适的底层数据结构，因为它们只用得到链表的头尾操作，而这正是链表的强项。

但这里我必须泼一盆冷水：在实际的业务开发中，LinkedList的出场机会真的不多。很多博客吹的“频繁中间插入删除用LinkedList”，在工程上其实站不住脚，原因后面我会专门用性能数据来说明。现代操作系统和JVM对数组的缓存友好性是链表完全没法比的，ArrayList的批量插入（通过ensureCapacity + System.arraycopy）很多时候反而比LinkedList在这种场景下更快。

我自己在项目里见到LinkedList最多的地方反而是两个：一是作为消息队列的本地缓冲，因为消息的消费总是从尾部追加、从头部取出；二是在某些外部SDK的源码里，需要一个能当栈又能当队列的容器时顺手用它。搞清楚这个现实，你就能理解为什么很多源码阅读资料都建议“先读ArrayList，再读LinkedList”了。ArrayList是日常主力，LinkedList则是理解数据结构和Deque接口的最佳教材。

2. 核心字段与内部节点结构

2.1 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指向前一个节点。然后是构造函数的参数顺序，(prev, element, next)，前驱在前，后继在后，和数据字段的声明顺序是反的。很多人在手写链表代码时被这个顺序坑过，所以我特意提一嘴。

其次是这个构造函数没有做任何参数校验和赋值以外的操作，朴实得让人有点意外。这是JDK源码的一贯风格：内部类只负责表达最基础的数据结构，逻辑判断全部留在外层方法里。这么做的好处是内聚性高，Node本身只有“我是谁、我指向谁”的信息，任何对它字段的修改都必须通过LinkedList的方法来进行，从而保证链表结构的一致性。

还有一点值得注意，Node在源码设计中打上了static关键字。这意味着它是一个静态内部类，不持有外部LinkedList的引用，因此不会造成内存泄漏，也不会在序列化时产生额外的隐式引用字段。这种细节在写业务代码时无所谓，但在框架设计中是必修课。

2.2 三个核心成员变量

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

核心变量不多，一共三个：size记录节点数量，first指向头节点，last指向尾节点。它们都被声明为transient，意味着在序列化时这三个字段不会被默认机制处理。LinkedList自己重写了writeObject和readObject方法，按顺序逐个序列化每个节点上的元素。这样做的好处是避免了将整个链表拓扑结构（包括前后指针）序列化，从而节省存储空间，也避免了因为节点间互相引用而可能导致的递归序列化问题。

一个很容易被忽略但面试中偶有出现的点：first和last并没有像数组那样的默认值。对LinkedList来说，空链表的first和last都是null，size为0。这也意味着所有的空链表判断都依赖这三者的一致性，而不是单一字段。

当链表为空时，first和last同时为null；当链表只有一个节点时，first和last指向同一个节点，且该节点的next和prev都是null；当链表有多个节点时，first.prev和last.next恒为null。这三个不变式是LinkedList所有方法正确性的基础，理解它们对后续阅读非常有帮助。

2.3 构造函数：看似简单实则暗藏玄机

public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

无参构造函数啥也没干，这是链表的一大特色：节点不需要预分配空间。所以LinkedList构造之后内存开销极小，不像ArrayList默认会分配一个容量为10的底层数组。这个差异在小规模场景下不明显，但如果在高水位内存环境下，哪怕只创建了一个空集合容器，ArrayList也多占了40字节的数组头，LinkedList则基本不占额外空间。

集合构造函数就更简单了，直接调用this()然后交给addAll(Collection<? extends E> c)。这里暗含一个细节：addAll的默认参数是size（尾部追加），所以new LinkedList<>(list)等价于把传入集合的迭代顺序追加到新链表尾部，不会打乱顺序。要注意的是，这里调用的是addAll(c)而非addAll(size, c)，后者才是真正意义上的“指定位置批量插入”，前面那个只是便捷入口，最终还是调用了addAll(size, c)。

我读源码时经常强调一个习惯：看构造函数不要只看它怎么赋值，要关注它没做什么。LinkedList没有容量参数、没有预检查，因为它压根没有容量概念，这对理解后面的扩容逻辑和性能特征很有帮助。

2.4 模版方法 addAll 的细节

这里我看一段重要的内部方法。

public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }

我来拆解一下这个方法的思路。先调用checkPositionIndex(index)校验插入位置合法性，然后把传入的Collection转成Object数组，这一步很关键，它保证了后续的遍历可以基于数组而不是Iterator，效率更高，也避免了在遍历过程中集合被并发修改导致的问题。

接下来是核心的节点操作。先用succ和pred分别记录“插入位置原本的节点”和“它的前驱”。如果插入位置就是尾部，则succ为null，pred是原来的last；如果在链表中间，则通过node(index)找到那个位置的节点，pred就是它的前驱。选定位置之后，循环创建新节点，并不断更新pred指针。最后分两种情况收尾：如果succ为null，说明插入到了尾部，直接更新last；否则把最后一个新节点和succ串起来。

这个方法的精妙之处在于，它不是逐个调用add(index)来实现批量插入的。那样每次都要执行一次node(index)查找，复杂度会变成O(n²)。addAll一次性完成所有链接工作，把总复杂度控制在线性级别。从这种设计能看出，JDK对批量操作是有明确优化意识的，这也是源码阅读的价值所在——能学到普通编程书里不会讲到的工程优化思维。

3. 核心方法源码深度解析

3.1 add(E e)：尾插法的详细执行流程

LinkedList的add(E e)方法直接调用了私有方法linkLast(E e)：

public boolean add(E e) { linkLast(e); return true; } 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保存当前的尾节点，防止后续操作中last被修改但旧尾节点丢失；第二步，创建新节点，它的prev指向旧的尾节点，next为null；第三步，更新last为新节点，这个操作必须先于判断，否则判断条件会失效；第四步，根据旧的尾节点是否为空，决定是把新节点设置为first（链表为空的情况），还是把旧尾节点的next指向新节点。

特别注意modCount++，这是一个容易被忽视但极其重要的细节。modCount是父类AbstractList中定义的计数器，记录结构被修改的次数。添加、删除、清空、排序等操作都会让它自增，而迭代器在迭代过程中会校验这个值，一旦发现不一致就抛ConcurrentModificationException。这就是fail-fast机制的底层来源。

3.2 add(int index, E element)：从中间插入的完整链路

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

这里的逻辑很有代表性。首先是checkPositionIndex(index)，它内部调用isPositionIndex(index)，判断条件是index >= 0 && index <= size。注意这里是允许index == size的，因为添加操作可以在尾部追加元素。接着分两种情况：如果插入位置正好是尾部，走linkLast；否则调用node(index)找到目标节点，再交给linkBefore执行前插。

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的前驱节点pred。创建新节点，它的prev指向pred，next指向succ。然后把succ的prev指向新节点。接着判断pred是否为null：如果为null，说明succ原来是第一个节点，那么新节点就成为了新的first；否则把pred的next指向新节点。这里的操作顺序是先改新节点的引用，再改succ的引用，最后改pred的引用，一步都没省。如果先改了pred.next，导致pred的next不再是succ，后面用new Node<>(pred, e, succ)的succ引用就会错，所以源码中的顺序是经过深思熟虑的。

理解这段代码后，你会发现“链表插入快”的说法其实是需要前提的：前提是你已经知道了插入位置的前驱节点。如果像add(index, e)这样要从头遍历定位index，那这个“快”就荡然无存了。这正好解释了为什么很多人说“LinkedList中间插入不一定有ArrayList快”——虽然插入本身是O(1)，但定位插入点需要O(n)的时间。

3.3 get(int index)与二分查找优化

public E get(int index) { checkElementIndex(index); return node(index).item; } 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; } }

node(int index)是整个LinkedList里最会“取巧”的方法，也是面试中容易考细节的地方。它先判断index是在链表的前半段还是后半段，size >> 1等价于size / 2。如果在前半段，就从头节点开始往next方向遍历；如果在后半段，就从尾节点开始往prev方向遍历。这个优化让平均遍历长度从n变成了n/2，虽然时间复杂度依然是O(n)，但常数项减半了。

这个优化在数据量小的时候感知不明显，但如果链表有几万甚至几十万个节点，访问中间位置的元素时就能明显感觉到相比纯从头遍历快了一半。我看到很多源码解读文章对node方法一带而过，但我建议你认真思考一下：为什么不直接size/2而要用位运算size >> 1？不讨论性能，至少在JDK 8的源码里，位运算是这种无符号右移除以2的惯用写法，它在处理负数时和Math.floor(size / 2)有细微差别，但size是链表长度，永远非负，两种写法等价。从这里也能看出JDK源码作者在细节上的把控。

不过必须强调，get(int index)虽然在设计时尽量优化了，但它毕竟还是要遍历链表。这也是为什么“LinkedList查询慢”这个结论永远成立的最直接原因。

3.4 remove(int index)与remove(Object o)的异同

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }

remove(int index)的逻辑比较简单：先校验index是否在[0, size)范围内，然后通过node(index)找到要删除的节点，调用unlink(x)进行物理删除。注意index=size这个位置是删除不了的，因为越界了，这和add方法里的checkPositionIndex是有区别的。

remove(Object o)则有几个坑要注意。第一个坑是它只会删除第一次出现的元素，也就是最靠近head的匹配项，删除完成就立即返回true，后续重复元素不会被删。第二个坑是它对null值专门做了分支处理，因为null.equals会抛NullPointerException，所以必须先用x.item == null判断。第三个坑是o.equals(x.item)而不是x.item.equals(o)，这个顺序是有讲究的，它保证了被删除元素自己重写的equals方法（如果有）不会影响比较结果。

真正的删除动作发生在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; }

这个方法值得逐行背诵。它先把被删节点的数据、前驱、后继都保存到局部变量里。如果prev为null，说明被删的节点是头节点，那么新的头节点应该是next；否则把前驱的next指向后继。如果next为null，说明被删的节点是尾节点，新的尾节点应该是prev；否则把后继的prev指向前驱。最后一步，把被删节点的x.prev、x.next、x.item全部置为null，这一步的目的是断开引用，让GC可以及时回收被删节点的对象。

请注意这里的三个= null赋值，很多白话讲解都会忽略，但在内存敏感场景下，如果被删节点是个大对象结构，不及时断开引用会导致它比预期的存活时间更长，产生内存滞留。这种“用完之后主动置空引用”的习惯，也是看源码最大的收获之一。

3.5 队列与双端操作：peek/poll/push 是如何实现的

LinkedList实现了Deque接口，自然需要实现队列相关的所有方法。这里我挑几个典型的来看：

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

peek和poll的语义差异是：peek只看不删，队列为空时返回null；poll取出并删除，同样空队列返回null。底层实现都是先判断头节点是否为空，为空就返回null，不为空则执行相应操作。

push(E e)方法就是头插法：

public void push(E e) { addFirst(e); }

而addFirst(e)的核心是linkFirst(e)，其逻辑和linkLast完全对称：先保存旧的first，创建新节点让它的next指向旧头节点，更新first，最后把旧头的prev指向新节点。从这个角度看，LinkedList作为栈来用是完全合法的，因为它实现了Deque接口，而Deque正是Java官方推荐的栈实现方案。

4. 迭代器原理与遍历陷阱

4.1 为什么不能用for循环get来遍历LinkedList

这是一个经典到不能再经典的“坑”，我在各种Java基础课里讲过不下几十次。如果你用普通的for循环加get(i)来遍历LinkedList：

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

表面上看没什么问题，但性能是灾难级的。原因在于每次get(i)都要调用node(i)方法，它从first或last出发，沿着链表逐个节点往后走，这本身就是O(i)的复杂度。那整个循环的复杂度就是O(0+1+2+...+n) = O(n²)。

而当数据量到了十万、百万级别，这种二次方复杂度带来的卡顿是肉眼可见的。我专门做过一次测试，在10万条数据的情况下，for+get遍历LinkedList需要几百毫秒，而用迭代器或者增强for循环只需要几毫秒，差距是两个数量级。

根本原因在于：迭代器内部维护了一个next指针，每次next()操作只需要返回当前节点并后移一位，复杂度是O(1)，整个遍历的复杂度是O(n)。这就是数据结构和算法设计在工程上的直接体现——理论上分析的时间复杂度，在真实环境中会以性能数字的形式找上门来。

4.2 ListItr内部类的职责

LinkedList的迭代器是在listIterator(int index)方法中返回的：

public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); }

ListItr的核心字段有四个：

private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount;

lastReturned记录最近一次通过next()或previous()返回的节点，next是指向下一个要返回节点的指针，nextIndex记录当前迭代到第几个位置，expectedModCount保存创建迭代器时的modCount值。

next()方法的逻辑如下：

public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; }

关键在于checkForComodification：

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

它会在每次next()或previous()时校验modCount是否仍然等于创建迭代器时的值。如果期间有任何结构性修改操作（比如add、remove、clear）改变了modCount，迭代器就会立刻抛出ConcurrentModificationException。这种fail-fast策略保证了迭代器在“看到”不一致状态时第一时间失败，而不是继续使用已经过期的内部指针产生不可预期的行为。

4.3 迭代器的remove方法：模版字段的正确用法

很多人知道“遍历的时候不要用list.remove()，要使用迭代器的remove()”，但不知道背后的原理。迭代器的remove()是这样实现的：

public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; }

这里有几个细节很有意思。lastReturned为空时会抛IllegalStateException，这是因为迭代器刚创建时还没有通过next()获取过元素，此时不允许直接remove。执行unlink(lastReturned)后，因为modCount增加了，所以这里必须手动把expectedModCount同步为最新的modCount值，否则下次调用next时就会误报并发修改异常。

如果next == lastReturned，说明刚删除的是通过next()返回的节点，此时需要把next指针移到lastNext；否则说明删除的是通过previous()返回的节点，需要把nextIndex自减。最后把lastReturned置为null，确保下一个remove操作前必须先调用next或previous。这套状态管理的严谨程度，值得每一个写容器的开发者学习。

4.4 增强for循环与迭代器的关系

在Java里写for (String s : list)这种增强for循环时，编译器会自动把它转换成迭代器调用。这就是为什么增强for循环遍历LinkedList性能正常的原因。但这里有一个绝大部分人会踩的坑：在增强for循环里删除元素。

for (String s : list) { if (s.equals("delete")) { list.remove(s); } }

这段代码运行到第二次迭代时，会抛ConcurrentModificationException。因为增强for循环底层用的是迭代器，每次循环都会调用checkForComodification，而list.remove(s)会修改modCount，导致迭代器的expectedModCount和它不一致，于是第一时间抛异常。

正确的删除姿势有两种：一种是使用迭代器的remove()方法，它会在删除后同步expectedModCount；另一种是使用JDK 8开始的removeIf()方法，直接传入过滤条件，内部帮你处理了并发修改的逻辑。

list.removeIf(s -> s.equals("delete"));

这个API比手写移除更简洁，而且从JDK 8开始是默认推荐的做法。我见到很多老项目还在用迭代器remove的老写法，也能跑，但阅读性和安全性都不如removeIf。这也是一个很好的源码启发：读源码能帮你发现很多“更新更好的替代写法”。

5. 性能实测与选型对比

5.1 我做的基准测试：数据会说话

理论分析再天花乱坠，不如直接跑一组数据来得直观。下面是我在实际开发环境（JDK 8，8G内存，Win10）下做的一组对比测试，数据量分别为1万、10万和100万，测试ArrayList和LinkedList在尾部插入、头部插入、随机访问和迭代遍历四种场景下的耗时。

先说明一下，这些数字受机器环境影响会有浮动，但趋势是非常明确的。

列表最直观的结论：尾部追加时，ArrayList反而比LinkedList快。原因很简单，ArrayList的追加是内存连续写，触发扩容的概率低，而且扩容时用的是Arrays.copyOf这种高效的数组拷贝；LinkedList每次都要new一个Node对象，还要维护两块指针的赋值，对象分配和内存不连续性带来的开销就显露出来了。

头部插入则是LinkedList的绝对主场，100万数据量下耗时只有ArrayList的百分之一不到。因为ArrayList的头插需要把整个数组往后挪一位，这种大规模搬迁操作是O(n)的，而LinkedList只需要改两个指针。

随机访问的差距更是触目惊心，LinkedList慢了差不多三个数量级。至于for+get遍历，数据量一旦过10万，LinkedList的耗时就开始爆炸式增长，这就是前面说的O(n²)复杂度在现实中的落地表现。

5.2 为什么实际项目中ArrayList反而更常用

很多人看完上面的数据会疑惑：既然LinkedList查询慢、遍历慢，为什么还要学它？我的看法是：LinkedList更适合做“结构实验”的教材，而不是“业务主力”的工具。

从工程经验来看，除非你在写一个真正需要频繁在头部插入和删除的队列场景，否则LinkedList并不能给你带来性能上的优势。现代CPU对连续内存的缓存预取非常友好，ArrayList在遍历时能利用cache line的高命中率，而LinkedList则完全享受不到这种红利。每次访问一个节点都是一次随机内存访问，CPU需要频繁等待主存数据，这在大型集合的场景下是非常致命的。

还有一个非常冷门但真实存在的因素：LinkedList每个节点需要额外存储两个指针（24字节以上，不含对象头对齐），相同数据量下内存占用大约是ArrayList的好几倍。在内存敏感的服务端场景，这可能直接导致GC压力上升。

所以我的建议是：默认用ArrayList就对了。只有当代码逻辑里明确需要频繁进行首尾操作、且随机访问极少的场景，比如LRU缓存、任务调度队列、消息缓冲区，才考虑用LinkedList。另外，如果你需要栈或队列，直接使用ArrayDeque往往也优于LinkedList，是因为它基于循环数组，内存更紧凑，且两端的操作都是O(1)。这个结论在JDK官方文档里其实都能找到依据。

5.3 快速验证测试代码

如果你也想像我一样在自己机器上跑一跑，可以复制下面这段简单的测试代码：

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListBenchmark { public static void main(String[] args) { int size = 100_000; List<Integer> arrayList = new ArrayList<>(); List<Integer> linkedList = new LinkedList<>(); // 尾部插入 long start = System.nanoTime(); for (int i = 0; i < size; i++) arrayList.add(i); long arrayAddCost = System.nanoTime() - start; start = System.nanoTime(); for (int i = 0; i < size; i++) linkedList.add(i); long linkedAddCost = System.nanoTime() - start; System.out.println("ArrayList尾部add耗时(ms): " + arrayAddCost / 1_000_000.0); System.out.println("LinkedList尾部add耗时(ms): " + linkedAddCost / 1_000_000.0); // 取中间元素 int mid = size / 2; start = System.nanoTime(); arrayList.get(mid); long arrayGetCost = System.nanoTime() - start; start = System.nanoTime(); linkedList.get(mid); long linkedGetCost = System.nanoTime() - start; System.out.println("ArrayList随机get耗时(ms): " + arrayGetCost / 1_000_000.0); System.out.println("LinkedList随机get耗时(ms): " + linkedGetCost / 1_000_000.0); } }

跑完这组数据，你对LinkedList的认知绝对会从“背概念”变成“有体感”。编程这件事，很多结论不自己亲自验证一次，永远只是口号。

6. 面试题与真相：LinkedList的“传说”与“现实”

6.1 高频面试题：八股文背后的源码验证

面试Java基础的时候，LinkedList必然会被问到，下面这些问题是我在面试别人和复盘自己面试时总结出来的高频题：

问题一：ArrayList和LinkedList有什么区别？

面试官想听到的完整答案应该是：底层数据结构不同，ArrayList基于动态数组，LinkedList基于双向链表；随机访问ArrayList是O(1)，LinkedList是O(n)；插入删除在已知节点位置时LinkedList是O(1)，ArrayList需要移动元素；尾部追加ArrayList虽然偶尔扩容，但均摊下来和LinkedList差距很小；内存占用上LinkedList每个节点需要存储两个指针，比ArrayList更耗内存；迭代遍历时两者差异不大，但按index遍历LinkedList会退化成O(n²)。

问题二：LinkedList能当作栈用吗？

能。LinkedList实现了Deque接口，所以有push(E e)、pop()、peek()等方法，完全遵循栈的LIFO语义。但严格来说，Java官方推荐使用ArrayDeque作为栈实现，因为它性能更好、内存更紧凑。面试时能主动提到这个对比，会显得你对源码做过功课。

问题三：为什么LinkedList插入删除不一定比ArrayList快？

因为“插入删除快”的前提是已经定位到了目标位置。add(int index, E e)需要先通过node(index)定位到index位置，这一步就是O(n)了。只有在头部或尾部操作时，LinkedList才有稳定的O(1)优势。如果是在中段频繁操插入删除，ArrayList的批量移动反而更快，因为System.arraycopy是经过JVM高度优化的原生方法。

问题四：LinkedList是线程安全的吗？

不是。LinkedList所有方法都没有使用synchronized或Lock，也没有使用volatile修饰内部状态，它就是一个普通的非线程安全集合。如果多线程并发访问并修改，需要外部加锁，或者使用Collections.synchronizedList(new LinkedList<>())。在JDK中还有一个ConcurrentLinkedDeque专门用于高并发队列场景，它基于CAS实现，读多写少的场景性能很好。

6.2 踩坑记录：ConcurrentModificationException 真实案例

我在真实项目中遇到过这么一个问题：有个消息推送模块，用ArrayList缓存待推送的消息，消费者线程定时遍历这个列表发送消息，发送成功后从列表里remove掉对应消息。结果这个模块上线第一天就开始随机抛ConcurrentModificationException，日志里全是堆栈。

问题就出在“遍历过程中执行了remove”这个动作，两个线程同时操作同一个list，一个在迭代，一个在删除，迭代器的expectedModCount和实际的modCount对不上了。这种并发问题用LinkedList或ArrayList都一样会触发，不是因为链表导致的，而是集合并发修改的固有语义。

正确的修复方案有两个方向：一是用CopyOnWriteArrayList，每次修改都会复制一份新的数组，迭代器永远在旧快照上工作，不存在fail-fast异常，但写操作代价高；二是改用并发队列ConcurrentLinkedQueue，天然支持多生产者多消费者模型，完全不需要手动加锁。

这个案例让我意识到：源码里的fail-fast机制不是设计缺陷，而是一个非常实用的安全护栏。它让你在并发环境用错了容器结构时，第一时间发现问题，而不是在数据污染之后花大代价排查。

6.3 SubList 的隐藏陷阱：为什么修改SubList会影响原列表

LinkedList继承了AbstractList的subList(int fromIndex, int toIndex)方法，并返回一个内部的SubList对象。这个对象看起来是原列表的“视图”，底层其实持有原LinkedList的引用。所以对SubList做任何修改，最终都会作用到原LinkedList上。

乍一听好像很方便，但很容易踩坑。比如你想取出List的前100个元素再单独操作，结果不小心对SubList做了clear()，原列表的前100个元素全部被删掉了。这种“引用共享”的语义在源码里写得很清楚，但使用的时候根本不会注意。

更隐蔽的是，当你先创建了一个SubList，然后对原LinkedList执行add操作，再通过SubList遍历时，会发生什么？答案依然是ConcurrentModificationException。因为SubList的内部迭代器也维护了expectedModCount，原LinkedList的add操作会修改modCount，于是两个迭代器都罢工了。

所以我的建议是：如果你需要SubList，就在创建SubList之后立刻拷贝一份新集合再操作，比如new ArrayList<>(list.subList(0, 100))，切断引用共享，避免所有后续问题。

6.4 为什么现在很少有人直接使用LinkedList

翻一翻Java代码库，LinkedList在真实业务代码中的出现频率确实越来越低。这不是因为它不好，而是ArrayDeque和ArrayList覆盖了绝大多数场景。ArrayDeque在队列和栈场景下完胜LinkedList，ArrayList在动态数组场景下因为内存连续性和缓存友好性而胜出。

从数据结构本身来说，只有一种情况我仍然会主动选择LinkedList：当元素数量极其巨大，且需要在链表已知位置反复执行插入删除，而随机访问又几乎不发生的时候，LinkedList才能稳稳地胜过ArrayList。但说实话，这种极端场景在普通CRUD系统里几乎不存在。

如果你在做算法题或者写一些底层中间件，LinkedList依然是非常趁手的工具。它在LeetCode题解里出现频率很高，比如LRU缓存就是经典的“HashMap + 双向链表”结构，很多人的手写实现就直接借鉴了LinkedList的Node结构。理解LinkedList源码，其实是在理解所有双向链表变体的基础模板。

7. 总结之外：从LinkedList源码能学到什么

说句实话，LinkedList源码的价值不只是让你在面试里多背几题八股文，更重要的是培养一种读代码的思维习惯。每一处if (prev == null)的边界判断、每一个modCount++的意图、每一步= null的GC辅助，背后都藏着JDK作者对Java语言和内存模型的理解。

我现在每读到一段优秀源码，都会习惯性地问自己三个问题：作者为什么这么写？这么写的先决条件是什么？如果把先决条件破坏掉，会发生什么？带着这三个问题回头看LinkedList，你会发现每一段代码都不是多余的，每一个细节都指向“保证链表结构不变式成立”这个核心目标。

最后再分享一个小技巧：读书时不要只盯着LinkedList单个类看。你可以把它和ArrayList的ensureCapacity放在一起对比，再把它和Collections.synchronizedList的装饰器模式放在一起对比，你会发现Java集合框架的设计层次是环环相扣的。理解了这层关系，不管面试官怎么变着法子问Java集合，你都能从容应对。编程这条路没有捷径，读源码就是最快的那条慢路。