ArrayList vs LinkedList 深度效能對比
兩者皆實作 List 介面，底層結構不同導致效能特性迥異。本文實測 1000 萬筆資料，分析各操作在不同位置的表現。
一、底層結構差異
| 特性 | ArrayList | LinkedList |
|---|
| 結構 | 動態陣列 | 雙向鏈表 |
| 隨機存取 | O(1) | O(n) |
| 記憶體 | 連續，擴容需複製 | 分散，節點額外指標開銷 |
| 擴容機制 | 1.5 倍 | 無 |
二、實測結果摘要（1000 萬筆）
1. 新增
- 尾部新增：ArrayList < LinkedList（ArrayList 僅賦值，LinkedList 需建節點、修改指標）
- 指定索引插入：ArrayList 需搬移元素，LinkedList 需遍歷到位置
2. 查詢
| 方法 | ArrayList | LinkedList | 差異 |
|---|
| get(index) | 極快 (O(1)) | 慢 (O(n))，索引越後越慢 | 數量級差距 |
| contains / indexOf / lastIndexOf | 快 | 較慢 | ArrayList 優 |
3. 刪除
| 方法 | ArrayList | LinkedList |
|---|
| remove(last) | 極快 | 快 |
| remove(first/middle) | 需搬移後續元素 | 需遍歷到節點 |
| remove(Object) | 慢（先查找再搬移） | 極慢（查找+指標修改），但實測 LinkedList 更差 |
三、位置影響詳細分析
插入位置
- ArrayList：越靠近尾部越快（搬移元素少），頭部最慢
- LinkedList：頭部最快（O(1)），尾部次之（有尾指標），中間最慢（雙向遍歷較近端）
查詢位置
- ArrayList：位置無關，恆 O(1)
- LinkedList：索引越大越慢，中間約 n/2 步
刪除位置
- ArrayList：尾部 O(1)，頭部/中間 O(n) 搬移
- LinkedList：頭部 O(1)，尾部 O(1)（有尾指標），中間 O(n)
四、選擇指南
| 場景 | 推薦 | 理由 |
|---|
| 頻繁隨機存取、遍歷 | ArrayList | CPU 緩存友好、O(1) 存取 |
| 頻繁頭部/中間插入刪除 | LinkedList | 無搬移開銷 |
| 佇列/棧 | LinkedList / ArrayDeque | Deque 介面支援 |
| 不確定/通用 | ArrayList | 多數場景更優、記憶體較省 |
五、現代替代方案
- 高效能佇列：
ArrayDeque（非同步）、ConcurrentLinkedQueue
- 大量資料：考慮陣列、
IntList (Eclipse Collections) 避免裝箱
