LinkedList源码拆解：双向链表如何优雅实现栈、队列与双端操作

在Java日常开发里，提到List大家第一反应基本都是ArrayList，数组加下标的随机访问实在太顺滑。但有一个类平时不怎么起眼，一旦遇到频繁头尾增删、需要双端操作、或者想顺手搭一个栈和队列，它才是真正的主角——这就是LinkedList。这篇文章不打算只罗列API，我会从源码实现一步步拆开它的内部结构，把链表、栈、队列三件事一次讲清楚，再配上我自己实测过的性能数据和踩坑记录。适合正在复习集合源码的开发者，也适合写业务代码时纠结该用ArrayList还是LinkedList的朋友。

1. 定位篇：LinkedList凭什么在ArrayList之外活得很好

1.1 ArrayList的三道坎，正好是LinkedList的主场

先回忆一下ArrayList。它底层是Object[]数组，默认容量10，扩容时按1.5倍增长。数组确实快，但有三道坎绕不过去。

第一道坎是扩容。容量不够时，要重新new一个更大的数组，然后用System.arraycopy把旧数据整体搬过去。单次扩容看起来还好，但数据量大或者频繁写入时，这个拷贝动作会反复发生，整体耗时会非常难看。第二道坎是中国插入和头部删除。中间插入意味着后续所有元素都要后移一位，Java里这个后移也是对某一段数组做arraycopy，数据量大时成本相当可观。第三道坎是双端操作。如果需求要求"从头部取数据、从尾部放数据"，ArrayList只能靠两个下标手动维护，还要处理扩容后下标失效的问题，代码写起来又丑又容易错。

LinkedList在这几个场景里是天然更优的选择：它不需要扩容，来一个元素就分配一个节点；头部和尾部的增删都是O(1)；双端操作有现成API。我接过一个很典型的项目，两个线程之间要传消息，一个往里写、一个从另一端取。最初用ArrayList，头部删除时数据量大之后明显卡顿，换成LinkedList后两端操作都是常数级，问题直接消失。有时候性能问题不一定是实现算法有问题，可能就是集合类型没有选对。

1.2 内存里的双向链表长什么样

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

每个元素不是存放在连续内存里，而是单独创建一个Node对象，通过prev和next两个引用串成一条链。LinkedList内部维护两个关键引用：first指向头节点，last指向尾节点。新增节点时，只需要修改相邻节点的引用关系，不需要移动任何已有数据，这是它和数组最本质的差别。

我常用一个生活类比来解释：数组像电影院连排座位，位置固定，想中间插人就得整排挪动；链表像游乐场排队，每个人只要记住自己前面是谁、后面是谁，中间突然插队，只需要让前面那个人的"下一个"指向新来者，让新来者记住前后的连接关系。这就是为什么链表的插入和删除天然比数组灵活。

还有一个容易被忽略的点：LinkedList允许存null。因为节点本身是引用对象，null可以作为一个普通元素存在，它不参与链式关系。这个特性在某些需要用null做占位符的场景里很实用，但也带来了队列判空时的隐患，这一点在后面专门讲队列时我会重点提醒。

1.3 LinkedList的“双重身份”：List + Deque

LinkedList同时实现了List 和Deque 两个接口，这在Java集合体系里很少见，但理由充分：双向链表本身就是一串按顺序排列的元素，天然可以作为List；它同时有头尾两个可操作的端点，天然可以作为Deque。

也就是说，同一个类可以有三种完全不同的使用视角。当我对某个模块只需要"列表"语义，会用List引用去接，屏蔽掉队列的API；当需要栈或队列语义，就用Deque或Queue引用去接。这里有个设计习惯想分享：声明变量时尽量用接口类型，不要直接写LinkedList。比如Deque stack = new LinkedList<>()，而不是LinkedList stack = new LinkedList<>()。前者暴露的API更清晰，后面换实现类也容易。如果你把LinkedList所有能力都暴露出去，调用方既能看到addFirst，又能看到get，代码意图会变得模糊。

2. 源码篇：把核心操作复杂度掰开揉碎

2.1 查询和修改：O(n)背后的遍历逻辑

ArrayList里list.get(5)是O(1)，数组下标直接用基址加偏移量就能算出位置。LinkedList完全不同，get和set都要先通过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; } }

源码里有这样一段优化：先判断index在链表的前半段还是后半段，决定从头还是从尾找。这里有两个点值得展开。

第一，即使做了方向的优化，时间复杂度依然是O(n)，只是把常数项缩小了一半。第二，get(int index)每次调用都重新从头或从尾遍历，如果你在循环里写list.get(i)，累计下来就是O(n^2)。我遇过一次线上接口慢得离谱，排查半天发现是一个子模块里有人对LinkedList做随机读取，数据量到几十万后响应时间变成几十秒，换成ArrayList后几乎秒开。

所以第一条选型规则非常确定：如果你主要做随机访问，LinkedList是真正的负面教材，它的强项从来不在这里。

2.2 插入和删除：到底哪个环节是O(1)，哪个环节拖慢了整体

教科书上常说"链表插入删除是O(1)"，这话有前提：你必须已经握着目标节点，或者就在头部、尾部操作。如果是list.add(2, x)这种按下标的插入，仍然要先经过node(index)找到位置，查找是O(n)，所以整体还是O(n)。

先看add方法的高级流程：先检查index是否越界，如果index等于size，直接linkLast把新节点挂到尾部；否则通过node(index)取出当前位置的节点，再调用linkBefore把新节点插到它前面。也就是说，时间主要花在"找位置"上，真正改引用只涉及几个赋值。

反过来看真正的O(1)场景，比如addFirst、addLast，以及迭代器的add、remove，因为迭代器手里本来就握着当前节点，不需要再从头找。unlink方法和link方法一样，只需要修改前后节点的引用，再把当前节点的所有引用置空，帮助GC回收。

这个结论对业务开发的指导意义很大：如果操作集中在已知位置，比如总是头部或尾部，或者边遍历边删除，LinkedList优势明显；如果只是随机下标插入删除，ArrayList因为有System.arraycopy的底层能力，在大块数据挪移时反而可能更快。我早期做组件开发时踩过坑，误以为只要是链表就一定快，实测在中间位置插入时ArrayList反而胜出，原因就是链表找节点多出来的遍历时间抵消了插入操作本身的高效。

2.3 indexOf、contains与迭代器的使用姿势

indexOf和contains都靠equals逐个比较，复杂度O(n)。如果列表里存的是自定义对象，equals没重写的话，比较的就是引用，结果会非常诡异。

迭代器是LinkedList最推荐的遍历方式，不只是O(n)线性，更重要的是支持边遍历边删除。ListIterator除了next还有previous，可以双向移动，在链表上使用非常自然。

使用迭代器删除有一个极易踩坑的规则：必须先调用next()，才能调用remove()；连续两次remove会抛IllegalStateException，因为报错时还没有新的元素被返回。这个约束不是LinkedList特有的，但因为它自带fail-fast机制，一旦并发修改或者迭代方式不合法，异常会立刻暴露。

顺带说一句：LinkedList内部维护的modCount，是用来记录结构化修改次数的。迭代器在遍历时会记下初始modCount，每次next或remove之后都会校验，发现集合被其他线程修改就会抛ConcurrentModificationException。所以多线程环境下，如果需要共享一个LinkedList，必须自己加锁或用并发容器，裸用它做共享队列非常危险。

3. 实战篇：用LinkedList实现栈和队列的完整姿势

3.1 当栈用：push/pop的细节与ArrayDeque对比

在算法题和实际项目中，当需要栈结构时，现在普遍推荐用Deque接口，而LinkedList是Deque接口的经典实现。Deque提供了一套标准的栈方法：push压栈、pop出栈、peek查看栈顶。

Deque<String> stack = new LinkedList<>(); stack.push("第一层"); stack.push("第二层"); stack.push("第三层"); System.out.println(stack.peek()); // 第三层 System.out.println(stack.pop()); // 第三层 System.out.println(stack.pop()); // 第二层

这里要注意，push内部其实就是addFirst，pop内部就是removeFirst，都作用于链表头。LinkedList的头部操作是O(1)，所以拿它当栈完全正确。但我必须说一个性能上的事实：如果只使用栈语义，不需要列表操作，ArrayDeque通常更合适。

原因在于ArrayDeque底层是循环数组，内存连续，局部性很好，CPU缓存命中率比链表高，实测在十万级和百万级操作下会明显更快。而LinkedList每个元素都是独立Node对象，地址分散，遍历head和tail之间跳来跳去，缓存命中率天然吃亏。所以我的习惯是：需要更强栈/队列性能的时候选ArrayDeque，需要同时具备列表和双端语义的时候选LinkedList。多掌握一种实现没有坏处，但选型时心里要有数，别把LinkedList当成唯一的栈实现。

3.2 当队列用：offer/poll的正确打开方式

队列语义下，推荐用Queue引用接LinkedList。Queue接口定义了offer入队、poll出队、peek看队头，这些在LinkedList中都是O(1)。

Queue<Integer> queue = new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); System.out.println(queue.peek()); // 1，不移除 System.out.println(queue.poll()); // 1，移除并返回 System.out.println(queue.poll()); // 2

这里有个非常重要的坑：LinkedList允许null入队，但Queue接口规范明确要求实现类拒绝null，因为poll和peek都是用返回null表示"队列为空"，如果允许null入队，语义就矛盾了。LinkedList为了兼容List语义没有强制拦截null，所以用了它，就只能用isEmpty()判空，不要依赖返回null判断队列是否结束。

这个坑我在真实项目里见人踩过。一个消息消费程序，生产方异常时往队列里放了一个null，消费方发现poll返回null，以为是队列空了，直接退出循环，消息就凭空丢了。排查半天才定位到，就是判空方式不对。另外一个提醒：LinkedList不是线程安全的，多线程共享队列时不要裸用，要么加锁，要么直接换成ArrayBlockingQueue或LinkedBlockingQueue这类线程安全队列。单线程或线程内部使用才适合直接它。

3.3 性能实测：同样是增删，为什么结论差这么多

我实际跑过一个简单测试，分别对比ArrayList和LinkedList在几个典型场景上的表现。数据量10万，用System.nanoTime()计时，为避免JIT预热影响，先跑几轮再取稳定值。

int n = 100_000; long start = System.nanoTime(); List<Integer> list = new LinkedList<>(); for (int i = 0; i < n; i++) { list.add(i); } System.out.println("LinkedList尾部add: " + (System.nanoTime() - start) / 1_000_000 + " ms"); start = System.nanoTime(); List<Integer> arrayList = new ArrayList<>(); for (int i = 0; i < n; i++) { arrayList.add(i); } System.out.println("ArrayList尾部add: " + (System.nanoTime() - start) / 1_000_000 + " ms");

实测结果和理论基本一致：尾部添加，ArrayList略快，LinkedList差不了多少，都在同一量级；头部添加，LinkedList毫秒级，ArrayList因为每次add(0, x)都要整体后移，耗时明显更高；随机访问，ArrayList是纳秒级，LinkedList是毫秒级，差距有好几个数量级。

这个结果说明，判断要不要用LinkedList，不要只看"是否涉及插入删除"这种空泛标准，而要看操作集中在哪一端。总是操作头部或尾部，比如实现缓存淘汰、双端队列、撤销栈，LinkedList很合适；如果总是按索引访问，哪怕涉及到插入，也应该重新思考，因为插入前查找O(n)的成本会吃掉链表增删高效的优势。

4. 避坑篇：高频面试题、排查记录与选型建议

4.1 常见问题与排查速查表

把开发过程中的常见问题整理成一张速查表，遇到类似症状直接对着定位：

这张表不是背答案用的，而是排查时的思维导图。看到卡顿，先想是不是随机访问；看到异常，先想是不是并发修改；看到结果不对，先想是不是null语义和equals实现有问题。

4.2 遍历删除、equals、序列化、泛型擦除这些坑一次说清

先说遍历删除。很多新人用fori循环，删除后忘了做下标回退：

for (int i = 0; i < list.size(); i++) { if (条件) { list.remove(i); // 这里不执行i--，就会漏删 } }

在LinkedList里，就算加了i--，每次remove(i)也都要从头部或头尾找节点，效果不理想。正确的方案是迭代器删除：

Iterator<String> it = list.iterator(); while (it.hasNext()) { if (条件) { it.remove(); } }

迭代器remove是O(1)的，不会因为删除导致索引错乱，也不会触发fail-fast。JDK 8以后还能用list.removeIf(条件)，底层就是迭代器循环，更简洁，实战里我非常推荐。

再说equals。LinkedList的equals继承自AbstractList，会比较两个列表长度、每一对元素是否满足equals。两个LinkedList即使内部结构不同，只要元素顺序和内容一致，equals就是true。这本身没问题，问题在于如果存的是自定义对象而没重写equals和hashCode，contains、remove(obj)就全用引用比较，结果非常难定位。所以往集合里放自定义对象，第一件事就是重写equals和hashCode，这不是建议，是纪律。

然后是序列化。LinkedList实现了Serializable，序列化输出的是每个节点的item值；反序列化时，会从first开始逐个重建节点，整个过程是O(n)。如果列表特别大，反序列化耗时不可小觑。对这一点没有太多优化空间，要么换数组结构，要么自己做分段存储，内存敏感场景下设计时要提前考虑。

最后是泛型擦除。LinkedList 和LinkedList 运行时都是同一个Node类，类型信息在编译后就被擦除了。如果你通过反射往列表里塞一个不同类型对象，运行时不会立刻报错，等遍历取出并强转时才抛ClassCastException。这种问题在工程里非常隐蔽，遇到类似的强转异常，先怀疑反射和反序列化是否绕过了编译期校验，别只盯着业务代码。

4.3 我的选型决策清单

把理论落到实际项目，我会这样决策：

• 列表大小基本固定、需要频繁随机访问，直接用ArrayList。
• 不确定大小，主要尾部追加、偶尔头部操作，优先ArrayList，必要时用双端队列接口替代。
• 明确要频繁操作头部和尾部，且不需要随机访问，果断用LinkedList，或者如果只是栈/队列语义，用ArrayDeque。
• 需要实现LRU、淘汰队列、撤销栈这类双端结构，LinkedList或ArrayDeque都行。
• 多线程共享队列，不要裸用LinkedList，选择并发容器更踏实。

这里还有一个容易被忽略的点：LinkedList对GC的压力普遍比ArrayList大。每个元素都是一个Node对象，包含自身数据和两个连接引用，如果存放的是大量小对象，GC会明显感受到压力。在内存敏感或高吞吐场景，比如每秒几万条消息的临时队列，用数组实现环形队列通常会更稳。选型不能只看单次操作的时间复杂度，还要把对象分配频率和缓存局部性一并算进去。

我对LinkedList最深的体会，不是它比ArrayList快，而是"在适合的场景里用对工具"。刚学Java那阵子，我以为链表全面优于数组；后来写多了才发现，大部分业务代码用ArrayList就够了，LinkedList的用武之地集中在双端操作和栈队列场景。如果你读完这篇，能解释清楚为什么LinkedList当栈和队列时是O(1)、当List随机访问时是O(n^2)，那说明你真的把它搞懂了。实在记不住结论也没关系，就记一句：遇到大量随机访问，第一反应是迭代器而不是get(i)；遇到头部插入删除和栈队列场景，第一反应是LinkedList而不是ArrayList。这套判断，下次面试和写代码时都能帮你省不少事。