264. Java 集合 - 插入元素性能对比：LinkedList vs ArrayList

在 Java 中，我们常用 LinkedList 和 ArrayList 来表示列表结构，它们在插入操作上的性能差异尤其值得关注。本节我们通过基准测试、原理分析和实例演示，深入剖析它们在不同位置插入元素的效率表现。

---

🎯 基本原理回顾

🔗 LinkedList 的插入机制：

• 每个节点包含指向前一个和后一个节点的引用。
• 插入新节点时，只需修改相邻节点的引用指向即可。
• 但是：在插入中间位置时，你必须先从头或尾遍历到目标位置，这个过程非常耗时，特别是在节点不连续存储（指针跳跃+缓存未命中）。

📦 ArrayList 的插入机制：

• 底层是一个数组。
• 插入元素前，需要将插入点之后的所有元素整体右移一位。
• 如果数组已满，还要扩容：重新分配一个更大的数组并复制所有元素。

---

📊 插入操作性能对比分析

📍 插入位置对性能的影响（LinkedList）

我们测量了在开头、中间和末尾插入元素时的性能差异。

🟢 插入开头（头插）表现稳定：

List<Integer> list = new LinkedList<>();
list.addFirst(42); // 等价于 list.add(0, 42);

SIZE	Score (ns/op)
10	7.00
100	7.12
1,000	7.56

✅ 头部插入性能基本恒定，适合大量前置添加的场景。

🔴 中间插入代价高（随着列表增长成倍增加）：

list.add(list.size() / 2, 42);

SIZE	Score (ns/op)
10	10.6
100	49.1
1,000	584.8
10,000	46,157

⚠️ 插入中间性能是灾难性的 —— 时间复杂度约 O(n)，不建议这么用！

🟡 尾部插入也很高效：

list.add(42); // 或 list.addLast(42);

SIZE	Score (ns/op)
10	9.13
1,000	9.79

---

📍 插入位置对性能的影响（ArrayList）

🟢 尾部添加效率极高（尤其预留容量时）：

List<Integer> list = new ArrayList<>();
list.add(42);

SIZE	Score (ns/op)
10	2.21
1,000	5.60

✅ 最推荐的方式，尤其是列表动态增长的主场景。

🔶 中间插入需移动元素，代价略高：

list.add(list.size() / 2, 42);

SIZE	Score (ns/op)
10	23.7
1,000	56.0

🔴 头部插入最慢：

list.add(0, 42);

SIZE	Score (ns/op)
10	22.3
10,000	717.8

⚠️ 越靠前插入，复制操作越多，性能越差。

---

🧨 数组扩容的隐藏成本（ArrayList）

当数组容量不足时，ArrayList 会：

1. 创建一个容量更大的新数组（通常为原大小 * 1.5）。
2. 将旧数组内容复制过去。
3. 插入新元素。

List<Integer> list = new ArrayList<>(10);
for (int i = 0; i < 10; i++) list.add(i); // 已满
list.add(42); // 触发扩容！

SIZE	插入尾部（满）	插入中间（满）	插入头部（满）
10	19.3 ns/op	39.3 ns/op	28.2 ns/op
1,000	432.3 ns/op	451.4 ns/op	452.1 ns/op
10,000	4,140.6 ns/op	4,638.6 ns/op	4,762.7 ns/op

⚠️ 插入时触发扩容，会显著拖慢操作速度。

---

🧠 总结：该用谁？在哪用？

场景	推荐集合	理由
高频插入尾部	✅ ArrayList	内存连续、写入快
高频插入头部或尾部	✅ LinkedList	头尾插入性能稳定，特别是 addFirst/addLast
高频插入中间，数据量大	❌ 避免使用	不管是哪种 List，中间插入都较慢（尤其 LinkedList）
可预测元素数量	✅ ArrayList	可预设容量，避免扩容成本
需要频繁插入和删除操作	✅ LinkedList	只要不是基于 index 的随机访问