# 问题
3. LinkedList 的数据结构是什么?为什么它适用于插入操作频繁的场景?
# 标准答案
LinkedList
是 双向链表(Doubly Linked List),底层由 Node<E>
结点组成,每个结点包含 数据(item)、前驱指针(prev)、后继指针(next)。由于链表插入和删除元素时只需修改指针,不需要移动大量元素,因此在 插入和删除操作频繁 的场景下,比 ArrayList
更高效。但由于 链表不支持随机访问(O(n) 查找),访问远距离元素性能较差,所以不适用于频繁查找的场景。
# 答案解析
# 1. LinkedList 的底层数据结构
LinkedList
采用 双向链表 结构,每个元素封装在 Node<E>
结点中,结点定义如下(JDK 1.8):
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
11
2
3
4
5
6
7
8
9
10
11
整个 LinkedList
通过 first
和 last
指针维护链表的 头结点 和 尾结点:
transient Node<E> first; // 头结点
transient Node<E> last; // 尾结点
1
2
2
- 双向链表特点:
- 插入、删除操作 O(1),仅需调整指针,无需大规模数据移动。
- 查找操作 O(n),需从
first
或last
依次遍历,无法像ArrayList
一样通过O(1) 索引访问
。
# 2. 为什么 LinkedList 适用于插入操作频繁的场景?
# (1)插入元素的性能优势
- 在
ArrayList
中,插入元素时如果发生 数组扩容或中间插入,需要 O(n) 级别的元素移动,性能较差。 LinkedList
只需 修改前后指针,插入 O(1),适合 频繁插入 的场景。
插入操作示例(add(E e)
方法):
public boolean add(E e) {
linkLast(e); // 插入到链表尾部
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
- 头部插入:调整
first
指针。 - 尾部插入:调整
last
指针。 - 中间插入:修改前后
prev/next
指针,避免ArrayList
的数据搬移。
# (2)删除元素的性能优势
ArrayList
删除元素需要 O(n) 级别的移动,影响性能。LinkedList
删除仅需 修改前后指针,时间复杂度为 O(1)。
删除操作示例(remove(E e)
方法):
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;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- 只需修改
prev
和next
指针,无需移动数据,避免ArrayList
的大量System.arraycopy()
调用。 - 适用于 链表队列、缓存淘汰(LRU)、频繁删除的场景。
# 3. LinkedList 的缺点
# (1)查询性能较差(O(n)
ArrayList
通过 数组索引 O(1) 访问 元素,而LinkedList
需要 从头结点或尾结点遍历,平均时间复杂度 O(n)。- 示例:查找第 5000 个元素时:
ArrayList
:list.get(5000)
直接访问,O(1)。LinkedList
:需要从first
或last
遍历,O(n) 级别,查询性能远低于ArrayList
。
# (2)空间开销大
LinkedList
需要额外存储 prev / next 指针,每个结点的存储成本比ArrayList
高。- 示例:存储 100w 个
Integer
数据:ArrayList
:只需100w * 4B = 4MB
(连续存储)。LinkedList
:需要额外指针,空间开销 至少 2-3 倍。
# (3)CPU 缓存命中率低
ArrayList
元素存储在连续内存地址,CPU 预读取数据块,缓存利用率高。LinkedList
元素分散存储,导致 Cache Miss(缓存未命中),CPU 读取数据变慢。
# 最佳实践
适用于插入/删除频繁的场景
- 消息队列(如
LinkedBlockingQueue
) - 缓存淘汰策略(LRU)(如
LinkedHashMap
) - 链表结构的
HashMap
桶(JDK 1.7 以前)
- 消息队列(如
避免在索引访问频繁的场景使用
- 避免
get(int index)
访问远距离元素 - 若需要 频繁随机访问,请使用
ArrayList
。
- 避免
# 深入追问
# 1. 为什么 LinkedList
适用于 LRU
缓存?
LinkedHashMap
继承自HashMap
,但维护了一个 双向链表,结合removeEldestEntry()
方法,可以高效淘汰最近最少使用的数据(LRU 机制)。
# 2. 为什么 LinkedList
在 for-each
迭代时比 ArrayList
慢?
for-each
本质上会调用iterator.next()
,而LinkedList
需要 从前驱结点依次遍历,远比ArrayList
直接索引访问慢。
# 3. LinkedList
为什么不适合作为 ArrayList
的底层?
ArrayList
需要随机访问元素,而LinkedList
只能顺序遍历,这与ArrayList
设计理念不符。
# 相关面试题
LinkedList
和ArrayList
的性能对比?LinkedList
在 JVM 内存管理上的影响?LinkedList
适合哪些实际业务场景?LinkedList
和ConcurrentLinkedQueue
的区别?