ArrayList 核心源碼深度解析：動態數組實現原理

概述

ArrayList 是基於動態數組實現的 List 接口，支援隨機訪問、自動擴容、允許 null 元素，但非線程安全。每個實例擁有 capacity（底層數組長度），始終 ≥ size（元素個數）。

核心字段

private transient Object[] elementData; // transient 避免序列化空槽位
private int size;

三種構造方式

1. 無參：初始容量 10（new Object[10]）
2. 指定容量：new Object[initialCapacity]，負數拋異常
3. 集合轉換：c.toArray()，若非 Object[] 則 Arrays.copyOf 轉型

核心操作源碼解析

讀取 get(index) - O(1)

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];
}

修改 set(index, element) - O(1)

public E set(int index, E element) {
    rangeCheck(index);
    E old = (E) elementData[index];
    elementData[index] = element;
    return old;
}

尾部添加 add(E e) - 平均 O(1)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

指定位置插入 add(index, element) - O(n)

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

批量添加 addAll

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

刪除 remove(index) - O(n)

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E old = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // GC 友好
    return old;
}

按對象刪除 remove(Object o) 需遍歷查找，同樣涉及數組左移。

擴容機制 ensureCapacity

public void ensureCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
        if (newCapacity < minCapacity) newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

最佳實踐：預知數據量時用構造函數或 ensureCapacity 預分配，避免頻繁擴容拷貝。

縮容 trimToSize()

public void trimToSize() {
    modCount++;
    if (size < elementData.length)
        elementData = Arrays.copyOf(elementData, size);
}

Fail-Fast 機制

通過 modCount 記錄結構性修改次數。迭代器創建時記錄 expectedModCount，操作前比對，不一致拋 ConcurrentModificationException。

總結

高頻增刪場景建議改用 LinkedList。