深度解析 ArrayList 與 LinkedList 源碼：核心機制與性能抉擇

前言：List 接口的兩大支柱

在 Java 集合框架中，List 接口繼承自 Collection，定義了有序、可重複的數據結構規範。其核心實現類 ArrayList 與 LinkedList 雖然同樣實現了 List 接口，但底層數據結構截然不同，導致它們在不同場景下的性能表現有天壤之別。本文將深入源碼，剖析兩者的擴容、增刪改查、迭代器等核心機制，助你做出正確的技術選型。

一、ArrayList：動態數組的藝術

1. 核心字段與構造器

ArrayList 內部維護一個 transient Object[] elementData 數組與 int size 字段。transient 關鍵字意味著序列化時不直接持久化數組，而是通過 writeObject/readObject 自定義序列化邏輯，節省空間。

三個構造器分別支持：指定初始容量、默認容量（10）、從集合初始化。特別注意第三個構造器中對 c.toArray() 返回類型的防禦性檢查——因為泛型擦除與數組協變特性，List<String>.toArray() 可能返回 String[] 而非 Object[]，直接賦值會導致運行時 ArrayStoreException，源碼通過 Arrays.copyOf 強制轉型為 Object[] 規避風險。

2. 擴容機制：1.5 倍增長策略

ensureCapacity(int minCapacity) 是擴容入口。當容量不足時，新容量 = oldCapacity * 3 / 2 + 1（即 1.5 倍 + 1），若仍不足則直接使用 minCapacity。隨後調用 Arrays.copyOf 複製數組。此過程涉及內存分配、數組複製，頻繁觸發會嚴重影響性能，因此預估數據量時應指定初始容量。

3. 核心操作源碼解析

• 添加元素：add(E e) 尾插 O(1) 摊還；add(int index, E element) 需 System.arraycopy 後移元素，O(n)。
• 刪除元素：remove(int index) / remove(Object o) 均需前移後續元素並將末位置 null 釋放引用，O(n)。
• 查找元素：get(int index) 數組下標直接訪問 O(1)；indexOf/lastIndexOf 線性掃描 O(n)，區分 null 用 ==，非 null 用 equals。
• 修改元素：set(int index, E element) 直接覆蓋 O(1)。

4. 迭代器與 Fail-Fast 機制

內部類 Itr 實現 Iterator，通過 expectedModCount == modCount 判斷並發修改。modCount 在結構性修改（增/刪）時遞增，迭代過程中若檢測到不一致，拋出 ConcurrentModificationException，實現「快速失效」。

5. trimToSize() 與最佳實踐

刪除元素不會自動縮容，調用 trimToSize() 可將容量縮減至 size，釋放閒置內存。總結：頻繁隨機訪問、少量增刪選 ArrayList；大量頭尾增刪、少量隨機訪問選 LinkedList。

二、LinkedList：雙向鏈表的靈動

1. 節點結構與哨兵節點

靜態內部類 Entry<E>（JDK 1.6 稱 Node）包含 element、next、previous 三字段。header 哨兵節點 element=null，next=previous=header 形成閉環，簡化邊界判斷。

2. 添加操作：指針重組的藝術

核心私有方法 addBefore(E e, Entry<E> entry)：創建新節點 newEntry，將其 previous 指向 entry.previous，next 指向 entry；再修改前驅節點的 next 與 entry 的 previous 指向 newEntry。所有公開添加方法（addFirst、addLast、add(index, element)、addAll）均委派給此方法，O(1) 完成插入（不計查找位置時間）。

3. 刪除操作：斷鏈重聯

remove(Entry<E> e) 僅需修改前驅節點的 next 指向後繼、後繼節點的 previous 指向前驅，並將被刪節點字段置 null 釋放引用，O(1)（不計查找時間）。clear() 遍歷斷鏈並重置 header 閉環。

4. 查找與索引優化

get(int index)、indexOf、lastIndexOf 均需遍歷。entry(int index) 採用「雙向查找優化」：index < size/2 從頭向後，否則從尾向前，平均遍歷長度減半。

5. ListIterator：雙向游標的完整實現

ListItr 實現 ListIterator，維護 lastReturned、next、nextIndex，支持雙向遍歷、add/set/remove 修改操作，同樣通過 expectedModCount 實現 Fail-Fast。

6. 線程安全性與適用場景

兩者均非線程安全。多線程環境下可用 Collections.synchronizedList 包裝，或選用 CopyOnWriteArrayList（讀多寫少）、ConcurrentLinkedQueue 等並發容器。

三、性能對比與選型指南

經驗法則：默認優先 ArrayList；明確涉及大量頭/尾/中間插刪、或作為隊列/棧（Deque 接口）時選 LinkedList。