核心差異總覽
| 特性 | 靜態陣列 | ArrayList | Vector | LinkedList |
| 大小 | 固定,宣告時決定 | 動態擴容 | 動態擴容 | 動態,鏈式結構 |
| 元素類型 | 基本型別或具體引用型別 | Object(泛型擦除後) | Object | Object |
| 同步/線程安全 | 否 | 否 | 是(方法級 synchronized) | 否 |
| 隨機訪問 get(i) | O(1) | O(1) | O(1) | O(n) |
| 尾部增刪 | 不可變 | O(1) 攤還 | O(1) 攤還 | O(1) |
| 中間增刪 | 不可變 | O(n) 需搬移 | O(n) 需搬移 | O(1) 僅改指針 |
| 記憶體開銷 | 最小 | 預留空間 1.5 倍 | 預留空間 2 倍 | 每節點額外 2 指針 |
原理深度剖析
ArrayList / Vector:動態陣列
- 底層
Object[] elementData
- 擴容機制:
- ArrayList:
newCapacity = oldCapacity + (oldCapacity >> 1)(1.5 倍)
- Vector:
newCapacity = oldCapacity * 2(2 倍),可指定增量
- 插入/刪除需
System.arraycopy 搬移後續元素
LinkedList:雙向鏈表
- 節點結構:
Node { E item; Node next; Node prev; }
- 頭尾指針
first/last,尾部增刪極快
- 索引訪問需從頭/尾遍歷,
index < size/2 從頭,否則從尾
同步性選擇指南
// 單執行緒 / 手動同步:ArrayList(效能最佳)
List list = new ArrayList<>();
// 多執行緒讀多寫少:Collections.synchronizedList(new ArrayList<>())
// 或 CopyOnWriteArrayList(寫入複製,讀取無鎖)
// 多執行緒寫入頻繁:Vector(舊 API)或 ConcurrentLinkedQueue / CopyOnWriteArrayList
// 注意:Vector 方法級同步無法保證複合操作原子性(如 check-then-act)
List syncList = Collections.synchronizedList(new ArrayList<>());
synchronized(syncList) { // 複合操作需額外同步
if (!syncList.contains("x")) syncList.add("x");
}
效能基準參考(百萬級數據)
| 操作 | ArrayList | LinkedList | Vector |
| 順序添加 100 萬 | ~15ms | ~25ms | ~30ms |
| 隨機訪問 100 萬次 | ~5ms | ~2500ms | ~5ms |
| 頭部插入 1 萬次 | ~800ms | ~2ms | ~900ms |
| 中間插入 1 萬次 | ~400ms | ~1200ms | ~450ms |
| 記憶體佔用 (100 萬 Integer) | ~16 MB | ~40 MB | ~18 MB |
數據僅供參考,實際受 JVM、GC、硬體影響。
選型決策樹
需要固定大小、極致效能、基本型別? → 陣列 (int[], byte[] 等)
需要動態大小、頻繁隨機訪問、尾部增刪? → ArrayList
需要頻繁頭部/中間增刪、不需隨機訪問? → LinkedList
多執行緒環境、簡單同步需求? → Collections.synchronizedList / Concurrent 包
舊版 API 相容、不介意效能? → Vector
避坑指南
- 指定初始容量:
new ArrayList<>(10000) 避免多次擴容拷貝
- 勿在循環中刪除 ArrayList 元素:用
Iterator.remove() 或反向循環
- LinkedList 不適合隨機訪問:
for (int i=0; i<list.size(); i++) list.get(i) 是 O(n²) 災難
- Vector 已過時:新代碼優先用
ArrayList + 顯式同步或 java.util.concurrent