鏈結串列

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

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

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

1
2
3
4
5

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

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

1
2
3
4
5
6
7
8

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;
}

要刪除節點的話，就把要刪除的節點的上一個節點，接到要刪除的節點的下一個節點。不過單向鏈結串列要找一個節點的上一個節點的話，必須從頭開始線性搜尋，會比較麻煩一點。這個時候就可以用雙向連結串列，也就是再存一個指向上個節點的指標，這樣就可以馬上知道上一個點是誰了。

還有很多種可能的狀況，像是你的鏈結串列是環狀的，就可以讓最後一個節點的下一個節點是第一個節點。

除了可以用指標來做外，也可以開兩個陣列，這兩個陣列中的相同位置一起表示一個節點，一個陣列用來存值、另一個存下一個節點的位置編號，如果要做雙向的話也可以再開一個陣列。

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

STL

STL 中的 list 是雙向鏈結串列，但是很難用，沒什麼用處。