ArrayList 与 LinkedList 源码对比

ArrayList 和 LinkedList 是日常开发中使用频率最高的两个 List 实现，但很多人对它们的认识停留在"数组查询快、链表增删快"。这句话只在特定条件下成立。本文基于 JDK 8 与 JDK 17 的源码，从数据结构、扩容策略、内存布局和并发行为四个角度做对比，帮助你在真实业务里做出正确选型。

一、底层结构决定一切

ArrayList 的本质是一个可以动态扩容的 Object[]，元素在内存中连续存放；LinkedList 是双向链表，每个元素被包装成独立的 Node 对象，通过前后指针串联。

ArrayList（JDK 8）
elementData ──► [0][1][2][3][4][5][6][7][8][9][ ][ ]
                 ↑ size = 10，后续槽位为 null

LinkedList
first ──► [prev=null][item=A][next] ⇄ [prev][item=B][next] ⇄ [prev][item=C][next=null] ◄── last

ArrayList 的关键字段非常少：

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

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // 真正存数据的数组
    private int size;               // 元素个数，不是数组长度
    protected transient int modCount; // 结构修改次数，用于 fail-fast
}

注意 size 与 elementData.length 是两个概念：容量是数组长度，size 是有效元素个数。ArrayList 在 JDK 8 中采用懒初始化，new ArrayList<>() 并不会立刻分配 10 个槽位，而是先指向共享的空数组，第一次 add 时才真正分配。

LinkedList 的节点定义如下，一个节点包含三个引用：

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

在 64 位 HotSpot 开启压缩指针的情况下，一个 Node 的对象头约 12 字节，三个引用占 12 字节，对齐后约 24 字节；而 ArrayList 每个槽位只占 4 字节引用。同样是存 100 万个 Integer，LinkedList 仅节点结构就要多消耗约 20 MB，这还没有算上节点分散带来的缓存不友好。

二、ArrayList 的扩容与搬移

add(E e) 先确保容量，再在尾部写入：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 检查是否需要扩容
    elementData[size++] = e;
    return true;
}

扩容发生在 grow 中，JDK 8 的策略是旧容量的 1.5 倍：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;                      // 至少满足本次需求
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Arrays.copyOf 底层是 System.arraycopy，属于 native 方法，会一次性申请新数组并整体复制。扩容是 O(n) 操作，但按 1.5 倍增长，均摊到每次 add 仍是 O(1)。JDK 17 把这段逻辑换成了 ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1)，增长因子不变，只是把溢出判断封装进了工具类。

在中间插入或删除时，ArrayList 必须搬移后续元素：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // 置空，帮助 GC
    return oldValue;
}

删除时把末尾槽位置为 null 是一个容易被忽略的细节：如果不置空，数组仍然强引用被删除的对象，造成对象无法回收。源码已经替你做了，但自己写类似结构时要记得。

为什么扩容是 1.5 倍而不是 2 倍

扩容因子越大，扩容次数越少，但浪费的空间越多。取 2 倍时，新数组总是比历史分配总和还大，前面释放的旧数组空间很难被后续扩容复用；取 1.5 倍时，新容量约等于之前若干次容量之和，堆上的空闲块有机会被重新利用。代价是扩容次数略多，但由于是均摊 O(1)，总复制量仍在可接受范围。这是空间利用率与复制开销之间的折中，也是 ArrayList 在长期运行的服务里表现稳定的原因之一。

另外，ArrayList 的序列化并不直接写出 elementData。它实现了私有的 writeObject，只写 size 和有效元素，避免把容量中大量 null 槽位也写进流里。反序列化时用 readObject 重建数组，并把 size 作为新的容量起点。这也是 elementData 被标记为 transient 的原因。

三、LinkedList 的定位与改链

LinkedList 的 get(int index) 并不是 O(1)，它需要从头或尾遍历：

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

源码用 size >> 1 做了一次优化，最多遍历一半，但复杂度仍是 O(n)。所以在 LinkedList 上写 for (int i = 0; i < list.size(); i++) list.get(i)，整体会退化为 O(n²)，这是最常见的性能事故之一。

尾部追加只需修改三个指针：

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

删除节点同样只改指针，但前提是已经拿到了节点。通过 remove(Object o) 删除时，仍然要先从头遍历找到节点，因此整体还是 O(n)。

四、复杂度与内存对比

| 操作 | ArrayList | LinkedList |

| --- | --- | --- |

| get(i) 随机访问 | O(1) | O(n) |

| 尾部 add(e) | 均摊 O(1)，扩容时 O(n) | O(1) |

| 头部 add(0, e) | O(n) | O(1) |

| 中间插入/删除 | O(n) 搬移 | O(n) 定位 + O(1) 改链 |

| 迭代器顺序遍历 | 快，连续内存 | 慢，指针跳转、缓存不命中 |

| 单元素内存开销 | 约 4 字节（压缩指针） | 约 24 字节 |

| 是否实现 RandomAccess | 是 | 否 |

RandomAccess 是一个空标记接口，Collections.binarySearch、List.subList 等工具会据此选择遍历方式。LinkedList 没有实现它，正是因为随机访问代价高。

结论很明确：绝大多数场景选 ArrayList。只有在"已经持有节点位置、需要频繁在头部插入删除"时，LinkedList 才有优势，而这类需求通常用 ArrayDeque 更合适，它同样是双端队列，但底层是环形数组，内存和缓存表现都更好。

五、并发场景分析

两个类都不是线程安全的。ArrayList 的 add 中 size++ 是"读-改-写"三步，并发执行会丢失元素，甚至出现 null 槽位。LinkedList 的 linkLast 修改 last、l.next、size 多个字段，并发下可能形成结构错乱。

ArrayList 的迭代器采用 fail-fast：每次 next() 检查 modCount 是否等于创建迭代器时记录的 expectedModCount，不等就抛 ConcurrentModificationException。

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
for (String s : list) {
    if ("b".equals(s)) {
        list.remove(s); // 抛出 ConcurrentModificationException
    }
}

正确写法是使用迭代器自身的 remove，或 JDK 8 的 removeIf：

list.removeIf("b"::equals);

如果需要并发容器，读多写少用 CopyOnWriteArrayList，它在写时复制整个数组，读操作完全无锁，代价是写开销大、内存瞬时翻倍；读写均衡则用 Collections.synchronizedList，但迭代时仍要手动对列表加锁。

六、常见坑 / 最佳实践

1. 预估容量。能估算元素数量时使用 new ArrayList<>(expectedSize)，避免多次扩容复制。注意构造参数是容量而不是元素个数，传负数会抛 IllegalArgumentException。
2. 不要用 get(i) 遍历 LinkedList。改用增强 for 或迭代器，否则复杂度从 O(n) 退化到 O(n²)。
3. Arrays.asList 返回的是固定长度视图。add、remove 会抛 UnsupportedOperationException，需要可变列表时用 new ArrayList<>(Arrays.asList(...))。List.of 返回的是不可变集合，连 set 都不允许。
4. subList 是视图不是拷贝。对原列表做结构性修改后，子列表的任何操作都可能抛 ConcurrentModificationException。
5. 遍历中删除用 Iterator.remove 或 removeIf，不要直接调用列表的 remove。
6. ArrayList 不是线程安全的。多线程写场景优先 CopyOnWriteArrayList 或加锁，不要寄希望于 Collections.synchronizedList 自动解决迭代问题。

七、小结

• ArrayList 底层是连续数组，随机访问 O(1)，扩容 1.5 倍，中间增删需要 System.arraycopy 搬移。
• LinkedList 底层是双向链表，头尾增删 O(1)，但定位是 O(n)，每个节点有约 24 字节额外开销。
• 顺序遍历和随机访问场景选 ArrayList；需要双端队列时选 ArrayDeque，而不是 LinkedList。
• 两者都非线程安全，ArrayList 的迭代器 fail-fast 只是错误检测机制，不是同步手段。
• 预估容量、避免 get(i) 遍历链表、用 removeIf 安全删除，是最实用的三条实践。