262. Java 集合 - Java 中 ArrayList 与 LinkedList 读取元素性能大对决

在 Java 中，我们经常面对一个问题：

🔍 哪个更适合：ArrayList 还是 LinkedList？

这节我们以“读取元素”为例，用基准测试（benchmark）对两者进行深入比较。

🧪 Benchmark 场景简介

我们将对以下三种读取操作进行性能测试（使用 JMH 工具）：

1. 读取第一个元素：list.get(0)
2. 读取最后一个元素：list.get(list.size() - 1)
3. 读取中间的元素：list.get(list.size() / 2)

我们对 ArrayList 和 LinkedList 分别执行这些操作，并使用不同的列表大小进行测试。

⚙️ 测试代码简化展示

List<Integer> ints = ...; // 已填充好数据
int last = ints.size() - 1;
int middle = ints.size() / 2;

ints.get(0);       // 读取第一个元素
ints.get(last);    // 读取最后一个元素
ints.get(middle);  // 读取中间元素

📊 基准测试结果总结

✅ 读取第一个元素

👉 两者性能几乎相同。读取第一个元素是 O(1) 操作，和数据规模无关。

✅ 读取最后一个元素

🔎 LinkedList 多了一点开销（虽然很小），但仍是 O(1)，因为它有一个指向末尾的引用。

⚠️ 读取中间元素

🔥 注意 LinkedList 的性能急剧下降！这说明读取中间元素是 O(n) 操作 —— 因为它需要顺着指针走一遍。

🧠 为什么 LinkedList 慢？

🔍 内部结构回顾：

Node {
   E element;
   Node next;
   Node previous;
}

• LinkedList 是双向链表。
• LinkedList 类保存两个指针：first 和 last。
• 读取中间元素时必须逐个节点遍历，即“指针追踪（pointer chasing）”。

💣 Pointer Chasing & Cache Miss 示例

我们用以下代码构造更“稀疏”的链表，以人为制造 cache miss 的情况：

LinkedList<Integer> ints = new LinkedList<>();
LinkedList<Integer> intsOther = new LinkedList<>();

for (int i = 0; i < LIST_SIZE; i++) {
    ints.add(i);
    for (int k = 0; k < SPARSE_INDEX; k++) {
        intsOther.add(k); // 插入无用节点，制造内存间隔
    }
}

➡️ 节点之间不连续，会大大降低性能。

📌 总结：读取操作谁更强？

✅ 小贴士

• 🚀 使用 JMH 进行性能测试，避免误导的微基准。
• 📦 ArrayList 底层是数组，支持随机访问，性能稳定。
• 🔄 LinkedList 更适合频繁插入/删除操作（尤其在头部）。