ArrayList vs LinkedList 效能實測與選型指南

ArrayList vs LinkedList 效能實測與選型指南

兩者皆實作 List 介面，但底層資料結構截然不同，導致適用場景大相逕庭。本文結合源碼分析與基準測試數據，給出明確選型建議。

底層實現差異

ArrayList：動態陣列

• 底層：Object[] elementData
• 預設容量：10，最大 Integer.MAX_VALUE
• 擴容機制：1.5 倍 (oldCapacity + (oldCapacity >> 1))
• 隨機存取：O(1) — 透過索引直接定位

LinkedList：雙向鏈表

• 底層：Node<E> 內部類，含 prev、next、item
• 無容量限制 (受限於記憶體)
• 頭/尾操作 O(1)，中間操作 O(n) 需遍歷
• 實作 Deque 介面，可作堆疊/佇列 (但效能不如 ArrayDeque)

基準測試數據對比 (JMH 風格簡化測試)

尾部插入

兩者差異不大，ArrayList 略勝 (無節點物件分配、無指標維護)。

預設容量 vs 指定初始容量

ArrayList 一次性指定容量可避免擴容複製，**效能提升 ~50%**。

頭部插入

LinkedList 完勝：只需修改頭節點指標。ArrayList 需整體右移，O(n)。

隨機存取 (get/set)

ArrayList O(1) 碾壓 LinkedList O(n/2) (雙向遍歷優化)。

選型決策表

核心結論

90% 以上場景首選 ArrayList。只有確定「高頻頭部/中間插刪且資料量大」時才考慮 LinkedList。現代 JVM 對陣列複製高度優化，鏈表的指標追蹤反而不利於 CPU 預取與快取。