Java 集合框架是處理物件群組的核心 API。本文系統梳理 Collection 體系架構，並深度剖析 ArrayList 與 LinkedList 的底層資料結構、核心方法實作與效能特徵，助你做出正確選型。
Iterable (根介面)
└── Collection
├── List 有序、可重複
│ ├── ArrayList
│ ├── LinkedList
│ └── Vector (舊)
├── Set 無序、唯一
│ ├── HashSet
│ ├── LinkedHashSet
│ └── TreeSet
└── Queue 佇列
├── PriorityQueue
└── Deque (雙端佇列)
Map** 不繼承 Collection，另成體系。
Object[] elementData 儲存元素。| 方法 | 時間複雜度 | 說明 |
|---|---|---|
| get(int index) | O(1) | 下標直接存取，極快 |
| set(int index, E) | O(1) | 下標直接替換，極快 |
| add(E) | 均攤 O(1) | 尾端新增，偶爾觸發擴容複製 |
| add(int index, E) | O(n) | 需移動 index 後所有元素 |
| remove(int index) | O(n) | 需移動 index 後所有元素 |
| remove(Object) | O(n) | 線性查找 + 移動元素 |
| indexOf(Object) | O(n) | 線性查找 |
prev、next、item 三欄位。Node<E> (JDK 8 以前稱 Entry)。first、last 指標與 size 計數。| 方法 | 時間複雜度 | 說明 |
|---|---|---|
| get(int index) | O(n) | 需從頭/尾遍歷至索引位置 |
| set(int index, E) | O(n) | 需先定位節點 |
| add(E) | O(1) | 尾端插入，僅調整指標 |
| add(int index, E) | O(n) | 需定位插入點，但無元素移動 |
| remove(int index) | O(n) | 需定位節點，僅調整指標 |
| remove(Object) | O(n) | 查找 + 調整指標 |
| addFirst/addLast | O(1) | 首/尾插入，極快 |
| removeFirst/removeLast | O(1) | 首/尾移除，極快 |
new ArrayList<>(initialCapacity) 避免多次擴容。Collections.synchronizedList() 或 CopyOnWriteArrayList / 併發佇列。List.of() 建立不可變列表。ArrayList 以動態陣列實現，隨機存取 O(1) 但插刪 O(n)；LinkedList 以雙向鏈表實現，插刪 O(1) 但隨機存取 O(n)。理解底層機制，依據存取模式選型，是寫出高效 Java 程式的關鍵。
