C++ Linked list

# C++ Linked list(鏈結串列) ## 簡介一般的陣列是以一組連續的記憶體空間構成的而鏈結串列類似陣列，但是是以"一個節點指向下一個節點"的方式構成的，在記憶體中不連續由於不是連續的，沒辦法直接透過索引值取得對應的元素以下將用指針的方式實作，指針概念可以參考 [https://hackmd.io/@fzw/cpp_pointer](https://hackmd.io/@fzw/cpp_pointer) ## Node 鏈結串列是由一個指向下一個節點構成的而一個節點可以存放任意內容在C++一般以struct實作 ```cpp #include <iostream> struct Node { int val; // 可選的任意資料 Node* next // 下一個節點 } int main() { Node* head = new Node(); head->val = 10; } ``` ![IMG_20240722_151258](https://hackmd.io/_uploads/rkl45IKjOA.png) 上述代碼創建了struct Node，並建立一個節點將val設為10 而next指針默認是nullptr 其中head->為*(head).的縮寫 ## 新增節點新增一個節點在head後面也就是在head->next的地方新增一個節點 ```cpp // 建立一個Node物件，並保存位址到head->next (Node *) head->next = new Node(); // 此時head->next的值是新的Node的地址 head->next->val = 30; ``` ![image-31](https://hackmd.io/_uploads/rkiZsKiuC.png) ## 插入節點若要在10→30之間插入20，10→20→30 ![image-52](https://hackmd.io/_uploads/BkkNhFj_R.png) 假設左邊的10節點是變數node 從圖中可以得知要將node->next變成指向新的節點而新的節點的next指向原本的node->next 這樣就完成插入的動作 ```cpp Node *temp = node->next; // 暫存30 node->next = new Node(); node->next->val = 20; node->next->next = temp; // 將20→30 ``` ## 刪除節點接著演示如何刪除中間的節點20 ![image-56](https://hackmd.io/_uploads/ByES1qsuC.png) 刪除20意味著將10指向30 變數node當作是10節點把node的箭頭(next)指向node的next的next ```cpp Node *temp = node->next; node->next = node->next->next; delete temp; // 從記憶體中刪除這個Node ``` ## 走訪從某個節點(通常是起點)走到最後 ```cpp Node *node = head; while(node) { cout << node->val << ' '; node = node->next; } ``` 注意這裡需要將起點複製一份來走，否則將起點走掉的話會失去起點位置此外bool(nullptr)為false，非空指針為true，所以不需要額外寫 != nullptr ## 雙向鏈結串列 ![image-45](https://hackmd.io/_uploads/r1eMJqn_R.png) ```cpp 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)，但擴充次數很少