适用读者：背过"数组随机访问 O(1)、链表插入 O(1)"但没在真机上对比过的人。
前置：S03-B01（复杂度口径）。
实测环境：JDK 21 / Ubuntu 24.04.1（ArrayListvsLinkedList）；实测日期 2026-11-05。
覆盖旧文：A-1499（数组，152 点）、A-1498（链表，167 点）= 319 点。
覆盖扩展：E-S03-002（cache 局部性）、E-S03-003（动态数组扩容摊还）。
上一篇：S03-B01 · 复杂度的三种写法与数据结构选型
下一篇：S03-B03 · 栈与队列。
1. 一句话结论
数组把数据放在一起，链表把数据散在各处——这个物理差异，在真实机器上比复杂度符号更能决定性能。
| 维度 | 数组（ArrayList） |
链表（LinkedList） |
|---|---|---|
| 随机访问 | O(1)（地址 = base + i×size） | O(n)（走指针） |
| 头部插入 | O(n)（搬移全部元素） | O(1) |
| 尾部插入 | 摊还 O(1) | O(1) |
| 中间插入 | O(n) | O(n)（找位置）+ O(1)（插） |
| 内存连续性 | ✅ 连续 | ❌ 分散 |
| 每元素额外开销 | 无（除了扩容空闲位） | 每节点 2 个指针（+ 对象头） |
| cache 友好 | ✅ 极好 | ❌ 差（每条链是一次可能的 cache miss） |
2. 实测：理论复杂度相同的东西，差了 20–390 倍
同一台机器、同一 JVM（-Xmx512m）、10 万次操作：
// 1) ArrayList 头部插入
for (int i = 0; i < N; i++) al.add(0, i);
// 2) ArrayList 尾部插入
for (int i = 0; i < N; i++) al2.add(i);
// 3) 顺序 get(i) 遍历
for (int i = 0; i < N; i++) s += list.get(i);
// 4) LinkedList 头部插入
for (int i = 0; i < N; i++) ll2.addFirst(i);
实测结果：
| 操作 | 耗时 | 相对比较 |
|---|---|---|
ArrayList 头插 10 万次 |
535.9 ms | 比尾插慢 23.7× |
ArrayList 尾插 10 万次 |
22.6 ms | 基准 |
ArrayList 顺序 get 10 万次 |
15.9 ms | 基准 |
LinkedList get(i) 遍历 10 万次 |
6,163.2 ms | 比数组慢 388× |
LinkedList 头插 10 万次 |
26.7 ms | 与数组尾插同量级 |
2.1 三个值得记住的结论
ArrayList头插是 O(n²)：每次插到 0 位都要把后面所有元素右移。10 万次累计 ≈ 5×10⁹ 次搬移，实测 536 ms 已经算快（靠System.arraycopy的批量搬移）。LinkedList.get(i)遍历是 O(n²)：每次get(i)都从头走 i 步。这是"用链表做下标遍历"的经典陷阱——正确写法是用Iterator或for-each（O(n)）。- 链表的唯一真优势在"已知位置的插入/删除"（头插 26.7 ms 与数组尾插相当）。
2.2 为什么差距远超复杂度预测
LinkedList.get(i) 是 388 倍而不是"常数倍"，原因有三：
| 原因 | 说明 |
|---|---|
| cache miss | 每个节点是独立对象，可能散落在堆各处；每次跳转都可能触发一次内存访问 |
| 对象头与指针 | 每个 Integer 节点 ≈ 16 字节对象头 + 2 个引用（8 字节 each） |
| 无预取 | CPU 无法预取"下一个指针指向哪" |
数组则相反：连续内存 + 硬件预取 + cache line 命中率高。这就是 E-S03-002 的实质：复杂度相同时，内存布局决定真实性能。
3. 动态数组扩容：为什么说"摊还 O(1)"（E-S03-003）
ArrayList 默认容量 10，扩容 1.5 倍。插入 n 个元素的总搬移次数：
10 + 15 + 22 + 33 + … ≈ 3n （几何级数，总和与 n 同阶）
所以 n 次插入的总代价是 O(n)，摊还到每次是 O(1)。
| 说法 | 正确性 |
|---|---|
"ArrayList 插入是 O(1)" |
⚠️ 不准确：摊还 O(1)，单次扩容那一下是 O(n) |
| "预分配容量可避免扩容" | ✅ new ArrayList<>(n) 或 ensureCapacity |
| "扩容倍数越大越省" | 代价是内存浪费（1.5× vs 2× 的取舍） |
工程建议：能预估规模就预分配，尤其在百万级集合上。
4. 链表真正的用武之地
| 场景 | 为什么链表合适 |
|---|---|
| LRU 缓存 | 需要 O(1) 移动节点到队首（配合哈希表定位） |
| 频繁在已知节点前后插入/删除 | 数组要搬移，链表只改指针 |
| 内存碎片化环境 | 大块连续内存拿不到时，链表可分散分配 |
| 实现栈/队列（链式） | 无扩容成本，容量无上限（除内存） |
反例（不该用链表）：
| 场景 | 原因 |
|---|---|
需要下标访问（get(i)） |
O(n)，且 cache 极不友好 |
| 需要遍历求和/查找 | 数组快得多（实测 388×） |
元素很小（如 int） |
每节点额外 2 指针 + 对象头，内存放大数倍 |
5. Java 里的实现细节（易被忽视）
| 类 | 底层 | 注意 |
|---|---|---|
ArrayList |
Object[] |
扩容 1.5×；remove(i) 也搬移 |
LinkedList |
双向链表 | 实现了 Deque，可当栈/队列用 |
ArrayDeque |
环形数组 | 当栈/队列首选，比 LinkedList 快 |
CopyOnWriteArrayList |
写时复制 | 读多写少；写操作 O(n) 且内存翻倍 |
实践判据：需要栈/队列优先
ArrayDeque；LinkedList只在"真的要频繁中间插入删除"时才考虑。
6. 五个误区
| 误区 | 真相 |
|---|---|
| "链表插入删除一定比数组快" | 找位置 O(n)；不找位置的场景数组常常更快 |
"LinkedList 适合做队列" |
ArrayDeque 通常更快、更省内存 |
| "数组插入是 O(1)" | 只有尾部摊还 O(1)；头部/中间 O(n) |
| "复杂度一样，性能就一样" | 实测差 388×（§2） |
| "链表省内存" | 每节点多 2 个指针 + 对象头，小元素时反而更费 |
7. 自检
ArrayList头插 10 万次是 O(n²) 还是 O(n)？解释你的答案。- 为什么
LinkedList.get(i)遍历比数组慢两个数量级？ - 什么情况下链表确实优于数组？举两个真实场景。
- 动态数组的"摊还 O(1)"怎么推导？为什么单次扩容仍是 O(n)？
- 你要实现一个栈，选
LinkedList还是ArrayDeque？为什么？
8. 下一篇
S03-B03 · 栈与队列：只在一端操作的价值
数组与链表的取舍讲完，下一篇看两种"受限"的结构：只在一端进出的栈、两端进出的队列。会给出循环队列的判满/判空条件与"为什么必须牺牲一格"的推导。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1498/1499；扩展点 E-S03-002/003。ArrayList/LinkedList 对比为 2026-11-05 在 JDK 21 实测。