课本上那张表很好记：数组查询快、插入删除慢；链表查询慢、插入删除快。我照着这条规律选过几次容器，结果跑起来跟想的完全不是一回事。于是这次不按课本，直接测。

一、怎么测的

100 万个元素，六组操作，每组都跑完取"每次操作多少纳秒"。为了避免 JIT 预热影响，先跑几轮热身；为了不让编译器把循环优化掉，每次访问的结果都累加到一个变量里，最后打印出来。

有个坑必须提前说：LinkedList 的随机访问是 O(n)，100 万次根本跑不完（要几十个小时）。所以这一项它只测 1000 次，再换算成每次耗时——换算过程在输出里写着，没藏。

二、结果

=== 1. 尾部追加 1000000 次 ===
int[]                        每次      6.9 ns
ArrayList           每次      9.4 ns
LinkedList          每次     74.0 ns=== 2. 随机 get 100 万次 ===
int[]                        每次      7.3 ns
ArrayList           每次     11.6 ns
LinkedList          每次 868905.8 ns   （换算自 1000 次）=== 3. 头部插入 10000 次 ===
ArrayList           每次   4702.3 ns
LinkedList          每次     63.1 ns=== 4. 中间插入 10000 次 ===
ArrayList           每次   2053.9 ns
LinkedList          每次  44760.3 ns=== 5. 遍历求和 100 万 ===
int[]                        每次      1.0 ns
ArrayList           每次      5.2 ns
LinkedList          每次     11.3 ns=== 6. 按值查找 200 次 ===
ArrayList           每次 447156.0 ns
LinkedList          每次 7066313.5 ns=== 7. 内存（100 万个 int）===
int[]                        3.9 MB
ArrayList          19.3 MB
LinkedList         38.2 MB

三、三个跟课本不一致的地方

第一，随机访问不是"慢一点"，是慢七万多倍。

11.6 纳秒和 868905 纳秒，差了 7.5 万倍。0.0000116 毫秒对比 0.87 毫秒——一个是"感觉不到"，一个是"肉眼可见地卡"。

原因不复杂：数组是连续内存，算个地址就取到了；链表要从头一个个跳，访问第 50 万个元素就要跳 50 万次。O(n) 这三个字平时看着没什么，乘上一百万就原形毕露。

第二，中间插入，链表反而慢 22 倍。

这才是真正让我意外的一条。LinkedList.add(size/2, x) 听起来是链表的强项，实测 44760 纳秒 vs 数组的 2053 纳秒。

原因是我一直忽略的那半句话：链表的插入是 O(1)，指的是"已经拿到那个位置的节点之后"。而 add(index, x) 这个 API 自带一次"从头走到 index"的定位，那一步是 O(n)。所以你付的仍然是 O(n)，还额外付了指针追逐的代价。

第三，链表唯一赢的地方是头部插入，赢了 75 倍。

add(0, x) 不需要定位——头插就是 O(1)，63 纳秒。而数组要把它后面的元素全部往后挪一位，4702 纳秒。

所以"链表插入快"这句话不是错的，是缺了前提。前提是：插入位置你已经知道了。

四、为什么会差这么多

O 复杂度只说了"数据量变大时怎么涨"，没说常数因子。而这里的常数因子差得非常离谱。

一个常见的解释是 CPU 缓存：数组的元素挨在一起，一次读入缓存行就能连带用好几个；链表每个节点都是堆上单独一块，地址乱跳，每次访问几乎都是缓存未命中。指针追逐（node = node.next）还会让 CPU 的分支预测和预取失效。

这条我没有专门测——要测需要做缓存命中率的实验，那是另一篇文章。但它和上面的数字是吻合的：同样是"走一百万步"，数组那 7.3 纳秒看起来根本不像走了一百万步。

五、内存差十倍

3.9 MB、19.3 MB、38.2 MB。

int[] 就是 100 万个 4 字节，正好 3.9 MB。ArrayList 里除了一个 Object[]，还有 100 万个 Integer 对象（对象头 16 字节 + 值），所以涨到 19.3 MB。LinkedList 每个节点还要多两个引用，38.2 MB。

也就是说，用 LinkedList 存 100 万个 int，比 int[] 多用十倍内存，然后每一项操作还都更慢。

（这个数是同类型分配两次取差值测的。第一次测出来 int[] 是负数，原因是 GC 把热身留下的垃圾也在那期间收掉了，差值算错。改成"分配两份、量第二份的增量"才对得上。）

六、结论

ArrayList 应该是默认选择。绝大多数场景下它都比 LinkedList 快，而且省内存。

LinkedList 值得用的场合只有一个：你确实要频繁在头部/尾部增删，并且把它当双端队列用。那用 ArrayDeque 通常还更快，所以严格说 LinkedList 在 Java 里已经很难找到非它不可的理由了。

那什么情况下链表真的快？当你已经持有那个位置的引用时——比如遍历的同时删除（用 Iterator.remove()），或者自己维护节点指针。这种情况下你付的不是 O(n)，O(1) 的插入才真正兑现。

最后一句实话：这类基准数字有抖动。 我连跑两次，随机访问那一项从 52 万纳秒变成了 87 万纳秒，头部插入从 85 纳秒变成 63 纳秒。量级和结论是稳的，具体数值不必当真。

附：核心代码

static final int N = 1_000_000;// 随机访问：结果累加起来，防止 JIT 把循环整段优化掉
long sink = 0;
long t = System.nanoTime();
for (int i = 0; i < N; i++) sink += arr[idx[i]];
long d = System.nanoTime() - t;
System.out.println("每次 " + (double) d / N + " ns，sink=" + sink);// LinkedList 只测 1000 次，再换算
int small = 1000;
t = System.nanoTime();
for (int i = 0; i < small; i++) sink += ll.get(idx[i]);
d = System.nanoTime() - t;
System.out.println("每次 " + (double) d / small + " ns（换算）");// 内存：同类型分配两份，量第二份的增量
long t1 = used();
int[] q2 = new int[N];
long t2 = used();
System.out.println("int[] ≈ " + (t2 - t1) / 1024.0 / 1024.0 + " MB");static long used() {for (int i = 0; i < 3; i++) {System.gc();try { Thread.sleep(80); } catch (InterruptedException ignored) {}}Runtime rt = Runtime.getRuntime();return rt.totalMemory() - rt.freeMemory();
}