陣列／vector 要求元素緊挨著放在記憶體裡；鏈結結構（linked structure）改用 節點（node）＋指標（pointer）：每個節點自己記得「下一個在哪」。 只要能從第一個節點（head）出發，相對順序就能靠指標一路走出來。
節點是鏈結串列的積木：data 放資料、next 指向下一個節點。
next == NULL 表示「後面沒有了」：這就是串列的結尾記號（grounded）。
未排序串列把新元素加在 head（最省事的位置，O(1)）。
重點戲是 remove：需要 prev / cur 雙指標同行，找到後讓 prev「跳過」cur。
順序錯了串列就斷：先接住後面，再改前面。
動畫面板用的是簡化寫法；實際的類別把 head 藏在 private、透過 Node 的
getNext()／setNext() 操作。size()、search()、remove()
都建立在同一個技巧上：走訪（traversal），也就是從 head 出發、
一個節點一個節點地拜訪到 NULL 為止。
add 裡若把兩行寫反（先 head = temp、再 temp->next = head），會發生什麼事？
排序串列的 add 不能亂插：prev/cur 往前走，直到 cur->data ≥ item 就是插入點。
search 因此能提前失敗：一旦看到比目標大的值就確定不存在。
判斷準則一句話：只碰 head 的操作是 O(1)，其他都要走訪。 search 平均找到目標時走了 n/2 步：聽起來省一半，但 Big-O 只看成長率， 係數 1/2 會被丟掉，而且最壞情況（不在串列裡、或排在最後）還是得走完全程，所以仍是 O(n)。 下表是講義列的完整 List ADT，一次看清楚每個方法的代價：
| 方法 | 做什麼 | 未排序 | 排序 |
|---|---|---|---|
| is_empty() | 串列是空的嗎（看 head） | O(1) | O(1) |
| add(item) | 加入元素 | O(1)（插 head） | O(n)（找位置） |
| size() | 邊走邊數 | O(n) | O(n) |
| search(item) | 找得到嗎 | O(n) | O(n)，可提前停 |
| remove(item) | prev/cur 找到後摘除 | O(n) | O(n) |
| append(item) | 接在尾端（補充練習） | O(n)；有 tail 指標可 O(1) | 不適用（位置由大小決定） |
| index(item) | 回報元素排第幾 | O(n) | O(n) |
| insert(pos, item) | 插到指定位置 | O(n)（走到 pos） | 不適用 |
| pop() / pop(pos) | 移除尾端／指定位置並回傳 | O(n) | O(n) |
search 平均只要走 n/2 個節點就找到目標。為什麼複雜度不寫成 O(n/2)？
單向串列刪尾端很痛：要先走到倒數第二個節點。雙向串列（doubly linked）
給每個節點多存一根 prev，兩個方向都能走；環狀串列（circular）
讓 tail 的 next 指回 head，作業系統的分時排程（輪流給每個程式一點 CPU）就是這樣繞圈的。
雙向串列的插入要同時接好四根指標：新節點的 prev、next，加上左右鄰居各一根。 順序亂了照樣斷鏈，所以實務上常加哨兵節點（sentinel）：在頭尾各放一個不存資料的假節點， 讓「插在最前」「刪到只剩一個」這些邊界情況消失，每次操作都變成「在兩個真實存在的節點之間動手」。 多花兩個節點的記憶體，換到少一半的 if，很划算。
要讓「刪除尾端節點」變成 O(1)，需要哪種配置？
理解原理之後，實戰請用 STL：std::forward_list 是單向串列、std::list 是雙向串列。
它們保證任意位置插入/刪除 O(1)（拿到迭代器之後），但不支援 [i] 隨機存取。
| vector | forward_list（單向） | list（雙向） | |
|---|---|---|---|
| 隨機存取 [i] | O(1) | —（不提供） | —（不提供） |
| 頭端插入 | O(n) | O(1) push_front | O(1) push_front |
| 尾端插入 | O(1) 攤銷 | O(n)（無 tail） | O(1) push_back |
| 已知位置插刪 | O(n) | O(1) insert_after | O(1) insert/erase |
| 每節點額外空間 | 0 | 1 指標 | 2 指標 |
| cache 友善度 | 高（連續） | 低（節點分散） | |
單向串列的 STL 版本連命名都在提醒你它的限制：插入叫 insert_after、
刪除叫 erase_after，因為單向串列只能「在某個節點後面」動手。常用操作：
| 操作 | 說明 |
|---|---|
| push_front(x) / pop_front() | 頭端加入、移除，O(1) |
| emplace_front(...) | 就地建構元素後放到最前面 |
| insert_after(it, x) | 在迭代器 it 的後面插入，O(1) |
| erase_after(it) | 刪掉 it 後面那個節點，O(1) |
| remove(x) / unique() / sort() | 串列自家的成員函式版本（不能用 std::sort，沒隨機存取） |
forward_list 只提供 insert_after，不提供 insert（插在某節點前面）。原因是？
一條長度 n 的單向串列，size()（用走訪實作）與「取第 k 個元素」的成本分別是？
remove(item) 用 prev/cur 雙指標。刪除的是 head 節點時，正確動作是？
C++ 手刻串列 remove 之後少做了什麼，會發生什麼事？
講義留了一題課後練習：替 UnorderedList 加上 append(item)，把新元素接在尾端。
走訪版的解答長這樣：
上面這個 append() 是 O(n)。要讓它變成 O(1)，正確的做法是？
| 操作 | vector／陣列 | UnorderedList | OrderedList |
|---|---|---|---|
| 存取第 k 個 | O(1) | O(k) | O(k) |
| 插入（頭） | O(n) | O(1) | O(n)（找位置） |
| search | O(n)／排序後 O(log n) | O(n) | O(n)，可提前停 |
| remove（已找到） | O(n)（搬移） | O(1)（改指標） | O(1)（改指標） |