C++ Linked list(鏈結串列)

簡介

一般的陣列是以一組連續的記憶體空間構成的
而鏈結串列類似陣列，但是是以"一個節點指向下一個節點"的方式構成的，在記憶體中不連續

由於不是連續的，沒辦法直接透過索引值取得對應的元素

以下將用指針的方式實作，指針概念可以參考
https://hackmd.io/@fzw/cpp_pointer

Node

鏈結串列是由一個指向下一個節點構成的
而一個節點可以存放任意內容
在C++一般以struct實作

#include <iostream>

struct Node {
    int val;  // 可選的任意資料
    Node* next  // 下一個節點
}

int main() {
    Node* head = new Node();
    head->val = 10;
}

上述代碼創建了struct Node，並建立一個節點將val設為10
而next指針默認是nullptr
其中head->為*(head).的縮寫

新增節點

新增一個節點在head後面
也就是在head->next的地方新增一個節點

// 建立一個Node物件，並保存位址到head->next (Node *)
head->next = new Node();
// 此時head->next的值是新的Node的地址
head->next->val = 30;

插入節點

若要在10→30之間插入20，10→20→30

假設左邊的10節點是變數node
從圖中可以得知要將node->next變成指向新的節點
而新的節點的next指向原本的node->next
這樣就完成插入的動作

Node *temp = node->next;  // 暫存30
node->next = new Node();
node->next->val = 20;
node->next->next = temp; // 將20→30

刪除節點

接著演示如何刪除中間的節點20

刪除20意味著將10指向30
變數node當作是10節點
把node的箭頭(next)指向node的next的next

Node *temp = node->next;
node->next = node->next->next;
delete temp;  // 從記憶體中刪除這個Node

走訪

從某個節點(通常是起點)走到最後

Node *node = head;
while(node) {
    cout << node->val << ' ';
    node = node->next;
}

注意這裡需要將起點複製一份來走，否則將起點走掉的話會失去起點位置
此外bool(nullptr)為false，非空指針為true，所以不需要額外寫 != nullptr

雙向鏈結串列

struct Node {
    int val;
    Node *pre;
    Node *next;
}

雙向鏈結串列是節點同時有往後和往前的箭頭
在走訪時有辦法往回走
←⑩→ 而插入和刪除的變化同樣可以看圖模擬出來，此處不補充

Linked list與Array差異

從上面的動作可以看到在插入和刪除
Linked list只需要動到相鄰的節點
Array需要將後面的元素全部往後移或往前移
但是在存取內容時
Linked list需要從頭往下走
Array只需要帶入索引值
空間大小的部分
Linked list在新增/刪除時動態的取得和釋放空間(new、delete)
Array固定長度
Vector擴充一次容量的時間複雜度O(n)，但擴充次數很少