ArrayList 与 LinkedList 底层原理

ArrayList 基于动态数组，LinkedList 基于双向链表。表面上看只是数据结构不同，但深入到源码、内存模型和硬件层面，差距远比"随机访问 O(1) vs O(n)"这一句话所暗示的要大得多。

ArrayList 的底层结构

核心字段

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, Serializable {

    transient Object[] elementData;  // 存储元素的数组
    private int size;                // 实际元素数量（≤ elementData.length）
}

两个关键点：

• elementData 用 Object[] 而非泛型数组：Java 泛型擦除后无法创建 new E[]，所以底层统一用 Object[]，取出时强转。
• size 与 elementData.length 是两个概念：length 是数组容量（capacity），size 是实际元素数量。size <= length。

elementData: [ A | B | C | D | null | null | null | null | null | null ]
               0   1   2   3    4      5      6      7      8      9
              ←—— size = 4 ——→  ←————— 空闲空间（capacity - size）————→

随机访问为什么是 O(1)

数组在内存中是连续存储的。访问 elementData[i] 时，CPU 只需计算：

目标地址 = 数组起始地址 + i × 每个引用的大小（通常 4 字节，开启压缩指针时）

一次加法、一次乘法，直接得到目标地址——这就是 O(1)。这也是 ArrayList 实现 RandomAccess 标记接口的原因：告诉算法"我支持高效的随机访问，请用 for 循环而不是迭代器遍历我"。

ArrayList 的扩容机制

触发条件与增长策略

当调用 add(E e) 时，如果 size == elementData.length（数组满了），就必须扩容。来看源码：

// JDK 17 源码（简化）
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();     // 数组满了，触发扩容
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity,   // 最小增长量
            oldCapacity >> 1             // 期望增长量 = 原容量的一半
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 首次添加元素，使用默认容量 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

核心逻辑：新容量 ≈ 旧容量 × 1.5（oldCapacity + oldCapacity >> 1）。

为什么是 1.5 倍而不是 2 倍？这是一个空间与时间的权衡：

数学上，当增长因子 ≤ φ（黄金比例 ≈ 1.618）时，之前释放的内存块之和最终能大于新分配的块，使得内存分配器可以复用旧空间。1.5 满足这个条件，而 2.0 不满足。

数组拷贝的底层：从 Java 到 native

扩容的核心操作是 Arrays.copyOf()，它最终调用 System.arraycopy()：

// Arrays.copyOf 本质上是：
public static <T> T[] copyOf(T[] original, int newLength) {
    T[] copy = (T[]) new Object[newLength];       // 分配新数组
    System.arraycopy(original, 0, copy, 0,        // 复制旧元素
                     Math.min(original.length, newLength));
    return copy;
}

System.arraycopy() 是一个 native 方法，JVM 内部使用 C/C++ 实现。在 HotSpot JVM 中，它通常被编译为 CPU 的 memmove 或 memcpy 指令，可以利用 SIMD 指令集一次搬运 128 位甚至 256 位数据。所以虽然扩容是 O(n) 操作，但常数因子非常小——远比你手写 for 循环逐个复制要快。

预分配容量的意义

如果你已知数据量是 10000 条：

// ❌ 默认容量 10，需要扩容约 24 次（10 → 15 → 22 → 33 → ... → 10000+）
List<String> list = new ArrayList<>();

// ✅ 一次分配到位，零扩容
List<String> list = new ArrayList<>(10000);

每次扩容都涉及堆内存分配 + 数组拷贝 + 旧数组等待 GC。预分配消除了所有这些开销。

LinkedList 的底层结构

Node 节点设计

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable {

    transient int size = 0;
    transient Node<E> first;  // 头节点
    transient Node<E> last;   // 尾节点

    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;
        }
    }
}

first                                                    last
  ↓                                                       ↓
 null ← [ prev | A | next ] ⇄ [ prev | B | next ] ⇄ [ prev | C | next ] → null

每个 Node 的真实内存开销

很多人忽视了 LinkedList 的内存代价。在 64 位 JVM（开启压缩指针，即 -XX:+UseCompressedOops，这是默认配置）下：

一个 Node<E> 对象的内存布局：
┌──────────────────────────────────┐
│  对象头 (Mark Word)     8 字节    │  ← 存储 hashCode、锁状态、GC 年龄
│  对象头 (Klass Pointer) 4 字节    │  ← 指向类元数据（压缩后 4 字节）
├──────────────────────────────────┤
│  item  (引用)           4 字节    │  ← 指向实际存储的元素
│  next  (引用)           4 字节    │  ← 指向下一个 Node
│  prev  (引用)           4 字节    │  ← 指向上一个 Node
├──────────────────────────────────┤
│  对齐填充 (padding)     0 字节    │  ← 24 已经是 8 的倍数，无需填充
└──────────────────────────────────┘
总计：24 字节 / 每个 Node

对比 ArrayList 存一个元素只需 4 字节（一个引用的大小）。也就是说，LinkedList 每存一个元素的额外开销是 ArrayList 的 6 倍。存储 100 万个元素时：

CPU 缓存局部性：性能差距的根源

这是 ArrayList 和 LinkedList 性能差距的最核心原因，也是工程实践中最容易被忽视的点。

现代 CPU 的缓存层级

CPU 不直接从主内存（RAM）读数据，而是通过多级缓存：

CPU 寄存器（~1 ns）
    ↓
L1 Cache（~1 ns，32-64 KB）
    ↓
L2 Cache（~4 ns，256 KB - 1 MB）
    ↓
L3 Cache（~10 ns，数 MB - 数十 MB）
    ↓
主内存 RAM（~100 ns）

CPU 每次从内存加载数据时，不是只取一个字节，而是一次取一个缓存行（cache line），通常 64 字节。

ArrayList 的缓存优势

ArrayList 的 Object[] 数组在内存中是连续存储的。一个缓存行（64 字节）可以装下 16 个引用（每个 4 字节）。当你遍历 ArrayList 时：

缓存行 1: [ref0 | ref1 | ref2 | ... | ref15]  ← 一次加载，命中 16 个元素
缓存行 2: [ref16 | ref17 | ref18 | ... | ref31]

CPU 预取器（prefetcher）会识别出"你在顺序访问连续内存"的模式，主动把后面的缓存行提前加载到缓存。结果是几乎每次访问都是缓存命中。

LinkedList 的缓存劣势

LinkedList 的 Node 对象散落在堆的各个位置。访问下一个元素时，CPU 必须：

1. 从当前 Node 的 next 字段读取下一个 Node 的引用（地址）
2. 跳转到那个地址——很可能在完全不同的内存区域
3. 缓存几乎必然不命中，需要等待 100 ns 从主内存加载

这就像翻一本书时，每翻一页都被告知"下一页在另一栋楼的某个书架上"——你大部分时间花在走路而不是阅读上。这种跳跃式的内存访问模式叫做指针追逐（pointer chasing），是缓存不友好的典型场景。

即使数据量相同、算法时间复杂度相同，缓存命中 vs 缓存不命中可以带来 10-100 倍的性能差距。

LinkedList 的"插入快"是个常见误区

中间位置插入的真实成本

很多教科书说"LinkedList 插入/删除是 O(1)"。这只对了一半——调整指针确实是 O(1)，但找到插入位置是 O(n)。

// list.add(index, element) 的源码（简化）
public void add(int index, E element) {
    if (index == size)
        linkLast(element);       // 尾部插入 O(1)
    else
        linkBefore(element, node(index));  // 先定位 + 再插入
}

// node(index)：定位第 index 个节点
Node<E> node(int index) {
    if (index < (size >> 1)) {   // 优化：如果在前半段，从头遍历
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                     // 在后半段，从尾遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

node(index) 做了一个小优化——判断 index 在前半段还是后半段，选择从 first 或 last 开始遍历。但这只是把最坏情况从 n 降到 n/2，本质仍然是 O(n)。

什么时候 LinkedList 的插入才真的是 O(1)

只有在已经持有目标节点引用的情况下，插入/删除才是 O(1)。最典型的场景是迭代器遍历时删除：

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (shouldRemove(item)) {
        it.remove();  // ← 迭代器已经持有当前节点的引用，直接调整指针，O(1)
    }
}

而 ArrayList 在同样场景下需要移动后续所有元素，是 O(n)。这是 LinkedList 唯一明显占优的场景。

ArrayList 和 Vector 的区别

Vector 的线程安全是方法级同步，粒度太粗。即使在多线程场景下，它也不是好选择——因为复合操作（如"检查 size 再 add"）仍然需要外部同步。需要线程安全的 List，有更好的选择。

CopyOnWriteArrayList：读多写少的线程安全 List

写时复制的核心思想

CopyOnWriteArrayList 的设计理念可以用一个比喻来理解：想象一块公告板，上面贴着一张通知。所有人都可以同时看这张通知（读是无锁的）。如果管理员要修改通知内容，他不会在原来的纸上涂改（那样其他人看到的是半成品），而是拿一张新纸抄一份、修改好、然后一瞬间替换掉旧的。

源码分析

public class CopyOnWriteArrayList<E> implements List<E> {

    // JDK 9+ 使用 ReentrantLock（JDK 8 用 synchronized）
    final transient ReentrantLock lock = new ReentrantLock();

    // volatile 保证读线程看到最新的数组引用
    private transient volatile Object[] array;

    // 写操作：加锁 → 复制 → 修改 → 替换引用
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);  // 复制
            newElements[len] = e;                                      // 修改
            setArray(newElements);     // volatile 写，替换数组引用
            return true;
        } finally {
            lock.unlock();
        }
    }

    // 读操作：直接读，无锁
    public E get(int index) {
        return (E) getArray()[index];
        // getArray() 返回 volatile 数组引用
        // 读到的可能是"旧快照"，但保证不会读到半写状态
    }
}

写时复制的两层保障

1. ReentrantLock 保证写-写互斥：同一时刻只有一个线程能修改数组
2. volatile 保证写-读可见性：写线程替换数组引用后，读线程能立即看到新引用

为什么读操作不需要加锁？因为读线程拿到的是一个不可变快照——旧数组一旦被替换，内容永远不会再被修改（新的修改会产生新的数组副本）。Java 中引用赋值是原子操作，所以读线程要么看到旧数组，要么看到新数组，不会看到"半新半旧"的状态。

适用场景与代价

遍历时删除元素与 fail-fast 机制

为什么 for-each 中不能直接 remove

// ❌ 抛出 ConcurrentModificationException
for (String item : list) {
    if (condition) list.remove(item);
}

这不是多线程问题——单线程也会抛。原因在于 fail-fast 机制：

// ArrayList 内部维护一个修改计数器
protected transient int modCount = 0;  // 继承自 AbstractList

// 每次 add/remove 都会 modCount++
public E remove(int index) {
    modCount++;    // ← 修改计数器 +1
    // ... 实际删除逻辑
}

// 迭代器在创建时记录当前 modCount
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;  // 快照

    public E next() {
        checkForComodification();     // 每次 next() 都检查
        // ...
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
            // modCount 被外部改过了！说明有人在迭代期间修改了结构
    }
}

当你在 for-each（本质上是 Iterator）遍历时直接调用 list.remove()，modCount 增加了，但 Iterator 的 expectedModCount 没有同步更新，下一次 next() 就会检测到不一致并抛异常。

安全删除的三种方式

// ✅ 方式一：Iterator.remove()（推荐）
// Iterator 自己的 remove() 会同步更新 expectedModCount
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) {
        it.remove();  // 内部同时更新 modCount 和 expectedModCount
    }
}

// ✅ 方式二：removeIf（JDK 8+，最简洁）
// 底层使用 BitSet 标记 + 批量移动，效率最高
list.removeIf(item -> shouldRemove(item));

// ✅ 方式三：倒序遍历删除（仅限 ArrayList）
// 删除不会影响未遍历元素的索引
for (int i = list.size() - 1; i >= 0; i--) {
    if (shouldRemove(list.get(i))) {
        list.remove(i);
    }
}

其中 removeIf 是性能最优的方案。它在内部用 BitSet 标记所有需要删除的位置，然后一次性批量移动剩余元素，避免了逐个删除时每次都要移动后续元素的 O(n²) 问题。

场景选型总结

底层认知：不要说"LinkedList 插入快"。准确的说法是：LinkedList 在已持有节点引用的情况下插入/删除是 O(1)；但在随机位置插入时，定位节点的 O(n) 遍历 + 指针追逐的缓存不命中，综合性能通常劣于 ArrayList 的数组拷贝（native memmove + 缓存命中）。