[DSA] 鏈結串列 linked list – 單向鏈結串列

為什麼需要鏈結串列

一般來說我們在認識鏈結串列前，應該都會先接觸陣列。陣列有個特徵是「連續的記憶體空間」，因此除了索引之外，操作上不是那麼的有效率。

而鏈結串列就不一樣，不需要一整塊連續的記憶體空間，它可以分散各處。要達到這個目的，只要每個元素都記住下個元素的位址即可，就可以像連連看一樣把一整串連起來，提高記憶體的使用效率，操作上能夠直接抽換（不用像陣列一樣搬移資料），也不用擔心是否需要擴充容量（幾乎等於沒有限制）。

當然這樣勢必有一些犧牲：無法像陣列一樣快速索引。例如我要第 n 個，跟陣列說，就等於直接開指定抽屜就可以拿到。而鏈結串列就必須一個一個往後找。

基本資料結構

class ListNode {
public:
	ListNode(int x) : val(x), next(NULL) {}
	
	int data;
	ListNode *next; 
};

上方是理解上比較簡單，實際上不會那麼單調（像是這邊先指定 data 只能有 int 型態）。

基本操作

假設我們已經擁有了 createLinkedList() 方法以供後續使用：

ListNode* createLinkedList(vector<int> arr) {
    if (arr.empty()) {
        return nullptr;
    }
    ListNode* head = new ListNode(arr[0]);
    ListNode* curr = head;
    for (int i = 1; i < arr.size(); i++) {
        curr->next = new ListNode(arr[i]);
        curr = curr->next;
    }
    return head;
}

另外光看圖像化的資料結構應該有感覺，當我想要新增、修改、查找等動作，不論是需要找前一個元素或是一個一個確認，都會需要從頭走訪各個元素，直到走到目標位址。

新增元素

希望新增資料在最前面（Head），因為 Head 是本來就知道的，這種新增最簡單：

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

ListNode* newNode = new ListNode(0);
newNode->next = head;
head = newNode;

新增鏈結串列 1->2->3->4->5
新增一個 node，資料為 0
要接在最頭，等於讓這個新的 node 的「下一個位址」指向現在的 head
舊 head 就會在這個串列最前面
結果為 0->1->2->3->4->100->5

時間複雜度：\(O(1)\)，因為本來就知道 head node 了。

而若是一般插入新元素在中間的狀況：

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

ListNode* p = head;
for (int i = 0; i < 3; i++) {
    p = p->next;
}

ListNode* newNode = new ListNode(100);
newNode->next = p->next;

p->next = newNode;

新增鏈結串列 1->2->3->4->5
找加入位置前的 node。例如想加入元素要放的是第四個節點後，要先找到第四個節點
新增一個 node，資料為 100
指定新 node 的 next 是第四個節點的 next，代表舊第五 node 前面是這新的節點
最後當然要把第四個節點的 next 也改為指向新 node
結果為 1->2->3->4->100->5

時間複雜度是：\(O(n)\)，因為要先找到加入位置的前面那個節點，其中 \(n\) 是鏈結串列的長度。

因此若指定加新元素到尾巴，時間複雜度也是一樣 \(O(n)\)，操作上也差不多。不過因為最尾端的 next 就是 NULL，所以更簡化一點：

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

ListNode* p = head;

while (p->next != nullptr) {
    p = p->next;
}

p->next = new ListNode(100);

新增鏈結串列 1->2->3->4->5
直接走到最後一個節點
把最後一個節點的 next 指向新創建的節點，完工
結果為 1->2->3->4->5->100

拿最開頭的水果例子來說（把數字資料代換成別的可能會好理解些）：

查詢、修改元素

如前面所述，鏈結串列中的節點透過指標相連，因此找到目標節點後，就可以直接修改該節點儲存的資料，不需要搬移其他元素，所以修改資料本身時間複雜度是 \(O(1)\)。

例如，若要找到值為 3 的節點並將其修改為 10，可以從頭節點開始依序尋找：

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

for (ListNode* p = head; p != nullptr; p = p->next) {
    if (p->val == 3) {
        p->val = 10;
        break;
    }
}

新增鏈結串列 1->2->3->4->5
從 head 開始往後找，有符合的值就改

類似的，如果是要透過索引存取或修改鏈結串列中的某個節點，也只能用 for 迴圈從頭節點開始往後找，直到找到索引對應的節點，然後進行存取或修改。

這個操作的最差時間複雜度是 \(O(n)\)，其中 \(n\) 是鏈結串列的長度。

所以像是這樣存取或修改鏈結串列中的某個節點，都是從頭節點開始依序往後尋找，直到抵達索引對應的節點。

時間複雜度是 \(O(n)\)，其中 \(n\) 是鏈結串列的長度。

刪除元素

刪除一個節點，首先要找到要被刪除節點的前驅節點，然後把這個前驅節點的 next 指標指向被刪除節點的下一個節點。這樣就能把被刪除節點從鏈結串列中移除了。

ListNode* head = createLinkedList({1, 2, 3, 4, 5});

ListNode* p = head;
for (int i = 0; i < 2; i++) {
    p = p->next;
}

ListNode* toDelete = p->next;
p->next = toDelete->next;
delete toDelete;