# 鏈結串列
###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

陣列和動態陣列都可以隨機存取，但如果要移除一個元素而不留空位，就得花 $O(n)$ 的時間把後面的元素往前移，在中間插入一個元素也是需要把後面所有元素後移，也要 $O(n)$ 的時間，那麼如果需要頻繁進行在序列中間刪除或插入的動作怎麼辦呢？

鏈結串列可以做到這件事，它把每一個元素放進一個節點裡，每個節點除了儲存元素的值外，也儲存一些指標，這些指標指向哪裡會根據鏈結串列的類型和你的需求而有所不同。

最基礎的鏈結串列是**單向鏈結串列**，每一個節點有一個指標，指向下一個元素所在的節點，如果沒有下一個，就指向 `nullptr`。

template<typename T>
struct Node{
    T value;
    Node* nxt = nullptr;
};

要插入一個元素的話，就把前一個元素的節點的下一個節點改成新插入的節點，而新插入的節點指向前一個節點本來的下一個節點。

template<typename T>
Node<T>* insert(Node<T>* node, int value){
    Node<T>* n = new Node<T>();
    n->nxt = node->nxt;
    n->value = value;
    node->nxt = n->value;
    return n;
}

要刪除節點的話，就把要刪除的節點的上一個節點，接到要刪除的節點的下一個節點。不過單向鏈結串列要找一個節點的上一個節點的話，必須從頭開始線性搜尋，會比較麻煩一點，就不付程式碼了。

除了單向鏈結串列外，鏈結串列還有很多類型，例如：
- 雙向鏈結串列：一個節點除了有指向下一個節點的指標外，也有指向上一個的。如果沒有下一個或上一個，就一樣指向 `nullptr`。
- 單向迴圈鏈結串列：最後一個節點的下一個節點指標指向第一個節點。
- 雙向迴圈鏈結串列：最後一個節點的下一個節點指標指向第一個節點、第一個節點的上一個節點指標指向最後一個節點。

除了這種用來存「一列」元素的之外，類似的概念也可以用來存像是樹的結構：每個節點有指向子節點的指標、或者是有指向父節點的指標。

除了可以用指標來做外，也可以開兩個陣列，這兩個陣列中的相同位置一起表示一個節點，一個陣列用來存值、另一個存下一個節點的位置編號，如果要做雙向鏈結串列，那就再開一個陣列存上一個節點的位置編號就好。這個做法會好寫很多，也比較不容易寫爛。

指標實作鏈結串列最大的缺點是不能隨機存取，但陣列實作可以彌補，雖然還是不能直接隨機存取串列裡第幾個元素，但你可以給位置編號特殊意義，像是在陣列裡的位置 $i$ 表示編號是 $i$ 的東西，這樣你就可以隨機存取每一個東西的上一個或下一個東西是什麼。

## STL

STL 中的 `list` 是雙向鏈結串列，迭代器是雙向迭代，也就是不能隨機存取，大致上有這些動作可以做：
- `empty()` - 判斷是否為空，$O(1)$。
- `size()` - 取得目前大小，$O(1)$。
- `front()` - 取得第一個元素參照，$O(1)$。
- `back()` - 取得最後一個元素參照，$O(1)$。
- `push_front(T value)` - 把一個元素放到最前面，$O(1)$。
- `pop_front()` - 把第一個元素移除，$O(1)$。
- `push_back(T value)` - 把一個元素放到尾端，$O(1)$。
- `pop_back()` - 把最後一個元素移除，$O(1)$。
- `insert(iterator pos, T value)` - 把一個元素插入到指定位置，本來在該位置和之後的元素會後移，而 `pos` 會依舊指向本來在該位置的元素，並且會回傳指向新插入元素的 iterator，$O(1)$。
- `erase(iterator pos)` - 把位於 `pos` 的元素移除，回傳被移除的元素的下一個元素的 iterator，$O(1)$。
- `clear()` - 清除所有元素。
- `operator=` - 複製一個 `list` 到另一個 `list`。

建構子：
- `list(size, T value)` - 讓 `list` 中有 `size` 個 `value`，`value` 沒填則是 `T()`。
- `list(list a)` - 複製 `a`。

我是覺得它很不實用就是了，比較實用的是陣列實作的版本。