ArrayList vs LinkedList：从源码看使用场景

面试官问："ArrayList 和 LinkedList 有什么区别？分别适合什么场景？"

大多数人的回答是："ArrayList 查询快，LinkedList 增删快。"——这个回答在十年前可能是对的，但在今天的 JDK 实现和现代 CPU 架构下，后半句几乎是错的。

这篇文章不靠记忆、不靠直觉，我们用源码 + 数据 + 内存模型来回答这个问题。读完之后你会发现，面试中最有区分度的答案往往不是背出来的，而是理解出来的。

ArrayList 的内部结构非常朴素——就是一个 Object[] 数组。所有的元素按插入顺序连续存放在内存中：

transient Object[] elementData; // 底层数组（transient 表示不参与序列化）
private int size;               // 当前元素个数（≠ 数组长度）

// 默认空数组，首次 add 时扩容到 10
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 随机访问 —— O(1)
public E get(int index) {
    rangeCheck(index);
    return elementData(index); // 直接下标取值
}

// 下标访问的内部方法，无任何边界检查
E elementData(int index) {
    return (E) elementData[index];
}

get(index) 的实现只有一行——直接数组下标访问。这意味着不管列表有 10 个元素还是 100 万个元素，get(999999) 的速度和 get(0) 完全一样。

LinkedList 的底层是一个双向链表——每个节点保存了前驱 prev、后继 next 和元素值 item：

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

要访问第 i 个元素，LinkedList 必须从头（或尾）开始，逐个节点跳转：

Node<E> node(int index) {
    // 优化：从距离更近的一端开始遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;       // 从头部跳到 index
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;       // 从尾部跳到 index
        return x;
    }
}

即使 JDK 做了"从更近的一端开始"的优化，访问中间元素仍然需要 O(n/2) 次指针跳转——这在大列表下是很可观的开销。

我们用 JMH 做了一个标准化基准测试，列表大小为 100,000，每个操作重复 1000 次取平均值：

注意看中间插入那一行——这是最大的认知误区。

那 LinkedList 在什么场景下真的快？——头尾操作：addFirst()、addLast()、removeFirst()、removeLast() 都是 O(1)。但这些操作用 ArrayDeque 做更快（连续内存 + 环形缓冲区），后面会说。

性能差异的根源不仅是算法复杂度，还有一个常被忽略的因素：CPU 缓存命中率。

现代 CPU 的 L1 缓存每次加载不是 1 个字节，而是一整个 Cache Line（64 字节）。ArrayList 的引用数组是连续的，所以一次缓存加载可以装下 8 个元素引用（每个 4-8 字节），CPU 预取器还能提前加载下一个 Cache Line。

LinkedList 的节点散落在堆内存的不同位置，每次跳转到新节点都可能触发一次 Cache Miss，需要从更慢的 L2/L3 缓存甚至主存中读取数据。这就是为什么 LinkedList 遍历 10 万个元素比 ArrayList 慢 4 倍——不是算法差了 4 倍，而是内存访问模式差了 4 倍。

每个元素的实际内存占用对比（64 位 JVM，开启指针压缩）：

也就是说，LinkedList 的额外开销是每个元素 24~36 字节的 Node 结构。对于 100 万个 Integer 元素：

• ArrayList 额外开销：100 万 × 8 字节（引用）= ~8 MB
• LinkedList 额外开销：100 万 × 32 字节（Node）= ~32 MB

LinkedList 多消耗了 4 倍的存储空间，而这 4 倍空间全部浪费在了"链接"上——不存储任何业务数据。

综合以上分析，给出一个明确的选择指南：

面试标准回答模板

👉 下一篇：ArrayList 扩容机制与性能调优