Java List 總結：ArrayList、LinkedList、Vector、Stack 性能實測與選型指南

List 作為有序集合的核心接口，其四大實現類 ArrayList、LinkedList、Vector、Stack 在底層結構、性能特徵、線程安全性上差異顯著。本文通過源碼級原理分析與百萬級基準測試，給出清晰的選型決策依據。

一、List 體系速覽

Collection
   ↑
  List (Interface)
   ↑
AbstractList (Abstract Class)
   ↑           ↑
ArrayList   Vector
               ↑
             Stack
   ↑
AbstractSequentialList
   ↑
LinkedList

• ArrayList：動態數組，隨機訪問 O(1)，插刪 O(n)，非線程安全。
• LinkedList：雙向鏈表，隨機訪問 O(n)，首尾插刪 O(1)，實現 Deque，非線程安全。
• Vector：同步動態數組，API 皆 synchronized，線程安全但性能較差。
• Stack：繼承 Vector，LIFO 棧，push/pop/peek 委託數組末尾操作。

二、百萬級基準測試實測（JDK 8，10 萬次操作）

結論：

• 頻繁頭部/中間插刪 → LinkedList 碾壓級優勢。
• 高頻隨機訪問/尾部追加 → ArrayList 極致性能。
• Vector/Stack 因同步開銷，單線程下性能與 ArrayList 持平但無優勢；多線程下建議改用 Collections.synchronizedList 或 CopyOnWriteArrayList。

三、源碼級性能差異根因分析

3.1 插入/刪除：數組搬移 vs 鏈表指針調整

// ArrayList.add(index, e) 核心
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 必須將 index 之後所有元素向後挪一位 → O(n)

// LinkedList.add(index, e) 核心
Entry<E> newEntry = new Entry<>(e, successor, predecessor);
predecessor.next = newEntry;
successor.previous = newEntry;
// 僅修改前後節點指針 → O(1) 定位後（定位本身 O(n/2)）

3.2 隨機訪問：下標直達 vs 雙向查找

// ArrayList.get(index)
return (E) elementData[index];  // 直接下標 → O(1)

// LinkedList.get(index)
Entry<E> e = header;
if (index < (size >> 1)) { for (i=0; i<=index; i++) e = e.next; }
else { for (i=size; i>index; i--) e = e.previous; }
return e.element;  // 需遍歷鏈表 → O(n)

LinkedList 優化：索引 < size/2 從頭向後，否則從尾向前，但仍屬線性級。

3.3 擴容策略差異

四、Vector vs ArrayList 核心差異

五、Vector 遍歷效率實測（10 萬元素）

iteratorThroughRandomAccess：6 ms   // 下標訪問最快
iteratorThroughEnumeration：7 ms
iteratorThroughFor2：8 ms
iteratorThroughIterator：9 ms      // 迭代器最慢

建議：Vector 優先使用下標隨機訪問遍歷。

六、選型決策樹

1. 需要棧/隊列/雙端隊列語義 → 直接用 ArrayDeque（非線程安全）或 LinkedList（實現 Deque），勿用 Stack/Vector。
2. 高頻隨機訪問、尾部追加、單線程 → ArrayList。
3. 高頻頭部/中間插刪、單線程 → LinkedList。
4. 多線程並發讀寫 → CopyOnWriteArrayList（讀多寫少）或 Collections.synchronizedList(new ArrayList())（寫多）。
5. 遺留代碼維護 → 理解 Vector/Stack 同步特性，新代碼禁用。

七、最佳實踐清單

• 預估數據量 → 構造函數指定 initialCapacity 減少擴容。
• 僅需遍歷只讀 → for (E e : list) 或 list.forEach()。
• 需在遍歷中刪除 → 僅用 Iterator.remove()，避免 ConcurrentModificationException。
• 多線程環境 → 優先選用 java.util.concurrent 包下並發集合。
• 避免在 LinkedList 中使用 get(index)/set(index) 進行批量隨機訪問。