# 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
  • 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
  • list.get(i) 时间复杂度 O(n),因为它必须从头(或尾)开始逐个遍历,直到找到索引位置。
  • 不连续存储,CPU 缓存命中率低,无法利用 CPU 预取优化,遍历速度慢。

# 2. 遍历性能对比

假设 n = 100000,测试 ArrayListLinkedList 的遍历性能:

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

在实际测试中:

遍历方式 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

优化:使用迭代器(O(n))

for (Integer value : linkedList) {
    System.out.println(value);
}
1
2
3
  • Iterator 内部维护指针避免重复查找,访问时间 O(n)。
# (2)使用 ListIterator 避免双向查找
ListIterator<Integer> iterator = linkedList.listIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
1
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 缓存