在 Java 開發中，ArrayList 與 LinkedList 是最常用的兩個 List 實作。雖然它們都實作了 List 介面，擁有相似的 API，但底層資料結構截然不同，導致在不同場景下的效能表現有天壤之別。選錯集合類型，輕則影響系統吞吐量，重則導致生產環境效能瓶頸。本文將從資料結構、時間/空間複雜度、實戰基準測試、原始碼層面深度剖析兩者差異，並給出明確的選型建議。
Object[] elementData 陣列。newCapacity = oldCapacity + (oldCapacity >> 1)（即 1.5 倍）。Node，包含 item、next、prev 三個欄位。Deque 介面，天然支援棧、佇列、雙端佇列操作（push/pop、offer/poll）。| 操作 | ArrayList | LinkedList | 說明 |
|---|---|---|---|
隨機存取 get(index)/set(index) | O(1) | O(n) | 陣列下標直達 vs 鏈表須遍歷 |
尾部新增 add(E) | O(1) 攤銷 | O(1) | 陣列偶爾擴容複製，鏈表只改尾指標 |
頭部/中間新增 add(0, E) | O(n) | O(1)（已定位節點） | 陣列需整體右移，鏈表只改指標 |
頭部/中間刪除 remove(index) | O(n) | O(1)（已定位節點） | 陣列需整體左移，鏈表只改指標 |
遍歷 for-each/iterator | 極快 | 快 | 陣列連續記憶體對 CPU 緩存友好 |
查找 indexOf/contains | O(n) | O(n) | 皆需線性掃描 |
// 50,000 有序元素，執行 50,000 次 Collections.binarySearch
ArrayList 耗時： 15 ms
LinkedList 耗時： 2596 ms // 差距 170 倍！結論：LinkedList 不實作 RandomAccess 介面，隨機存取需逐節點跳轉，極不適合二分查找、跳表等演算法。
// 50,000 次 list.add(0, new Object())
ArrayList 耗時： 2463 ms
LinkedList 耗時： 15 ms // 差距 160 倍！結論：ArrayList 每次插入都觸發 System.arraycopy 整體右移，隨著尺寸增長耗時線性上升；LinkedList 僅修改頭節點指標，耗時恆定。
ensureCapacity() 預分配、trimToSize() 釋放多餘空間。Node 物件：item + next + prev 三引用。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++;
}void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null) last = newNode;
else f.prev = newNode;
size++;
modCount++;
} CopyOnWriteArrayList 或 Collections.synchronizedList，或自行加鎖。new ArrayList<>(estimatedSize) 避免擴容開銷。ArrayList 與 LinkedList 的本質差異在於「連續記憶體 + 下標直達」對決「離散節點 + 指標跳轉」。現代硬體架構下，CPU 緩存友好的 ArrayList 在 90% 以上場景勝出。除非你確定需要高頻頭部/中間增刪、或利用其 Deque 特性，否則請毫不猶豫選擇 ArrayList。記住：先測量，再優化，盲目優化是萬惡之源。
