LinkedList 与双端队列：当"连续内存"不再是最优解（017）

覆盖考点：017｜LinkedList 与队列结构：双向链表、Deque 用法及选型边界

适合读者：高级 Java 工程师、技术专家、架构师候选人

预计阅读时长：35–40 分钟（文末问答不计入）

上一篇讲 ArrayList 时反复强调一句话：它的一切代价，都是"连续内存"这个特性的副作用。LinkedList 是对这句话的正面回应——它彻底放弃了连续内存，换来了完全不同的成本模型。但很多人对 LinkedList 的理解停留在"链表，插入删除快"这一句话上，说不清它到底实现了几个接口、为什么能同时当 List、Queue、Deque 用，也说不清为什么阿里的《Java 开发手册》明确建议"非顺序访问场景不要用 LinkedList 当作首选"。

面试官在这一考点上通常按这条链追问：LinkedList 的底层结构是什么 → 它如何同时满足 List/Queue/Deque 三套接口契约 → 和 ArrayList 的成本模型到底差在哪、差多少 → ArrayDeque 是什么、为什么官方文档建议用它替代 LinkedList 做队列 → 现在生产代码里 LinkedList 还有没有存在的价值。本文按这个顺序展开。

一、双向链表：LinkedList 的底层结构

1. 节点是什么：不再是数组下标，而是散落在堆里的对象

LinkedList 内部维护的核心是一个私有的 Node<E> 内部类：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

每个元素被包装成一个 Node 对象，item 存放真正的数据，next 指向下一个节点，prev 指向上一个节点。这些 Node 对象在堆内存里没有任何连续性要求——它们可能散落在堆的任意角落，彼此之间纯粹靠指针（引用）串联。LinkedList 本身只保留两个引用：first（指向链表头节点）和 last（指向链表尾节点），再加一个 size 计数器。

这和 ArrayList 的"一块连续内存 + 基地址"是两种完全不同的组织方式：ArrayList 用地址算术换来了 O(1) 随机访问，但要求内存连续、大小固定；LinkedList 放弃了这种连续性要求，换来了"插入删除只需要改指针，不需要搬数据"的能力，但代价是——要访问某个节点，必须从头或从尾开始，沿着指针一个个走过去。

2. 双向 = 两个方向都能走

之所以叫"双向"链表而不是普通单向链表，是因为每个节点同时持有 next 和 prev。这带来两个直接收益：可以从头遍历也可以从尾遍历，Deque 需要的"两端都能高效操作"正是建立在这个基础上；删除一个节点时不需要额外记录"前驱节点"——单向链表删除一个节点必须先找到它的前驱（因为要把前驱的 next 指向被删节点的下一个），双向链表里节点自己就持有 prev，删除逻辑简单直接。

二、一个类，三套接口：List、Queue、Deque

1. LinkedList 的继承声明

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

Deque（double-ended queue，双端队列）本身继承自 Queue，所以 LinkedList 一个类同时满足了 List（有序、可按下标访问的集合）、Queue（先进先出的队列）、Deque（两端都能进出的双端队列）三套接口契约。这不是巧合，而是双向链表这个数据结构天然具备的能力：链表的头尾都能 O(1) 访问和修改，正好对应了 Deque 定义的 addFirst/addLast/removeFirst/removeLast 这组操作。

2. 同一个操作，三套方法名

因为要同时满足三套接口，LinkedList 里出现了大量语义相同但方法名不同的 API，这也是很多人用起来"记不住哪个方法叫什么"的根源：

add 和 offer 语义上略有差异：在容量受限的队列实现里 add 满了会抛异常，offer 满了返回 false；但 LinkedList 本身没有容量上限，这个区别在 LinkedList 上体现不出来，只有在换成 ArrayBlockingQueue 这类有界队列时才有实际意义。

三、成本模型：和 ArrayList 到底差在哪

1. 头尾操作：LinkedList 全面占优

addFirst/addLast/removeFirst/removeLast 都是 O(1)——因为 LinkedList 始终持有 first 和 last 两个引用，头尾节点可以直接定位，插入删除只是改几个指针的指向，不涉及任何数据搬迁。这一点上 LinkedList 明显比 ArrayList 更有优势：ArrayList 头部插入删除是 O(n)，因为要整体搬迁数组元素。

2. 随机访问：LinkedList 全面落后

get(index) 在 LinkedList 上是 O(n)——源码里能直接看到这一点：

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 更靠近头部还是尾部，选择从更近的一端开始遍历，最多走 size / 2 步——但这只是把常数系数减半，时间复杂度依然是 O(n)，因为链表节点没有地址算术这条捷径，唯一的定位方式就是沿着指针一步步走。这是 LinkedList 相比 ArrayList 最大的短板，也是"非顺序访问场景不建议用 LinkedList"这条建议的直接依据。

3. 中间插入删除：常被误解的"伪 O(1)"

很多人会说"链表中间插入删除是 O(1)，数组是 O(n)"，这个说法只对了一半。如果你已经手里攥着目标节点的引用（比如用 ListIterator 遍历到了这个位置），那么在这个位置插入或删除确实只需要改指针，是真正的 O(1)；但如果你只有一个下标 index，LinkedList 的 add(index, e)/remove(index) 内部首先要调用**node(index)**找到这个位置，这一步本身就是 O(n)，找到之后改指针才是 O(1)。所以按下标操作 LinkedList 中间元素，总代价依然是 O(n)——和 ArrayList 按下标操作中间元素的 O(n) 属于同一量级，只是"贵在哪一步"不同：ArrayList 贵在搬数据，LinkedList 贵在找位置。

真正体现 LinkedList 优势的场景，是配合**Iterator**/**ListIterator**边遍历边操作——遍历过程中天然持有当前节点的引用，此时插入删除是真正的 O(1)，不需要重新定位。

4. 一张表说清楚 LinkedList vs ArrayList

四、ArrayDeque：为什么它比 LinkedList 更适合当队列/栈

1. ArrayDeque 是什么：基于数组的循环队列

ArrayDeque（Array Double Ended Queue）底层是一个可扩容的循环数组（circular array），用 head 和 tail 两个下标标记队列的头尾位置，两端都能 O(1) 操作，扩容策略和 ArrayList 类似（成倍扩容）。它同样实现了 Deque 接口，API 和 LinkedList 高度重合，很多场景可以直接替换。

2. 为什么 JDK 官方文档建议优先用 ArrayDeque 而不是 LinkedList 做队列/栈

Deque 接口的 Javadoc 里明确写着一句话：作为栈使用时，ArrayDeque 可能比 Stack 更快；作为队列使用时，可能比 LinkedList 更快。原因有三层：

• 内存局部性（cache locality）：ArrayDeque 的元素存储在连续（或分段连续）的数组里，现代 CPU 的缓存预取机制对连续内存访问非常友好；LinkedList 的节点分散在堆的各个角落，遍历时几乎每一步都可能触发一次缓存未命中（cache miss），实际运行速度往往比理论时间复杂度看起来的差距更大；
• 对象开销：LinkedList 每存一个元素都要额外创建一个 Node 对象，每个 Node 对象本身有对象头（通常 12-16 字节）、item/next/prev 三个引用字段（每个引用在 64 位 JVM 开启指针压缩后通常是 4 字节），算下来每个元素的额外内存开销远高于 ArrayDeque 里"just a slot in an array"；
• 它不支持随机访问，也不需要：ArrayDeque 不实现 List 接口，专注于双端队列这一种语义，没有 LinkedList 身上"既要满足 List 又要满足 Deque"的接口负担，实现更纯粹。

3. 什么时候 LinkedList 仍然有价值

ArrayDeque 不允许存 null 元素（用 null 作为内部"空位"的哨兵标记），如果业务逻辑真的需要在队列里存 null，LinkedList 是备选项；此外如果需要的是严格的 List 语义（比如需要用 ListIterator 在任意位置双向遍历并做 O(1) 结构调整、或者需要 subList 视图），LinkedList 作为 List 实现仍然有其位置。但单纯当队列、栈或双端队列使用，ArrayDeque 几乎总是更优选择。

五、常见误区与工程实践

1. "链表插入删除比数组快"不能不加条件地套用

如前所述，这句话只在"已持有节点引用"的场景成立。如果代码写成 for (int i = 0; i < list.size(); i++) { if (condition) list.remove(i); } 这种按下标遍历 LinkedList 并删除，每次 remove(i) 都要重新从头/尾定位，整体复杂度会退化到 O(n²)，比同样写法的 ArrayList（虽然也是 O(n²)，但常数因子小得多）还慢。正确写法应该用 Iterator.remove() 或 ListIterator，让删除操作发生在已经定位好的节点上。

2. LinkedList 实现了 List，但不代表适合随机访问场景

如果代码里对同一个 List 变量既有大量 get(index) 调用又有大量头尾插入删除，选型时要评估哪种操作是主要瓶颈——绝大多数业务场景里随机访问的频率远高于头尾操作，这也是为什么 ArrayList 是默认首选、LinkedList 反而是"特殊场景才用"的次选。

3. 生产队列场景的实际选型顺序

单线程/无并发场景的双端队列、栈：优先 ArrayDeque；需要并发安全的队列：ConcurrentLinkedQueue（无锁）或 LinkedBlockingQueue（有阻塞语义）；需要严格 List 语义又要频繁头部操作的场景：才轮到 LinkedList。这也是《阿里巴巴 Java 开发手册》里"直接使用 LinkedList 前先评估随机访问频率"这条规范的实际工程依据。

六、面试追问链

延伸阅读

• JDK 源码：java.util.LinkedList（Node 内部类、node(int)、linkFirst/linkLast）
• JDK 源码：java.util.ArrayDeque（循环数组、head/tail 下标运算）
• CPU 缓存局部性（cache locality）与数据结构性能的关系
• 《阿里巴巴 Java 开发手册》集合处理章节：LinkedList 使用建议
• java.util.concurrent.ConcurrentLinkedQueue 与 LinkedBlockingQueue：并发场景下的队列选型

问答（不计入阅读时长）

Q1：LinkedList 用 push()/pop() 当栈用的时候，实际调用的是哪一端的操作？

A：LinkedList 实现 Deque 接口时，push(e) 等价于 addFirst(e)，pop() 等价于 removeFirst()——也就是说 LinkedList 把"栈顶"定义在链表的头部，而不是尾部。这个选择不是随意的：push/pop 都发生在头部，意味着"后进先出"（LIFO）语义天然对应"头部插入、头部取出"，和栈的直觉完全一致。如果误以为 push 是往尾部加（很多人受数组实现的栈的影响，习惯把尾部当栈顶），会在需要严格顺序保证的场景（比如手写一个括号匹配算法）里得到完全错误的结果。

Q2：既然 ArrayDeque 不让存 null，那**peek()**返回 null 是什么意思？和"元素本身是 null"冲突吗？

A：不冲突，而且这正是 ArrayDeque 禁止存 null 的设计目的。Queue/Deque 接口里大量方法用 null 作为"特殊返回值"，比如 peek()、poll() 在队列为空时返回 null，表示"没有元素"而不是抛异常。如果 ArrayDeque 允许存放 null 元素，调用方拿到 poll() 返回的 null 时就无法区分"队列本来就空"还是"队列里真的有一个 null 元素"——这种歧义是接口设计上不能接受的。所以 ArrayDeque 从源头上禁止插入 null（addFirst(null) 会直接抛 NullPointerException），用"禁止歧义输入"换来"返回值可以放心用 null 判空"。LinkedList 因为同时要满足 List 接口（List 本身允许存 null，ArrayList 也可以存 null），所以没有这个限制，但代价就是它自己的 peek()/poll() 语义上其实存在这种歧义，只是大多数业务场景不会真的往队列里塞 null，这个隐患平时不容易被注意到。

Q3：用**ListIterator**遍历**LinkedList**并调用**Iterator.remove()**，为什么是真正的 O(1)，而不是"先 O(n) 找到再 O(1) 删"？

A：区别在于这个节点的引用是不是已经在手上。ListIterator 内部会维护一个指向"当前节点"的引用（Node<E> lastReturned），每调用一次 next()，这个引用就沿着链表往前走一步——这个"走"的过程本身摊到了整个遍历过程中，是遍历本来就要付的代价，不是额外发生的定位开销。当你调用 iterator.remove() 时，迭代器直接用手里已经持有的 lastReturned 节点引用去改前后指针，不需要再调用**node(index)**重新从头/尾定位。而如果你写的是 list.remove(index)，即便你心里知道大概是遍历到的第几个位置，代码本身并不知道"你刚刚已经走到这里了"，它必须重新调用 node(index)，从头或尾重新走一遍。这就是为什么本文强调"LinkedList 真正的优势场景是配合 Iterator 边遍历边操作"——省下来的正是这次重复定位。

Q4：文章说 LinkedList 每个节点有额外的指针开销，具体多出来大概多少内存？值得在意吗？

A：粗略估算：一个 Node 对象包含对象头（开启指针压缩的 64 位 JVM 下通常 12 字节，按 8 字节对齐可能补齐到 16 字节）、item/next/prev 三个引用字段（指针压缩后每个 4 字节，共 12 字节），加起来一个空节点大约 28-32 字节，这还没算 item 实际指向的数据对象本身的开销。相比之下 ArrayList/ArrayDeque 里同样一个引用类型元素只占数组里的 4 字节（指针压缩后）一个槽位。也就是说存储同样数量的引用类型元素，LinkedList 的额外开销大概是每个元素多花 24-28 字节——如果存的是一两百个元素，这点开销完全不值得纠结；但如果是百万级元素的长期缓存或者内存敏感的场景（比如内存受限的容器化环境），这个差距会被放大到 MB 级别，是否在意取决于这个列表的规模和生命周期，不是一个"绝对该不该用"的问题，而是要算一下账。

Q5：为什么 ConcurrentLinkedQueue 是无锁的，而 LinkedBlockingQueue 需要阻塞，两者的链表结构有什么不同？

A：两者都是基于链表实现，但解决的问题不同。ConcurrentLinkedQueue 追求的是"无锁并发安全"，内部用 CAS（Compare-And-Swap）操作配合 volatile 字段来保证多线程 offer/poll 时不会破坏链表结构，代价是操作失败时需要自旋重试，没有锁但也没有"排队等待"这种语义——如果队列空了，poll() 立刻返回 null，不会阻塞。LinkedBlockingQueue 则是显式用 ReentrantLock（内部分别为 put 端和 take 端维护两个锁，允许生产者和消费者并发操作而不互相阻塞）加上 Condition 实现"队列满了就阻塞生产者、队列空了就阻塞消费者"这种生产者-消费者模型，天然适合需要"等待直到有数据"或者"限流"的场景。选型上：只是无锁地并发读写、不需要等待语义 → ConcurrentLinkedQueue；需要生产者-消费者模型、需要阻塞等待 → LinkedBlockingQueue。

Q6：**node(index)**里"从更近的一端开始遍历"这个优化，为什么只是把常数系数减半，而不能真正改变时间复杂度？

A：因为这个优化解决的是"从哪一端出发"的问题，不是"怎么定位"的问题。无论从头还是从尾出发，链表本身都不支持地址算术，唯一的定位手段永远是"沿着指针一步步走"，每走一步的代价是 O(1)，但总共要走的步数仍然和 index 到最近一端的距离成正比——这个距离最坏情况下是 size / 2（正好在中间的位置），依然是和 size 成正比的量级，也就是 O(n)，只是这里的 n 系数从"最坏情况下遍历几乎整个链表"变成了"最坏情况下遍历半个链表"。时间复杂度描述的是随规模增长的渐进趋势，减半只改变了常数因子（在数学记号上会被吸收进大 O 的常数项里），不改变"随 size 线性增长"这个本质趋势，所以严格来说 node(index) 依然是 O(n)，这个优化只是让实际运行速度更快，而不是从根本上突破了链表结构本身的限制。

Q7：手写 LRU 缓存时用 LinkedList 实现双向链表部分，和直接用 LinkedHashMap 相比，踩坑点分别在哪？

A：如果自己拿 LinkedList 手写 LRU 的双向链表部分，最容易踩的坑是——LinkedList 本身不支持"给定一个节点引用，O(1) 把它从当前位置删除并移动到链表头部"这种操作，因为它没有对外暴露内部 Node 的引用，你手里只有元素的值，删除一个已知值的节点仍然要走 remove(Object)，内部要先线性查找到这个值对应的位置，退化成 O(n)——这就完全违背了"访问一个元素后把它挪到最近使用位置"这个 O(1) 更新的初衷。正确的手写做法是自己定义一个持有 prev/next 指针的 Node 类，配合一个 HashMap<Key, Node> 存"值到节点引用"的映射，这样访问、删除、移动都能借助拿到的节点引用做到真正的 O(1)——这正是 LinkedHashMap（设置 accessOrder=true）内部的实现思路，它本质上就是"HashMap + 双向链表"的组合，所以工程上实现 LRU 几乎总是直接用 LinkedHashMap 覆写 removeEldestEntry，而不是拿 java.util.LinkedList 现成的 API 去凑——LinkedList 的公开 API 从设计上就不是为"随机访问后立刻调整链表结构"这种场景优化的。

Q8：面试问"LinkedList 和 ArrayDeque 都能当队列用，你会选哪个"，怎么回答才不会显得只会背结论？

A：更有说服力的回答分三层：先说默认选择——单线程场景下当队列/栈用，默认选 ArrayDeque，因为它的循环数组结构在内存局部性和对象开销两方面都优于 LinkedList 的分散节点，这是 JDK 官方 Javadoc 明确给出的建议；再说例外条件——如果业务场景明确需要在队列里存 null 元素，或者需要用到 LinkedList 作为 List 接口的能力（比如 ListIterator 双向遍历、subList），这两种场景下 ArrayDeque 用不了或者用不顺手，才轮到 LinkedList；最后说验证方式——如果拿不准，应该用 profiler 或者简单的 JMH 基准测试实际跑一下两者在具体业务负载下的表现，而不是纯粹凭理论复杂度下结论，因为像"缓存局部性"这类因素理论时间复杂度是体现不出来的，真实性能差距往往比 Big-O 分析看到的更大。这种"默认选择 + 例外条件 + 如何验证"的三层回答，比单纯说"我选 ArrayDeque，因为官方推荐"更能体现出对底层原理的理解深度。