| 特性 | ArrayList | LinkedList |
|---|---|---|
| 資料結構 | 動態陣列 | 雙向鏈表 |
| 記憶體佈局 | 連續記憶體區塊 | 分散節點，每節點含 prev/next 引用 |
| 擴容機制 | 1.5 倍 (舊容量 + 右移 1 位) | 無擴容，按需分配節點 |
| 預設初始容量 | 10 | 無 (空鏈表) |
| 操作 | ArrayList | LinkedList | 說明 |
|---|---|---|---|
隨機存取 get(index) | O(1) | O(n) | 陣列直接定址 vs 鏈表遍歷 |
尾部新增 add(e) | 均攤 O(1) | O(1) | 陣列偶爾擴容複製 |
| 頭部/中間新增 | O(n) | O(1)* | * 需先定位節點，實際常退化為 O(n) |
| 頭部/中間刪除 | O(n) | O(1)* | 同上 |
搜尋 indexOf/contains | O(n) | O(n) | 皆需線性掃描 |
| 迭代器遍歷 | 極快 (CPU 緩存友好) | 較慢 (指針跳躍) | 連續記憶體預取優勢巨大 |
Object[] elementData + int size → 每元素 1 引用 (4/8 bytes)Node<E> { E item; Node<E> next, prev; } → 每元素 3 引用 + 物件頭Integer，ArrayList ≈ 16 MB，LinkedList ≈ 40 MB+// 100 萬次尾部新增
ArrayList: 12 ms (擴容 3-4 次)
LinkedList: 18 ms (新增 100 萬 Node 物件)
// 100 萬次隨機 get
ArrayList: 3 ms
LinkedList: 850 ms (每次從頭/尾遍歷)
// 10 萬次頭部插入
ArrayList: 450 ms (每次 System.arraycopy 位移)
LinkedList: 4 ms (只改 head 指針)需要頻繁隨機存取 (get/set by index)？
├─ 是 → ArrayList
└─ 否
需頻繁頭部/中間增刪？
├─ 是 → LinkedList (或考慮 ArrayDeque)
└─ 否
記憶體敏感 / 遍歷為主？
├─ 是 → ArrayList
└─ 否 → ArrayList (預設首選)// ArrayList 擴容核心 (JDK 17)
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x
if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
// LinkedList 節點定義
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; this.next = next; this.prev = prev;
}
}🎯 90% 場景用 ArrayList：連續記憶體、CPU 緩存友好、隨機存取 O(1)、記憶體省
🔧 LinkedList 專用場景：極高頻頭部/中間增刪、雙端隊列語義、不需隨機存取
⚡ 單執行緒雙端隊列首選 ArrayDeque：效能更好、記憶體更省
