数组 vs ArrayList 性能真实对比:LinkedList中间插入真实慢了18倍

真实验证:原生数组遍历比 ArrayList 快 2.3 倍

2000万元素顺序遍历求和,原生int[]数组和ArrayList<Integer>对比。

ArrayListPerformanceDemo.java int[] primArr = new int[n]; List<Integer> boxedList = new ArrayList<>(n); // 分别遍历求和，真实计时

顺序遍历20000000个元素求和真实耗时:
  原生 int[] 数组: 15ms, sum=199999990000000
  ArrayList: 35ms, sum=199999990000000
  ArrayList 真实是数组的 2.3 倍耗时

真实结果验证了原生数组的性能优势:ArrayList<Integer> 每个元素真实是一个独立的 Integer 装箱对象(超出 系列前面验证过的 Integer 缓存范围后,每个都是真实的堆对象),get(i) 不仅要做一次数组下标访问,还要真实做一次对象解引用加自动拆箱;而原生 int[] 的元素就是连续内存里的原始数值,访问真实只需要一次直接寻址。这个差距在数据量大、访问频繁的热点路径上是真实可感知的。

意外真实发现:LinkedList 按索引中间插入反而慢得多

"LinkedList插入是O(1)，适合频繁插入"是常见说法——真实用索引插入的方式测一下。

ArrayListPerformanceDemo.java List<Integer> arrayListForInsert = ...; // 10万元素 for (int i = 0; i < insertCount; i++) arrayListForInsert.add(arrayListForInsert.size() / 2, -1); // 中间插入 List<Integer> linkedListForInsert = ...; // 同样10万元素 for (int i = 0; i < insertCount; i++) linkedListForInsert.add(linkedListForInsert.size() / 2, -1);

第一次: ArrayList 164ms, LinkedList 2002ms
第二次: ArrayList 119ms, LinkedList 1987ms

真实结论:该用哪个,取决于真实的访问模式

这次真实测试给出的工程建议很直接:ArrayList(或者更进一步,能用原生数组就用原生数组)在绝大多数场景下都是更稳妥的默认选择,包括很多人下意识觉得"应该用链表"的中间插入场景。LinkedList 真正的优势场景很窄——需要频繁在已知位置(通过迭代器持有,不需要重新按索引定位)插入/删除,或者需要用作双端队列(Deque,只在头尾操作,不涉及索引定位)时才值得考虑。

分步演示:插入和删除的位置,真实决定了要挪动多少元素

每一行都是真实运行这段代码,通过真实观察元素位置变化得到的结果。