# 6. ArrayList 和 LinkedList 在遍历时的性能有什么区别?适用于哪些场景?
# 标准答案
ArrayList
采用动态数组,支持基于索引的 O(1) 随机访问,因此顺序遍历性能极高。而 LinkedList
采用双向链表,随机访问需要 O(n) 时间复杂度,导致遍历性能较差。
在 大规模数据遍历场景 下,ArrayList
比 LinkedList
更高效,适用于 读取频繁、查询为主 的业务(如缓存、商品列表)。而 LinkedList
更适用于插入和删除频繁,但数据量较小的场景,如 任务队列、双向链表结构的数据处理。
# 答案解析
# 1. ArrayList 和 LinkedList 的遍历方式
# (1)ArrayList:基于索引遍历(O(1))
ArrayList
采用连续内存存储,支持随机访问:
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)); // O(1)
}
1
2
3
2
3
list.get(i)
时间复杂度 O(1),直接通过 index 访问,访问速度快。- CPU 缓存友好,数据存储在连续地址,能充分利用 CPU 缓存预取(Cache Prefetching) 提高访问速度。
# (2)LinkedList:基于指针查找(O(n))
LinkedList
采用双向链表,每次 get(i)
需要从头(或尾)遍历到索引位置:
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)); // O(n)
}
1
2
3
2
3
list.get(i)
时间复杂度 O(n),因为它必须从头(或尾)开始逐个遍历,直到找到索引位置。- 不连续存储,CPU 缓存命中率低,无法利用 CPU 预取优化,遍历速度慢。
# 2. 遍历性能对比
假设 n = 100000
,测试 ArrayList
和 LinkedList
的遍历性能:
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < n; i++) {
arrayList.add(i);
linkedList.add(i);
}
// 遍历 ArrayList
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.get(i);
}
System.out.println("ArrayList 遍历时间: " + (System.nanoTime() - start));
// 遍历 LinkedList
start = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.get(i);
}
System.out.println("LinkedList 遍历时间: " + (System.nanoTime() - start));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
在实际测试中:
遍历方式 | ArrayList | LinkedList |
---|---|---|
for (i) | 快(O(1)) | 极慢(O(n)) |
for-each | 快(迭代器优化) | 较快(迭代器避免随机访问) |
Iterator | 快 | 较快 |
# 3. 如何优化 LinkedList
的遍历?
# (1)避免 for (i)
索引遍历
错误写法(O(n²)):
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i); // 每次都重新从头部查找,O(n)
}
1
2
3
2
3
优化:使用迭代器(O(n))
for (Integer value : linkedList) {
System.out.println(value);
}
1
2
3
2
3
- Iterator 内部维护指针,避免重复查找,访问时间 O(n)。
# (2)使用 ListIterator
避免双向查找
ListIterator<Integer> iterator = linkedList.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
1
2
3
4
2
3
4
- 支持双向遍历,更适合
LinkedList
。
# 4. 适用场景对比
适用场景 | ArrayList (推荐) | LinkedList |
---|---|---|
查询频繁 | ✅ 快(O(1)) | ❌ 慢(O(n)) |
插入/删除 | ❌ 慢(O(n) 移动数据) | ✅ 快(O(1) 插入/删除) |
顺序遍历 | ✅ CPU 预取优化 | ❌ CPU 缓存不友好 |
随机访问 | ✅ O(1) | ❌ O(n) |
大数据集合 | ✅ 推荐 | ❌ 不推荐 |
任务队列 | ❌ 不适合 | ✅ 适合(头部插入删除快) |
# 深入追问
# 1. 为什么 ArrayList
遍历时性能比 LinkedList
高?
- 顺序访问时,
ArrayList
数据存储在连续内存,CPU 可以提前加载(Cache Prefetching),极大提高访问速度。 LinkedList
遍历时,每次get(i)
都需要从头部/尾部遍历,导致 时间复杂度 O(n),性能急剧下降。
# 2. LinkedList
是否有场景适用?
LinkedList
适合:
- 插入和删除频繁的场景(如双向链表结构的任务队列)。
- 不关注索引访问,而是只用迭代器遍历的场景。
# 3. ArrayList
在高并发下是否安全?如何优化?
ArrayList
不是线程安全的,可以用Collections.synchronizedList()
或CopyOnWriteArrayList
。- 如果并发写入较多,
CopyOnWriteArrayList
避免锁竞争,适合读多写少的场景。
# 相关面试题
ArrayList
为什么查询快但插入慢?LinkedList
为什么插入快但查询慢?CopyOnWriteArrayList
如何优化并发读写?- 如何用
ArrayList
实现LRU 缓存
?