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)
}

• 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)
}

• 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));

在实际测试中：

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

优化：使用迭代器（O(n)）

for (Integer value : linkedList) {
    System.out.println(value);
}

• Iterator 内部维护指针，避免重复查找，访问时间 O(n)。

（2）使用 ListIterator 避免双向查找

ListIterator<Integer> iterator = linkedList.listIterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

• 支持双向遍历，更适合 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 缓存？