数组 vs 链表：参考对比
Vol 2：算法森林探险 · 决策参考页
一览
木牌 A → 数组（连续内存）：随机访问 O(1)，插入/删除 O(n)，缓存极好
木牌 B → 链表（离散节点）：随机访问 O(n)，定点插入/删除 O(1)，缓存差详细对比
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存布局 | 连续块 | 散落节点 + next 指针 |
| 随机访问 | O(1) | O(n) |
| 末尾插入 | O(1) 摊销 | O(1) 已知尾节点 |
| 中间插入 | O(n) —— 右移 | O(1) —— 已站在插入点 |
| 中间删除 | O(n) —— 左移 | O(1) —— 已知前驱 |
| 额外开销 | 极少 | 1-2 个指针 + 对象头 |
| 缓存局部性 | ✅ 极好 | ❌ 差 |
场景选型
| 需求 | 选 |
|---|---|
| 频繁按索引读取 | 数组 |
| 频繁中间插入/删除 | 链表 |
| 双向遍历 | 双链表 |
| 轮询循环 | 循环链表 |
| 不确定，求稳妥 | 动态数组 —— 95% 场景的默认选择 |
为什么数组实际中更快？
复杂度表说都是 O(n)，但数组遍历比链表快 10-100 倍。
数组连续——访问 arr[0] 时，CPU 把周围 64 字节都拽到 L1 缓存。arr[1] 已在缓存里，不要钱。
链表离散——node.next 可能在天涯海角，每次都从主存读。主存比 L1 缓存慢约 100 倍。
详细硬件原理见 Vol 3：存储器层次结构。
复杂度速查
操作 数组 链表
─────────────────────────
随机访问 O(1) O(n)
末尾插入 O(1)* O(1)**
中间插入 O(n) O(1)**
开头插入 O(n) O(1)**
按值查找 O(n) O(n)
中间删除 O(n) O(1)**
* 阵列 O(1) ** 定点 O(1)