鏈結串列

tags: `Competitive Programming Note`

本文已停止更新，新版請至 WiwiHo 的競程筆記

陣列和動態陣列都可以隨機存取，但如果要移除一個元素而不留空位，就得花

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。

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

鏈結串列

tags: Competitive Programming Note

STL

tags: `Competitive Programming Note`