265. Java 集合 - LinkedList vs ArrayList 插入性能实战对比分析

在 Java 中，LinkedList 和 ArrayList 是最常用的两个 List 实现。理论上，你可能会认为 LinkedList 插入效率更高，尤其是中间插入。但在实际运行中，ArrayList 往往在大多数场景下都更胜一筹，这其中隐藏着不少硬件与底层结构导致的性能差异。

🔍 理论 vs 实际：为什么 `LinkedList` 的插入反而慢？

虽然从算法复杂度角度看，LinkedList 的插入操作是 O(1)（假设我们已定位到插入位置），而 ArrayList 需要移动后续元素，插入操作是 O(n)。但真正运行时，LinkedList 的插入通常更慢。

🤯 为什么？

因为 LinkedList 需要频繁指针跳转（pointer chasing）来定位插入点，而现代硬件的缓存机制并不适合指针跳转：

节点不连续地分布在堆内存，无法命中 CPU 缓存。
指针跳转耗时大（尤其是在大列表中查找中间节点时）。

举个例子：

List<Integer> linkedList = new LinkedList<>();
linkedList.add(0);    // 头部插入，快
linkedList.add(500);  // 插入中间，需要从头或尾遍历一半，慢

✅ `LinkedList` 的两个插入优势场景

尽管在大多数情况下不如 ArrayList 快，但 LinkedList 在以下两种场景中表现不错：

1️⃣ 在头部插入元素

List<String> list = new LinkedList<>();
list.add(0, "Hello"); // 或 list.addFirst("Hello");

插入时间与列表大小无关。
因为直接持有 head 节点引用，仅需一次指针操作。
插入效率恒定，非常适合构建栈（Stack）结构。

2️⃣ 在尾部插入元素

list.add("World"); // 或 list.addLast("World");

尾部也有引用，定位快。
插入开销也不会随数据量增大。
插入速度虽然略慢于 ArrayList，但仍然可接受，并且性能可预测。

📌 注意：与 ArrayList 不同，LinkedList 在插入尾部时不涉及数组扩容，避免了可能的性能波动。

⚖️ `ArrayList` 的扩容成本：值得担心吗？

ArrayList 的插入在大多数场景中更快，但当数组空间耗尽时，它需要扩容（reallocate）：

List<Integer> arrayList = new ArrayList<>(10);
for (int i = 0; i < 10; i++) {
    arrayList.add(i); // 填满数组
}
arrayList.add(42); // 触发扩容！

扩容操作包括：

分配一个更大的新数组（默认增长为原容量的 1.5 倍）。
将旧数组元素全部复制到新数组。

虽然这个操作非常耗时，但由于发生频率低（指数增长），所以：

💡 平均下来对整体性能影响不大。

而且你完全可以提前避免它：

List<Integer> list = new ArrayList<>(1000); // 预设容量

🧠 小结：什么时候选哪个？

场景	推荐集合	理由
高频率尾部插入	✅ `ArrayList`	简单、快速，缓存友好。扩容成本可控。
高频率头部插入或删除	✅ `LinkedList`	不涉及元素移动，性能恒定。适合栈（`Stack`）或队列（`Queue`）场景
高频率中间插入/删除（尤其大列表）	❌ 避免使用	`LinkedList` 遍历慢，`ArrayList` 元素移动多，两者都不理想。
需要栈或队列行为	✅ `LinkedList`	`addFirst()`/`removeFirst()`/`addLast()` 性能稳定。
操作列表为主、随机访问为主	✅ `ArrayList`	数组结构支持快速 index 定位，优于 `LinkedList` 的线性遍历。

📌 额外提示：删除 vs 插入

别忘了，在 List 中，删除操作的性能和插入是非常相似的：

ArrayList 删除也要移动元素。
LinkedList 删除需要遍历定位节点。

所以：如果插入慢，删除也不会快。

🎯 结语：什么时候不该用 `LinkedList`？

👉 当你只需要一个普通列表，而不是栈或队列时，ArrayList 几乎总是更好的选择：

❌ “LinkedList 插入是 O(1)，所以更快” 这个观点不再成立。

在现代硬件 + JVM 的实际运行下，ArrayList 由于更好的缓存友好性和连续内存布局，整体表现更强。

265. Java 集合 - LinkedList vs ArrayList 插入性能实战对比分析