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,取决于具体怎么访问它。可以按下面的操作需求与成本判断:
- 必须用标准
ListAPI,并且持有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 实现的选择
单线程的栈和队列先选 ArrayDeque,循环数组省掉了节点分配和指针跳转。都实现了 Deque 接口,不代表内存和访问成本一样。
需要跨线程传递任务并等待队列状态时,见 BlockingQueue。
7.3 游标编辑与并发修改
当前线程可以通过迭代器自己的 remove、add 等方法编辑列表,这不会造成冲突。绕过迭代器直接调用列表的结构修改方法,或者有其他线程在修改,遍历就会出问题。fail-fast 机制只是尽力发现这类错误,不保证一定能发现,跨线程修改仍然需要同步。
7.4 节点删除与内存回收
删除元素时,LinkedList 会断开节点链接,并清空节点里保存的引用。但节点和元素要等到没有其他强引用之后才符合 GC 的回收条件,什么时候真正回收由垃圾收集器决定。所以删除元素不会立刻把内存还给操作系统。
8. 面试题卡片
9. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明