跳到主要内容
约 7 分钟2 张卡

LinkedList

LinkedList 是用双向链表实现的列表,同时实现了 List 和 Deque(双端队列)两个接口。它的成本特点可以归结为一句话:找到位置要沿链一个个走,是 O(n);找到之后改链接,是 O(1)。「链表插入是 O(1)」只说了后半句,按索引插入时还要先付定位的成本。分析 LinkedList 的题目,关键就是把定位和修改分开算,再加上节点分配和缓存不友好带来的实际开销。下文以 OpenJDK 21 为准。

1. 面试核心​

先记住这几条,再读正文
  • LinkedList 同时实现 List 和 Deque,每个元素对应一个保存前后引用的节点。
  • 按索引访问是 O(n);循环调用 get(i) 遍历整个列表,总成本是 O(n²)。卡 · 按索引访问
  • 在已经定位的迭代器处增删节点是 O(1),按索引增删还要加上 O(n) 的定位成本。卡 · 按索引访问
  • 首尾操作是 O(1),但每新增一个元素都要分配一个节点。
  • ListIterator.add 在游标前插入新元素,之后立即调用 previous 返回的就是这个新元素。卡 · ListIterator 的游标位置

2. 链表节点​

双向链表用前后两个引用把节点串起来,所以从哪一端都能开始走。每个节点保存三个引用:

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

列表对象本身还保存首节点、尾节点和元素数量。每个节点是单独分配的对象,在堆里可能相隔很远,遍历时要先读出引用,再跳到它指向的下一个节点:

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

对比 ArrayList:ArrayList 把元素引用连续存放在一个数组里,LinkedList 却要为每个元素多分配一个节点对象,这个对象除了元素引用,还有对象头和两个链接引用。所以存同样多的元素,LinkedList 占的内存更多,垃圾收集器(GC)要跟踪的对象也更多。

3. 按索引访问​

链表没有下标,按索引访问只能从一端沿链接走到对应的节点。比如下面这次调用,要先找到第 index 个节点,再返回里面的用户:

User user = linkedUsers.get(index);

实现会先判断 index 离头近还是离尾近,再从近的一端一个个往前走,最坏要走 n/2 步,成本是 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)。

即使都是 O(n),链表遍历实际上也比数组慢。节点分散在堆里,每跳一次都要读一个新的内存位置,CPU 缓存很难提前把下一个节点加载好,更容易发生缓存未命中。

4. 插入与定位成本​

链表插入的成本要拆成两部分算:找到位置,和修改链接。修改链接只需要创建新节点、改相邻节点的前后引用,是 O(1)。但按索引调用 add 时,要先花 O(n) 找到位置,所以总成本还是 O(n):

linkedUsers.add(index, user);

要真正拿到 O(1) 的插入,就得复用已经找到的位置。ListIterator 会记住当前遍历到的位置,这个位置叫游标。边遍历边在游标处编辑,就不用每次重新定位:

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

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

遍历到 marker 后,iterator.add 直接在它后面插入 inserted,没有再按索引查找一次。整个过程只走一遍链表。

换成 ArrayList,中间插入要把后面的引用整体往后挪,看起来是 O(n),但连续数组可以批量复制,元素不多或插入不频繁时其实很快。所以比较两者时,要同时考虑定位了几次、数据量多大,以及 LinkedList 每次分配节点的成本。

4.1 ListIterator 的游标位置​

要判断 add 之后 next 和 previous 返回什么,得把游标理解成两个元素之间的位置,而不是指向某个元素。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]

listIterator(1) 让游标一开始停在 A 和 B 之间。加入 X 后,游标移到 X 和 B 之间,所以 next 返回 B,列表变成 [A, X, B]。

成本也要分开看:listIterator(1) 这一步要沿链定位,之后的 add 只改相邻链接。所以只有复用同一个迭代器才能省掉重复定位;如果每次都按索引新建迭代器,定位成本一次也省不掉。

5. Deque 两端操作​

LinkedList 一直保存着首尾节点,所以在两端增删不需要定位,成本是 O(1)。通过 Deque 接口,可以从尾部放入任务、从头部取出:

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

addLast 和 pollFirst 都只碰端点。不过普通的单线程栈、队列或广度优先搜索(BFS),更适合先考虑 ArrayDeque,它用的是循环数组:

  • 引用连续存放在数组里,不用为每个元素分配节点。
  • 顺序读取能更好地利用 CPU 缓存,不用沿链接跳转。
  • 两端增删复用数组槽位,容量不够时才扩容。

两者还有一个区别:LinkedList 允许 null 元素,ArrayDeque 不允许。poll 在队列为空时返回 null,如果队列里本来就可能有 null,就分不清是取到了空任务还是队列空了。所以即使用 LinkedList,也最好只放非空元素。

6. 适用场景​

选不选 LinkedList,取决于具体怎么访问它。可以按下面的操作需求与成本判断:

  • 必须用标准 List API,并且持有 ListIterator 连续做局部编辑时,能用上 O(1) 的节点增删。
  • 必须允许 null 元素、又确实需要两端操作时,可以考虑 LinkedList,但要想清楚怎么区分 null 元素和队列为空。
  • 频繁按索引随机访问时,每次定位的 O(n) 会把改链接省下的成本全吃掉。
  • 元素很多、对堆占用、GC 或缓存效率敏感时,要实际测量节点分配和指针跳转的代价。

所以一般的列表先从 ArrayList 开始考虑,栈、队列和 BFS 先从 ArrayDeque 开始考虑。只有局部编辑的模式很明确,而且按实际数据规模做的基准测试也支持时,才选 LinkedList。

如果算法需要直接持有或移动节点,比如手写 LRU 时要把某个节点挪到链尾,标准 LinkedList 不暴露节点对象,就做不到。这类需求要用专门的数据结构,避免每次都通过索引去找节点。

7. 常见问题​

7.1 插入位置与复杂度​

已经有迭代位置时,局部插入是 O(1),只需要创建节点、调整相邻链接。按索引插入还要先花 O(n) 定位,所以要把定位和修改分开算。首尾两个位置可以直接拿到,是 O(1) 的特例。

7.2 Deque 实现的选择​

7.3 游标编辑与并发修改​

7.4 节点删除与内存回收​

8. 面试题卡片​

先想答案,再翻面先在心里答一遍,再点开卡片对照参考回答。卡片之间可以左右切换,看完会回到这里。
逐张翻看 2 张 →
未标记的卡读完后明天进入复习;已标记的按状态安排

9. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明