LinkedList

LinkedList 用双向链表实现 List 列表和 Deque 双端队列。本文以 OpenJDK 21 为准，先解释节点存储和按索引定位，再比较局部增删、首尾操作与内存成本。

1. 面试核心

先记住这几条，再读正文

• 节点结构。 LinkedList 同时实现 List 和 Deque，每个元素对应一个保存前后引用的链表节点。
• 索引与遍历成本。 LinkedList 按索引访问的成本为 O(n)，循环调用 get(i) 遍历整个列表的成本为 O(n²)。卡 · 按索引访问
• 定位与局部编辑。 LinkedList 在已定位的迭代器处增删节点为 O(1)，按索引编辑则还要计入 O(n) 的定位成本。卡 · 按索引访问
• 首尾操作。 LinkedList 的首尾操作为 O(1)，每次新增元素需分配节点。
• 迭代器游标。 ListIterator.add 在游标前插入新元素，随后立即调用 previous 会返回这个新元素。卡 · ListIterator 的游标位置

2. 链表节点

双向链表通过前后引用把节点连接起来，因此可以从两端开始移动。每个节点保存以下三个引用：

• 元素引用指向当前节点保存的对象。
• 前驱引用指向前一个节点。
• 后继引用指向后一个节点。

列表本身还保存首尾节点和元素数量。各节点单独分配，在堆中可以相距很远，所以遍历时要读取引用，再访问它指向的下一个节点：

first                                        last
  ↓                                            ↓
[prev|null, A, next] ⇄ [prev, B, next] ⇄ [prev, C, next|null]

相比 ArrayList 的连续引用数组，LinkedList 为每个元素额外分配一个节点。节点除了元素引用，还有对象头和两个链接引用。因此，同样多的元素需要更多内存，垃圾收集器（GC）也要跟踪更多对象。

3. 按索引访问

必会卡 · ArrayList 与 LinkedList 的插入、查询和遍历成本有什么不同

LinkedList 需要沿链接找到索引对应的节点。比如，下面的调用先定位节点，再返回其中保存的用户：

User user = linkedUsers.get(index);

实现会判断 index 更接近头还是尾，再从较近的一端逐个移动，最坏成本为 O(n)。遍历整个列表时，可以对比下面两种访问方式，实际使用时选择其中一种：

// 按索引遍历
for (int i = 0; i < linkedUsers.size(); i++) {
    consume(linkedUsers.get(i));
}

// 使用迭代器遍历
for (User user : linkedUsers) {
    consume(user);
}

• 按索引遍历时，每次 get(i) 都重新定位，把这些查找加起来，整体成本为 O(n²)。
• 增强 for 使用的迭代器会记住当前节点，只沿链移动一次，遍历成本为 O(n)。

不过，节点分散时，每次跳转都需要读取新的内存位置，更容易发生 CPU 缓存未命中。因此，即使和数组遍历同为 O(n)，链表也会有更高的实际访问成本。

4. 插入与定位成本

必会卡 · ArrayList 与 LinkedList 的插入、查询和遍历成本有什么不同

分析插入性能时，要分别计算定位和修改链接的成本。已经定位后，插入只需创建新节点并调整相邻链接，局部修改为 O(1)。但按索引调用 add 时，需要先 O(n) 定位，所以总成本仍为 O(n)：

linkedUsers.add(index, user);

ListIterator 会保存当前遍历位置，这个位置称为游标。在游标处连续编辑时，就能复用已经找到的位置，例如：

ListIterator<String> iterator = values.listIterator();

while (iterator.hasNext()) {
    if (iterator.next().equals("marker")) {
        iterator.add("inserted");
    }
}

示例遇到 marker 后，直接在它后面插入 inserted，省去再次按索引查找的过程。

ArrayList 中间插入需要搬移后续引用，但连续数组可以批量复制。元素较少或插入不频繁时，这种复制也很高效。所以，比较两者时，要同时考虑定位次数、数据量和节点分配成本。

5. Deque 两端操作

必会卡 · ArrayList 与 LinkedList 的插入、查询和遍历成本有什么不同

列表已经保存首尾节点，所以 LinkedList 可以直接在两端增删，成本为 O(1)。通过 Deque 接口，可以从尾部加入任务，再从头部取出：

Deque<Job> jobs = new LinkedList<>();
jobs.addLast(job);
Job next = jobs.pollFirst();

示例中的 addLast 与 pollFirst 都只访问端点。对普通单线程栈、队列或 BFS 广度优先搜索，可以先考虑 ArrayDeque，它的循环数组有以下特点：

• 数组中的引用连续存放，无需为每个元素分配节点。
• 顺序读取可以更好地利用 CPU 缓存，减少沿链接跳转。
• 两端增删可以复用数组槽，容量不足时再扩容。

LinkedList 允许 null，ArrayDeque 拒绝 null。由于 poll 用 null 表示队列为空，使用非空任务值可以避免把空任务和队空混淆。

6. 适用场景

选择 LinkedList 的依据是具体访问方式。可以结合以下操作需求与成本判断：

• 必须使用标准 List API，并持有 ListIterator 连续进行局部编辑时，可以利用 O(1) 的节点增删。
• 必须允许 null，且确实需要两端操作时，可以考虑 LinkedList，但要明确 null 与队空的区分方式。
• 频繁按索引随机访问时，反复定位会抵消修改链接的优势。
• 元素很多且对堆占用、GC 或缓存效率敏感时，需要测量节点分配和跳转的代价。

因此，一般列表可从 ArrayList 开始比较，普通栈、队列和 BFS 可从 ArrayDeque 开始。只有局部编辑模式明确，并且实际数据规模和基准测量支持时，再选择 LinkedList。

如果算法需要直接持有或移动节点，标准 LinkedList 隐藏的节点对象就难以满足要求。这类需求可以使用专门的数据结构，避免反复通过索引查找节点。

7. ListIterator 的游标位置

必会卡 · ListIterator.add 后，next 返回新元素还是原后继？

要判断插入后返回哪个元素，需要把游标理解为两个元素之间的位置。add 在游标前插入，插入后游标位于新元素与原后继之间。因此，随后调用 next 仍返回原后继；若立即调用 previous，则返回新元素。

var values = new LinkedList<>(List.of("A", "B"));
var it = values.listIterator(1);
it.add("X");
System.out.println(it.next()); // B
System.out.println(values);   // [A, X, B]

示例中，游标原本在 A 与 B 之间。加入 X 后，它位于 X 与 B 之间，所以 next 返回 B，最终列表为 [A, X, B]。

初始定位需要遍历节点，随后 add 只修改相邻链接。因此，复用迭代器才能省去重复定位；反复按索引创建迭代器，仍要反复承担查找成本。

8. 常见问题

8.1 插入位置与复杂度

已有迭代位置时，局部插入为 O(1)，因为只需创建节点并调整相邻链接。按索引插入还需 O(n) 定位，所以应将定位和修改分开计算。首尾位置可以直接取得，是 O(1) 的特例。

8.2 Deque 实现的选择

8.3 游标编辑与并发修改

8.4 节点删除与内存回收

9 · 面试题卡片

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。

逐张翻看 2 张 →

按索引访问必会

ArrayList 与 LinkedList 的插入、查询和遍历成本有什么不同

美团字节跳动阿里巴巴

考察 3 点 · 相关 §3 §4 §5

ListIterator 的游标位置必会

ListIterator.add 后，next 返回新元素还是原后继？

本站自测

考察 1 点 · 相关 §7

9.1 ArrayList 与 LinkedList 的插入、查询和遍历成本有什么不同

出现公司：美团、字节跳动、阿里巴巴

考察重点

• 说明链表定位与节点修改需要分别计算。
• 说明大 O 相同的遍历为何仍有实际性能差异。
• 说明队列场景为什么通常选择 ArrayDeque。

相关内容：按索引访问、插入与定位成本、作为 Deque 使用。

参考回答

ArrayList 擅长索引访问和尾部追加；LinkedList 的 O(1) 增删要求操作位置已经定位。

• 按索引查询：ArrayList 为 O(1)，LinkedList 为 O(n)。 后者需要沿链查找。
• 插入与删除：成本取决于位置。 ArrayList 中间增删需要搬移后续引用，尾部追加摊销 O(1)；LinkedList 已定位游标的增删为 O(1)，寻找位置的成本另算。
• 遍历：迭代器均为 O(n)。 LinkedList 需要逐个节点跳转，循环调用 get(i) 则会退化为 O(n²)。

普通列表可先考虑 ArrayList，栈和队列可先考虑 ArrayDeque。LinkedList 更适合有明确局部编辑模式、且测量结果支持的场景。

9.2 ListIterator.add 后，next 返回新元素还是原后继？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：解释插入前后游标的位置，并区分初始定位与局部增删的成本。

相关内容：ListIterator 的游标位置。

参考回答

next 返回原后继，因为 add 把新元素放在游标前，游标仍在原后继之前。

如果插入后立即调用 previous，则会返回新元素。LinkedList 在已定位的游标处 add 为 O(1)，初始定位的成本需要另计。

10. 参考资料

• Java API：LinkedList
• OpenJDK：LinkedList 源码
• Java API：ArrayDeque
• Java API：ListIterator