深度解析：為何頻繁插入刪除應選 LinkedList 而非 ArrayList

核心結論先行

頻繁在列表頭部/中間插入、刪除元素時，LinkedList 效能遠優於 ArrayList（可達 40-50 倍）；但隨機存取（get/set）與尾部新增（add(E)）場景下，ArrayList 更優。選型需根據業務寫操作分佈決策。

底層資料結構差異

源碼級效能分析

ArrayList 插入機制

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // 1. 檢查擴容
    System.arraycopy(elementData, index, elementData, index + 1, size - index); // 2. 核心搬移：將 index 及之後元素向後複製一位
    elementData[index] = element;      // 3. 賦值
    size++;
}

痛點：System.arraycopy 雖為 Native 優化，但每次插入都需搬移 size - index 個元素。頭部插入（index=0）搬移全陣列，尾部插入（index=size）搬移 0 元素。頻繁頭部/中間插入導致大量記憶體複製與 GC 壓力。

LinkedList 插入機制

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);      // 尾部新增優化
    else
        linkBefore(element, node(index)); // 中間/頭部插入
}

void linkBefore(E e, Node succ) {
    final Node pred = succ.prev;
    final Node newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

優勢：僅建立新節點、修改 prev/next 兩個指標，無陣列搬移，時間複雜度固定 O(1)（不含定位節點的 O(n) 遍歷）。

刪除操作對比

// ArrayList.remove(int index)
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved); // 搬移
elementData[--size] = null; // 釋放引用

// LinkedList.unlink(Node x)
E element = x.item;
Node next = x.next, prev = x.prev;
if (prev == null) first = next; else prev.next = next;
if (next == null) last = prev; else next.prev = prev;
x.item = null; x.next = null; x.prev = null; // GC 友善
size--;
modCount++;
return element;

同理，ArrayList 需搬移後續元素填補空缺；LinkedList 僅斷開重連指標。

修改操作：ArrayList 完勝

// ArrayList.set(int index, E element) - O(1)
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;

// LinkedList.set(int index, E element) - O(n)
Node x = node(index); // 折半遍歷定位
E oldVal = x.item;
x.item = element;
return oldVal;

LinkedList 修改元素需先遍歷定位節點（node(index) 採雙向折半遍歷），大量修改時效能遠遜於 ArrayList 的直接下標賦值。

實測數據參考

測試環境：JDK 1.8、Intel i7、10 萬筆資料、循環 1000 次取平均

選型決策樹

1. 唯讀/極少寫、大量隨機存取 → ArrayList
2. 頻繁頭部/中間插入刪除（佇列、棧、事件總線、緩衝區） → LinkedList
3. 僅尾部新增、偶爾中間插入 → ArrayList（預設首選）
4. 需併發安全 → 考慮 CopyOnWriteArrayList（讀多寫少）或 ConcurrentLinkedQueue（高併發佇列）
5. 不確定時 → 先用 ArrayList，效能瓶頸出現再針對性優化

常見誤區澄清

• 誤區：「LinkedList 適合佇列」→ 正確：實作 Deque 介面，offer/poll 為 O(1)，確實適合佇列/棧
• 誤區：「LinkedList 記憶體佔用小」→ 錯誤：每個節點額外 3 個引用，32 位 JVM 單節點開銷約 24 bytes，大量小對象時記憶體佔用反而更大
• 誤區：「ArrayList 擴容慢」→ 部分正確：擴容為摊還 O(1)，預估大小用 ensureCapacity 或建構子指定初始容量可避免

總結

ArrayList 與 LinkedList 的本質權衡是 「空間換時間」（陣列連續記憶體換取 O(1) 隨機存取）與 「時間換空間」（鏈表離散節點換取 O(1) 插入刪除）。實務中 90% 以上場景 ArrayList 為優先選擇，僅在明確存在高頻頭部/中間寫操作時才考慮 LinkedList。切記：過早優化是萬惡之源，先測量再決策。