ArrayList 核心原理與擴容機制深度解析

ArrayList 是基於動態數組實現的 List 接口，以隨機訪問快、記憶體緊湊著稱。本文深入剖析其擴容策略、核心方法實現及性能特徵，助力開發者做出正確選型與調優決策。

一、核心屬性與構造方法

// 默認初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空數組實例(延遲初始化用)
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 共享空數組實例
private static final Object[] EMPTY_ELEMENTDATA = {};

transient Object[] elementData; // 非序列化
private int size;

二、擴容機制：grow() 核心邏輯

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 1.5 倍擴容：oldCapacity + oldCapacity >> 1
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 新容量仍不夠，直接按需求分配
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 超過最大數組限制處理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // Arrays.copyOf 實現數組複製擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

關鍵點：

• 1.5 倍增長：比 2 倍更節省內存，減少大數組分配失敗風險
• System.arraycopy / Arrays.copyOf：native 實現，極快
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8：留出對象頭空間

三、核心方法實現剖析

3.1 add(E e) - 尾部添加

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 檢查擴容
    elementData[size++] = e;          // 賦值並 size++
    return true;
}

時間複雜度：攤還 O(1)，極少數觸發擴容時為 O(n)。

3.2 get(int index) / set(int index, E element) - 隨機訪問

public E get(int index) {
    rangeCheck(index);              // 邊界檢查
    return elementData(index);      // 直接下標訪問
}

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;   // 直接覆蓋
    return oldValue;
}

時間複雜度：O(1)，ArrayList 最大優勢。

3.3 add(int index, E element) - 指定位置插入

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    // 將 index 及之後元素向後移動一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

時間複雜度：O(n)，需移動後續元素。越靠前插入，移動元素越多。

3.4 remove(int index) - 指定位置刪除

public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 將 index+1 及之後元素向前移動一位
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null; // 清除引用，助 GC
    return oldValue;
}

時間複雜度：O(n)，同理需移動元素。

四、性能特徵總結表

五、實戰避坑指南

1. 預估大小：已知大致數據量時，使用 new ArrayList<>(estimatedSize) 避免多次擴容與數組複製
2. 避免頭部插刪：頻繁頭部操作請改用 LinkedList 或 ArrayDeque
3. 遍歷刪除：使用 Iterator.remove() 或反向循環，避免 ConcurrentModificationException 或索引錯位
4. trimToSize()：大量刪除後調用，釋放未使用的數組空間
5. 序列化：elementData 標記 transient，序列化時只寫入實際元素，反序列化重建數組，節省空間

六、ArrayList vs LinkedList 選型決策

隨機訪問多、尾部增刪多、數據量可預估  → ArrayList
頻繁頭部/中間增刪、不可預估大小、需隊列/棧語義 → LinkedList / ArrayDeque