昨天我們看了陣列的題目，今天我們要來學鏈結串列 ( Linked list )
我們在 Day6的時候有提到，陣列的插入和刪除很麻煩，那鏈結串列的優點就是插入和刪除都很方便，不需要移動大量資料

複習:Day 6 - 陣列 (Array)和記憶體位址

什麼是鏈結串列?

鏈結串列為一種線性序列，但是在記憶體中是 不連續 的存在

他是由一連串**節點(Node)**組成的資料結構,每個節點包含兩個部分:

• 資料欄(Data):存放實際的資料
• 指標欄(Pointer/ Next):存放下一個節點的記憶體位址

節點跟節點之間靠指標把它們「串」起來,這跟陣列「必須連續存放」的特性完全不同!

Linked List又可以分為三種，分別是 :

• Singly Linked List（單向鏈結串列）
• Doubly Linked List（雙向鏈結串列）
• Circular Linked List（環狀鏈結串列）

動態記憶體配置 (Dynamic allocation)

為什麼在學鏈結串列前會需要先學動態配置記憶體呢?
因為像是在宣告陣列時，程式在編譯時就決定好大小

int arr[100];
int array[10];

如果你在arr只用了十個位置，剩下的空間仍然會被保留
反之，如果在array需要放15個資料，陣列也沒辦法繼續擴充

所以我們希望需要多少空間，就配置多少空間
這時候就需要動態配置啦 !

但如果變數或物件使用動態配置記憶體的話，事後必須進行釋放，不然會造成記憶體洩漏(Memory leak)
如果是靜態配置記憶體的話，編譯器會自動完成釋放記憶體喔

C++動態配置記憶體

int* p = new int;
資料型態* 指標名字= new 資料型態

這時候系統會在記憶體中配置一個 int 大小的空間。

配置一個大小為5的動態陣列

int* arr = new int[5];

使用完要釋放

delete p;
delete[] arr;

節點宣告

struct Node {
    int data;       // 資料欄 放資料的
    Node* next;      // 指標欄,指向下一個節點的位址
};

建立第一個節點

Node* head = new Node; 

通常我們會用一個指標 head 指向鏈結串列的第一個節點，
作為整條 Linked List 的入口。

設定資料

head->data = 10;
head->next = nullptr;

也可以寫成

Node* head = new Node{10, nullptr};

建立一個簡單的鏈結串列

Node* head = new Node{10, nullptr};
head->next = new Node{20, nullptr};
head->next->next = new Node{30, nullptr};

插入節點

10 -> 30
插入 20

Node* newNode = new Node;

newNode->data = 20;
newNode->next = node10->next;

node10->next = newNode;

時間複雜度 : O(1)

刪除節點

10 -> 20 -> 30
刪除 20

node10->next = node20->next;
delete node20;

時間複雜度 : O(1)

比陣列快在哪裡?

當已經知道插入位置時，只需要修改指標即可完成插入，不需要像陣列那樣搬移後面的元素，因此插入操作本身為 O(1)。
但如果不知道插入位置，仍需要從 head 開始走訪尋找節點，這個過程需要 O(n)。

因此 Linked List 的優勢在於「已知位置後的插入與刪除效率高」，而不是整個插入流程一定都是 O(1)

Linked List 與 Array 比較

Linked List 最大的特色在於：

• 不需要連續記憶體空間
• 大小可以動態擴充
• 插入與刪除效率高

但也因為失去了索引的概念，
存取特定位置的元素必須從頭開始走訪，
因此存取效率不如 Array。

不同資料結構各有優缺點
必須根據實際需求選擇適合的資料結構~

參考資料和書籍

1. 圖解資料結構×演算法:運用C++ 胡昭明
2. https://zh.wikipedia.org/zh-tw/%E9%93%BE%E8%A1%A8