# 15. LinkedList 如何优化插入删除操作的指针操作?
# 标准答案
LinkedList
作为双向链表,在插入和删除时主要依赖指针操作。为了提高效率,它会在头尾快速插入(O(1)),并在中间插入时根据 index 判断从头还是尾遍历,尽量减少遍历次数(O(n))。此外,JDK 采用 懒删除策略,即删除节点时,仅调整前后指针,而不立刻清除对象引用,交由 GC 处理,从而降低操作开销。
# 答案解析
# 1. LinkedList 的指针结构
LinkedList
是双向链表,每个节点 (Node<E>
) 由 item
(存储数据)、next
(指向下一个节点)、prev
(指向前一个节点)组成。
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;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- 插入时:只需改变前后节点的
next
和prev
指针,不涉及大规模数据移动。 - 删除时:仅调整指针,不真正清理数据,降低 GC 压力(懒删除)。
# 2. 插入操作的优化
(1)尾部 / 头部插入(O(1))
- 直接修改
first
或last
指针,无需遍历。 - 代码示例(
addFirst()
):private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; }
1
2
3
4
5
6
7
8
9
10
(2)中间插入(O(n))
- 先根据
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; } }
1
2
3
4
5
6
7
8
9
10
11
12
13 - 减少遍历时间:如果
size = 1000
,查询index = 900
,从尾部遍历只需 100 次,比从头遍历(900 次)快 9 倍。
(3)插入新节点
- 常规链表插入:
private void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; }
1
2
3
4
5
6
7
8
9
10 - 优化点:
- 只操作局部指针,无需像
ArrayList
那样移动整个数组,提升性能。 - 若
index
过大,可调整存储策略(如Skip List
提高索引效率)。
- 只操作局部指针,无需像
# 3. 删除操作的优化
(1)懒删除策略
LinkedList
删除时,不立即释放对象,而是仅调整指针,等待 GC 处理:private void unlink(Node<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) first = next; else prev.next = next; if (next == null) last = prev; else next.prev = prev; size--; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14- 为什么不立即清除
x.item
?- 立即清除会增加
GC
负担,短时间内可能触发频繁回收。 - 延迟到
GC
触发时,批量清理,减少 Stop-The-World 影响。
- 立即清除会增加
(2)头部 / 尾部删除(O(1))
- 直接调整
first
/last
指针,效率极高:private void unlinkFirst(Node<E> f) { final Node<E> next = f.next; first = next; if (next == null) last = null; else next.prev = null; size--; }
1
2
3
4
5
6
7
8
9
# 4. 进一步优化
减少
index
访问开销- 改进策略:使用
TreeMap
+LinkedList
组合(如 LRU 缓存),提升查询速度。 - 示例:
private Map<Integer, Node<E>> indexMap = new TreeMap<>();
1 - 这样可以在 O(log n) 时间复杂度内获取
index
对应的Node
,避免O(n)
遍历。
- 改进策略:使用
合并多个删除请求
- 批量删除:减少链表操作次数,提高吞吐量。
- 示例:对于大量删除操作,采用
ArrayList
记录要删除的节点,统一处理:List<Node<E>> toDelete = new ArrayList<>(); for (Node<E> node : list) { if (shouldDelete(node)) { toDelete.add(node); } } for (Node<E> node : toDelete) { list.remove(node); }
1
2
3
4
5
6
7
8
9 - 优势:
- 减少频繁 GC:避免删除后立即回收,提高 GC 效率。
- 提高吞吐量:批量操作指针,降低 CPU 负担。
结合
Skip List
结构- 在高并发环境,可以用
ConcurrentSkipListMap
替代LinkedList
,提升随机访问效率。 - 例如 消息队列 或 缓存淘汰 场景。
- 在高并发环境,可以用
# 常见错误
- 误解
LinkedList
的删除是 O(1)- 正确: 头部、尾部删除是 O(1),但中间删除仍然需要 O(n) 遍历。
- 误认为
LinkedList
适用于所有插入场景- 正确: 仅在大量随机插入 / 删除时比
ArrayList
具有优势,但查询性能较低。
- 正确: 仅在大量随机插入 / 删除时比
# 最佳实践
- 批量操作时,提前计算
index
,减少遍历次数。 - 尽量避免
get(index)
,用Iterator
遍历,减少O(n)
遍历消耗。 - 高并发场景下,避免
LinkedList
,使用ConcurrentLinkedDeque
。
# 深入追问
LinkedList
在 JVM 内存管理上的表现如何?ArrayDeque
为什么比LinkedList
更适合作为队列?ConcurrentLinkedQueue
如何实现无锁链表?
# 相关面试题
- 为什么
LinkedList
适用于频繁插入删除,而ArrayList
适用于随机访问? LinkedList
和ConcurrentLinkedDeque
的区别是什么?