線性表是最基礎的資料結構之一，Java Collection 框架提供了豐富的介面與實作。本文從 ADT 理論、邏輯定義、Java 介面設計、到具體實作類別（ArrayList、LinkedList）與最佳實務，完整解析線性表在 Java 中的體現。
線性表是 n (n≥0) 個資料元素組成的有限序列：(a₁, a₂, ..., aₙ)
n=0：空表a₁：無直接前驅，僅有後繼 a₂aₙ：無直接後繼，僅有前驅 aₙ₋₁aᵢ (2≤i≤n-1)：唯一前驅 aᵢ₋₁、唯一後繼 aᵢ₊₁java.lang.Iterable ↑ java.util.Collection (介面) ← 根介面，基本操作：add, remove, contains, size, iterator() ↑ java.util.List (介面) ← 有序、可重複、支援索引存取 ↑ ├── java.util.ArrayList ← 動態陣列，隨機存取快，尾部增刪快 ├── java.util.LinkedList ← 雙向鏈表，首尾增刪快，循序存取 ├── java.util.Vector ← 同步化舊類別，不建議新專案使用 ├── java.util.Stack ← Vector 子類，LIFO，建議用 Deque/ArrayDeque └── java.util.concurrent.CopyOnWriteArrayList ← 讀多寫少並發場景
| 分類 | 方法 | 說明 |
|---|---|---|
| 索引存取 | get(int index) | 取得指定位置元素 |
set(int index, E element) | 替換指定位置元素 | |
add(int index, E element) | 插入元素，後續元素右移 | |
remove(int index) | 移除指定位置元素，回傳被移除值 | |
| 搜尋 | indexOf(Object o) | 首次出現索引，無則 -1 |
lastIndexOf(Object o) | 最後出現索引 | |
contains(Object o) | 是否包含 (equals 比較) | |
| 迭代器 | iterator() | 單向 Iterator，支援 remove() |
listIterator() | 雙向 ListIterator，支援 add/set/previous/hasPrevious |
| 操作 | ArrayList | LinkedList | 備註 |
|---|---|---|---|
| 隨機存取 get/set | O(1) ⭐ | O(n) | 陣列直接定址 vs 鏈表遍歷 |
| 尾部新增 add | O(1) 攤還 ⭐ | O(1) | 陣列偶爾擴容複製 |
| 頭部/中間插入刪除 | O(n) 元素位移 | O(1) 定位後 ⭐ | LinkedList 需先遍歷定位 O(n) |
| 搜尋 indexOf/contains | O(n) | O(n) | 皆為線性掃描 |
| 記憶體額外開銷 | 低 (Object[] + 少量欄位) | 高 (Node 物件含 prev/next 參考) | 大量小物件 LinkedList 記憶體壓力大 |
| 快取友善度 | 高 (連續記憶體) | 低 (分散節點) | 現代 CPU 預取機制偏好 ArrayList |
List list = new ArrayList<>(List.of("A", "B", "C", "D"));
ListIterator iter = list.listIterator(list.size()); // 定位至尾部之後
while (iter.hasPrevious()) {
System.out.println(iter.previous()); // D, C, B, A
} // Stack (LIFO) - 建議改用 ArrayDeque
Deque stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
String top = stack.pop(); // B
// Queue (FIFO) - 建議改用 ArrayDeque 或 LinkedList
Queue queue = new ArrayDeque<>(); // 或 new LinkedList<>()
queue.offer("A");
queue.offer("B");
String head = queue.poll(); // A 注意：Java 官方建議使用 ArrayDeque 替代 Stack 與 LinkedList 實作雙端佇列，效能更佳且非同步。
iterator()、size() 外所有 Collection 方法的預設實作toString()、contains()、toArray()、addAll() 等皆建構於 iterator/size 之上add、remove）Collections.unmodifiableList、List.of、Set.of）呼叫修改方法拋出 UnsupportedOperationExceptionRuntimeException，無須強制 try-catch，但呼叫端應注意契約文件CopyOnWriteArrayListList.of()、Set.of()、Map.of() 或 Collections.unmodifiableXxx()List list = new ArrayList<>(); 而非 ArrayList list = ... new ArrayList<>(expectedSize) 減少擴容複製Java Collection 框架將 ADT 理論工程化，提供統一介面、多樣實作、豐富演算法支援。理解各實作類別的時間/空間複雜度特性，依據存取模式選擇正確類別，是寫出高效能、可維護 Java 程式的關鍵能力。
