ArrayList vs LinkedList：一张表说清楚
核心区别
ArrayList = 数组，连续内存
→ 随机访问快（O(1)），中间增删慢（O(n)）
LinkedList = 双向链表，分散内存
→ 随机访问慢（O(n)），头尾操作快（O(1)）性能对比表
| 操作 | ArrayList | LinkedList | 胜者 |
|---|---|---|---|
随机访问 get(i) | O(1) | O(n) | ArrayList |
尾部添加 add(e) | O(1) 均摊 | O(1) | 平手 |
头部插入 addFirst() | O(n) | O(1) | LinkedList |
中间插入 add(i, e) | O(n) | O(n) | 平手 |
按索引删除 remove(i) | O(n) | O(n) | 平手 |
迭代器删除 it.remove() | O(n) | O(1) | LinkedList |
| 遍历（迭代器/forEach） | 快 | 更快 | LinkedList |
| 内存占用 | 低 | 高 | ArrayList |
| CPU 缓存 | 友好 | 不友好 | ArrayList |
图解：内存结构差异
ArrayList（连续内存）：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │ H │ ...
└───┴───┴───┴───┴───┴───┴───┴───┘
│ ← CPU 一次读一块，缓存命中率高
LinkedList（分散内存）：
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ A │───▶│ B │───▶│ C │───▶│ D │───▶ ...
└────┘ └────┘ └────┘ └────┘
↑ ↑ ↑
每次访问都要去内存里找下一个节点实战选择：5 个场景
场景 1：按索引随机访问
java
// ✅ ArrayList
List<Record> records = new ArrayList<>(db.queryAll());
for (int i = 0; i < records.size(); i++) {
process(records.get(i)); // O(1)，极快
}
// ❌ LinkedList
List<Record> linked = new LinkedList<>(db.queryAll());
for (int i = 0; i < linked.size(); i++) {
process(linked.get(i)); // O(n)，极慢
}场景 2：只尾部追加
java
// ✅ 两者都可以，ArrayList 稍快
List<String> list = new ArrayList<>();
// 或
List<String> linked = new LinkedList<>();
for (String s : data) {
list.add(s); // 或 linked.add(s)
}场景 3：迭代器遍历时增删
java
// ✅ LinkedList
List<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));
Iterator<String> it = list.iterator();
while (it.hasNext()) {
if (it.next().equals("B")) {
it.remove(); // O(1)，极快
}
}
// ❌ ArrayList
List<String> array = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (int i = 0; i < array.size(); i++) {
if (array.get(i).equals("B")) {
array.remove(i); // O(n)，慢
i--; // 还要调整索引
}
}场景 4：双端队列操作
java
// ✅ ArrayDeque（最快）
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.pollFirst();
// ✅ LinkedList
Deque<Integer> linked = new LinkedList<>();
linked.addFirst(1);
linked.addLast(2);
// ❌ ArrayList（最慢）
List<Integer> array = new ArrayList<>();
array.add(0, 1); // O(n)，慢场景 5：批量数据处理后遍历
java
// ✅ ArrayList
List<Transaction> txns = db.fetchTransactions();
// 处理...
for (Transaction t : txns) { // 遍历快，CPU 缓存友好
process(t);
}性能实测
java
import java.util.*;
public class ListPerformanceTest {
public static void main(String[] args) {
int size = 100_000;
ArrayList<Integer> array = new ArrayList<>();
LinkedList<Integer> linked = new LinkedList<>();
for (int i = 0; i < size; i++) {
array.add(i);
linked.add(i);
}
// 1. 随机访问
System.out.println("随机访问 10 万次:");
System.out.println(" ArrayList: " + measure(() -> {
for (int i = 0; i < size; i++) array.get(i);
}));
System.out.println(" LinkedList: " + measure(() -> {
for (int i = 0; i < size; i++) linked.get(i);
}));
// 2. 迭代器遍历
System.out.println("迭代器遍历:");
System.out.println(" ArrayList: " + measure(() -> {
for (Integer i : array) { /* 消耗 */ }
}));
System.out.println(" LinkedList: " + measure(() -> {
for (Integer i : linked) { /* 消耗 */ }
}));
// 3. 头部插入
System.out.println("头部插入 1 万元素:");
System.out.println(" ArrayList: " + measure(() -> {
ArrayList<Integer> a = new ArrayList<>();
for (int i = 0; i < 10000; i++) a.add(0, i);
}));
System.out.println(" LinkedList: " + measure(() -> {
LinkedList<Integer> l = new LinkedList<>();
for (int i = 0; i < 10000; i++) l.addFirst(i);
}));
}
static String measure(Runnable r) {
long start = System.nanoTime();
r.run();
return (System.nanoTime() - start) / 1_000_000 + " ms";
}
}典型结果：
随机访问 10 万次:
ArrayList: 5 ms ← 极快
LinkedList: 2000 ms ← 极慢
迭代器遍历:
ArrayList: 8 ms
LinkedList: 7 ms ← 迭代器方式遍历反而快
头部插入 1 万元素:
ArrayList: 1500 ms ← 每次都要移动元素
LinkedList: 5 ms ← 只需改指针避坑指南
| 误区 | 真相 |
|---|---|
| 「LinkedList 增删比 ArrayList 快」 | 只有迭代器增删或头尾操作时，LinkedList 才是 O(1)。按索引增删都是 O(n) |
| 「LinkedList 不需要移动元素，所以一定快」 | 但需要遍历找到位置，O(n)。总体不一定更快 |
| 「LinkedList 内存占用更低」 | 每个节点额外 2 个引用，内存占用更高 |
| 「LinkedList 适合做随机访问」 | LinkedList 不适合按索引访问，O(n) |
一句话总结
ArrayList：用「索引」思考 → 随机访问多用它
LinkedList：用「迭代器」思考 → 头尾操作或迭代中增删用它
ArrayDeque：队列/栈首选 → 比 LinkedList 快 3 倍