链表 vs 数组实测：100 万条数据下 LinkedList 遍历慢了 10 倍，随机读慢了 10 万倍，教科书没骗你但也没说全

一道让我怀疑人生的 LeetCode

去年写 LRU 缓存，用 LinkedList 存 key 做淘汰队列，本地跑 10 万次操作大概 200ms，提交上去 2.3 秒 TLE 了。我盯着屏幕看了半天，第一反应是评测机抖动，重新交了三遍，一样的数。

后来换成一个自己写的环形数组加头尾指针，掉到 180ms。这件事我一直没想通，因为按课本讲的，LRU 要频繁地在头部插入、在中间删除，链表应该是正解才对。

真正的暴击是三个月后。线上有个每天跑一次的对账脚本，把 80 万条订单 ID 塞进 LinkedList 遍历去重，稳定耗时 4.2 秒。同事顺手改成 ArrayList，0.6 秒。七倍。那天下午我把手头的事全推了，花了两个晚上搭了个 JMH 工程，把这事彻底测了一遍。

测试环境和具体参数（你要复现就照这个来）

• 机器：i7-12700H，DDR4-3200 双通道 16G×2，Windows 11 + WSL2 Ubuntu 22.04
• 运行时：Temurin JDK 17.0.9，JMH 1.37，-Xmx4g -XX:+UseG1GC
• 数据规模：100 万个 Integer（值域 0~999999，避开 -128~127 的 Integer 缓存，免得对比失真）
• 预热 5 轮，测量 5 轮，取平均；单 fork
• 每个 case 我都跑了两遍，数字有 ±15% 波动，别拿它当基准线，看数量级就行

结果：

前两列数字摆一起，其实已经把结论说完了：链表只在「你已经站在那个节点上」的时候快，而「走到那个节点上」的成本，它比数组贵得多，而且贵得离谱。

教科书漏掉的那三个字：常数项

所有讲数据结构的书都会告诉你，链表插入删除是 O(1)，数组是 O(n)。这句话没错，但它默认了一个前提：访问任意一块内存的代价是一样的。这个前提在 1980 年代成立，在今天不成立。

具体数字：x86-64 的缓存行是 64 字节。L1 命中约 1ns，L2 约 4ns，L3 约 15ns，打到主存是 80~100ns。差了将近两个数量级。

再看内存布局。ArrayList 内部是一个连续的引用数组，压缩指针下每个引用 4 字节，一行 64 字节的缓存行能装 16 个引用。遍历的时候，硬件预取器能识别这种线性步进，把后面几行提前拉进 L2，实际的主存 miss 次数远小于 n。

LinkedList 的每个节点是独立对象：对象头 12 字节 + prev 引用 4 字节 + next 引用 4 字节 + item 引用 4 字节 = 24 字节，再按 8 字节对齐，实际占 32 字节。100 万个节点就是 32MB，散落在堆的各个角落。遍历时每次 node = node.next 都是一次新的地址跳转，预取器完全失效——它没法猜下一个节点在哪。

所以把缓存折进去之后，两者的「等效复杂度」其实是：数组约 O(n/16) 次主存访问，链表是 O(n) 次。n 一大，这个 16 倍的系数差就被放大成了你实际看到的 10 倍耗时。

对了，LinkedList 的随机读为什么能慢到 10 万倍？因为它是双向链表，源码里 node(index) 会先比较 index 和 size/2，决定从头走还是从尾走。即便如此，读第 50 万个元素也要走 50 万步。1000 次这样的读取就是 5 亿步指针解引用，每一次都可能撞上 cache miss。

一个很多人没注意的坑：Java 的「数组」其实是指针数组

上面那个 1.2ms 的遍历成绩，得打个折看。ArrayList<Integer> 存的是一百万个引用，真正的一百万个 Integer 对象还是散在堆上，只不过它们是按顺序 new 出来的，年轻代里碰巧挨得比较近。

如果你换成 C++ 的 vector<Order>，那是值语义，对象本体连续排布，64 字节缓存行能塞下两个 32 字节的 Order，遍历性能还能再上一个台阶。

Java 想吃到这个红利，只能用原始类型数组手动做 SoA（Structure of Arrays）：本来一个 Order{int id; long ts; int amount;}，拆成 int[] ids、long[] timestamps、int[] amounts 三个平行数组。代码丑，但遍历吞吐能翻好几倍，风控和实时计算那类场景里很常见。

所以你在 Java 里说「数组快」，严格讲快的是引用局部性，不是对象局部性。这两个概念混在一起讲，是很多性能文章含糊过去的地方。

那链表到底还有没有用？有，但只有四种场景

1. 节点本身就是大对象。 比如节点里塞了 1KB 的订单快照，拷贝成本压过了指针开销，这时候数组的搬移反而更贵。
2. 你已经在节点上了，要 O(1) 把它摘掉。 定时器轮、无锁队列、LRU 的内部节点管理，都是这个模式。注意前提是「已经在节点上」，如果你还得先查找，那优势立刻没了。
3. CAS 只能操作单个指针。 写无锁结构时，数组扩容需要搬移整块内存，链表改两个指针就行，这是并发语义上的刚需，跟性能无关。
4. 你有内存池，节点是连续分配的。 这种情况下指针追逐变成顺序访问，性能能追回来——但这个结构已经不叫链表了，它叫 unrolled linked list，本质上是「分块的数组 + 块间指针」。

第 4 条特别值得说。真实世界里活下来的链表，几乎全是这个形态。Redis 的 list 从早期的双向链表 + ziplist，改成 quicklist（分块 ziplist 用双向链表串起来），7.0 之后又换成 listpack；MySQL InnoDB 的 B+ 树，一个 16KB 的页里塞几百个索引项，页与页之间才用双向链表串。链表用来连接大块，不用来存单个元素。 这是工程界用几十年试出来的答案。

落地到日常写代码，我的决策清单

• 容器元素是 int/long/短字符串/小对象，且要遍历 → 用数组，没得商量
• 需要频繁在头部插入 → 用 ArrayDeque，别用 LinkedList。ArrayDeque 是环形数组，头尾操作都是摊还 O(1)，还没有指针开销
• 需要频繁在任意位置按「已知节点」删除 → 才轮到链表
• 需要按下标随机访问 → 数组。链表做这件事的复杂度是 O(n)，不是 O(1)
• 元素个数少于 100 个 → 随便，别优化，你会花在纠结上的时间比省下的 CPU 时间值钱
• 不确定 → 先用数组，出现性能问题了再 profile。反过来做的话，你会先难受很久

顺便说一句，java.util.LinkedList 这个类在 JDK 自己的代码里基本没人用。AQS 的等待队列是双向链表，但那儿节点数量通常是个位数。你在业务代码里 new 出来的每一个 LinkedList，大概率都是一个可以避免的性能负债。

想自己测一遍的话，代码骨架在这

别用 System.currentTimeMillis() 手写循环，JIT 会把你的循环优化没，你会得到一堆看起来特别快的假数据。用 JMH：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 5, time = 1)
@Fork(1)
@State(Scope.Benchmark)
public class ListBench {

@Param({"1000000"})
    int n;



![图片](http://img2.baidu.com/it/u=890180079,3602562183&fm=253&fmt=auto&app=138&f=JPEG?w=514&h=500)


private List<Integer> array;
    private List<Integer> linked;

@Setup
    public void setup() {
        array = new ArrayList<>(n);
        linked = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            array.add(i);
            linked.add(i);
        }
    }

@Benchmark
    public long arrayIterate() {
        long s = 0;
        for (int i = 0, sz = array.size(); i < sz; i++) s += array.get(i);
        return s;
    }

@Benchmark
    public long linkedIterate() {
        long s = 0;
        for (Integer v : linked) s += v;
        return s;
    }
}

两个提醒。第一，for (int i = 0; i < array.size(); i++) 里那个 size() 提到循环外，ArrayList 的 size() 是简单字段读，LinkedList 的 size() 也是，但涉及接口调用时不一定能被内联，差别不大但能省就省。第二，测链表千万别用 for-each，它内部走迭代器，每次 next() 都多一层对象访问，我第一版就踩了这个坑，测出来的链表遍历慢了 18 倍而不是 10 倍，差点得出错误结论。

最后说个感受。性能这件事最反直觉的地方在于，你脑子里那套复杂度模型是「操作次数」的模型，而 CPU 关心的是「内存访问模式」。这两套语言不通，你在纸面上算得再漂亮，跑到真机上还是得让缓存说了算。