# 8. LinkedList 随机访问分析
# 标准答案
LinkedList
底层是 双向链表,不支持数组的 随机访问,获取元素时必须从头(或尾)开始遍历,直到找到目标索引。因此,get(index)
的时间复杂度是 O(n),相比 ArrayList
的 O(1) 随机访问,性能较差。如果 index
接近 头部或尾部,LinkedList
会选择从 较近的一端 遍历,优化访问性能,但仍然是线性复杂度。
# 答案解析
# JDK 18 源码解析
public E get(int index) {
checkElementIndex(index); // 检查索引是否越界
return node(index).item;
}
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
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LinkedList
采用 双向链表 结构,每个节点包含 prev
和 next
指针,没有索引映射关系,因此 无法 O(1) 访问任意位置元素,而是必须通过遍历找到对应节点。
# 时间复杂度分析
- 最佳情况:O(1),索引靠近
first
或last
时直接返回。 - 最坏情况:O(n),索引接近
size / 2
时,需要遍历n/2
个节点。 - 平均情况:O(n),查询
get(index)
平均遍历n/2
步。
示例:
LinkedList<Integer> list = new LinkedList<>(List.of(1, 2, 3, 4, 5));
list.get(3); // 从尾部遍历更快
1
2
2
链表结构如下:
[1] <-> [2] <-> [3] <-> [4] <-> [5]
1
get(0)
:O(1),直接返回first.item
。get(3)
:O(2),索引3 > size/2=2.5
,从last
向前遍历两步。get(2)
:O(2),索引2 < size/2=2.5
,从first
向后遍历两步。
# 为什么 LinkedList.get(index)
不能做到 O(1)?
- 底层是链表,无法直接索引
ArrayList
通过array[index]
直接访问元素,而LinkedList
只能 遍历链表 逐个访问节点。 - 不适合缓存索引
LinkedList
设计为 动态插入删除 友好,若增加索引缓存,会增加插入删除成本。 - 没有哈希索引优化
例如TreeMap
通过 红黑树 结构加速查询,但LinkedList
只提供顺序访问。
# 如何优化 LinkedList.get(index)
性能?
- 避免
LinkedList
频繁get(index)
,若需频繁查询,使用ArrayList
替代。 - 使用
ListIterator
,可减少重复遍历:ListIterator<Integer> it = linkedList.listIterator(); for (int i = 0; i < targetIndex; i++) { it.next(); } Integer value = it.next(); // 仅遍历一次
1
2
3
4
5 - 转换为
ArrayList
进行查询,若数据量较大,查询密集,可转为ArrayList
:转换成本 O(n),但后续查询 O(1)。List<Integer> list = new ArrayList<>(linkedList); Integer value = list.get(index); // O(1)
1
2
# 适用场景对比
场景 | ArrayList | LinkedList |
---|---|---|
随机访问 (get(index) ) | ✅ O(1) | ❌ O(n) |
头部插入删除 | ❌ O(n) | ✅ O(1) |
尾部插入删除 | ✅ O(1) | ✅ O(1) |
大量插入删除 | ❌ 需要移动元素 | ✅ 只需修改指针 |
迭代遍历 | ✅ 快,CPU 缓存友好 | ❌ 需频繁跳指针 |
# 深入追问
- 为什么
LinkedList.get(index)
不能使用哈希表加速?
LinkedList
是 有序结构,不支持哈希索引。如果维护哈希索引,会导致 插入删除操作额外维护索引,影响插入性能。 LinkedList.get(index)
为何不缓存中间结果?
LinkedList
设计为 流式(stream-like)数据结构,没有 索引缓存,但ListIterator
能减少重复遍历,建议替代get(index)
。- 为什么
LinkedList
从first
或last
遍历?- 降低平均遍历步数:从
first
或last
遍历 最多 O(n/2) 次,而不是O(n)
。 - 如果总是从
first
遍历,get(size-1)
变为 O(n),效率更低。
- 降低平均遍历步数:从
# 相关面试题
- 为什么
ArrayList.get(index)
是 O(1),LinkedList.get(index)
是 O(n)? LinkedList.get(index)
能优化到 O(1) 吗?为什么?- 什么时候应当使用
LinkedList
而不是ArrayList
? LinkedList
为什么不适用于频繁get(index)
访问?LinkedList
的iterator
和get(index)
有何区别?