學習資源

https://labuladong.online/algo/data-structure-basic/linkedlist-basic/

學習記錄

今天是學習的第 3 天，主要學習了單鏈表的基本操作：

為什麼需要鏈表

鏈表和陣列不一樣，不需要一整塊連續的記憶體空間儲存元素，而是通過每個節點上的 next, prev 指針，將零散的記憶體塊串連起來，形成一個鏈式結構。

好處是節點要用的時候就接上，不用的時候就拆掉，因此不用考慮陣列的縮擴容和資料搬移等問題。

但鏈表也是有其局限性的，例如陣列能夠透過索引快速訪問元素，而鏈表就不支持。

單鏈表的基本操作

這邊是一個工具函式，用來創建單鏈表

var ListNode = function(x) {
    this.val = x;
    this.next = null;
};

// 輸入一個陣列，轉換為一條單鏈表
var createLinkedList = function(arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    var head = new ListNode(arr[0]);
    var cur = head;
    for (var i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    return head;
}

查 / 改

如果想訪問每一個節點，可以這樣寫：

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
let head = createLinkedList([1, 2, 3, 4, 5]);

// for 迴圈遍歷單鏈表
for (let p = head; p != null; p = p.next) {
    console.log(p.val);
}

// 也可以使用 while 迴圈遍歷
var p = head;
while (p !== null) {
  console.log(p.val);
  p = p.next;
}

如果要通過索引訪問或修改單鏈表中的某個節點，只能從頭節點開始往後找，直到找到索引對應的節點，再進行訪問或修改。

增

情況一：在單鏈表頭部插入新元素

因為我們有單鏈表的頭節點 head，所以只需要將插入的新節點接到頭節點之前，再將新插入的節點作為頭節點即可。

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

// 在單鏈表頭部插入一個新節點 0
var newNode = new ListNode(0);
newNode.next = head;
head = newNode;

// 現在鏈表變成了 0 -> 1 -> 2 -> 3 -> 4 -> 5

情況二：在單鏈表尾部插入新元素

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

// 在單鏈表尾部插入一個新節點 6
var p = head;
// 先走到鏈表的最後一個節點
while (p.next !== null) {
    p = p.next;
}
// 現在 p 就是鏈表的最後一個節點
// 在 p 後面插入新節點
p.next = new ListNode(6);

// 現在鏈表變成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

情況三：在單鏈表中間插入新元素

我們要先找到要插入位置的前驅節點，接著操作前驅節點把新節點插入進去。

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

// 在第 3 個節點後面插入一個新節點 66
// 要先找到前驅節點，即第 3 個節點
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}
// 此時 p 指向第 3 個節點
// 組裝新節點的後驅指針
var newNode = new ListNode(66);
newNode.next = p.next;

// 插入新節點
p.next = newNode;

// 現在鏈表變成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

刪

情況一：在單鏈表中間刪除一個節點

首先要找到被刪除節點的前驅節點，接著把這個前驅節點的 next 指針指向被刪除節點的下一個節點，這樣就能把被刪除節點從鏈表中摘除了。

這邊有點繞口，讓我們直接看程式碼 😆

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

// 刪除第 4 個節點，要操作前驅節點
var p = head;
for (var i = 0; i < 2; i++) {
    p = p.next;
}

// 此時 p 指向第 3 個節點，即要刪除節點的前驅節點
// 把第 4 個節點從鏈表中摘除
p.next = p.next.next;

// 現在鏈表變成了 1 -> 2 -> 3 -> 5

情況二：在單鏈表尾部刪除一個節點

先透過 while 迴圈找到倒數第 2 個節點，並將其 next 設為 null，就能把最後一個節點從這個鏈表中摘除。

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

var p = head;
// 找到倒數第 2 個節點
while (p.next.next !== null) {
    p = p.next;
}

// 此時 p 指向倒數第 2 個節點
// 把尾節點從鏈表中摘除
p.next = null;

// 現在鏈表變成了 1 -> 2 -> 3 -> 4

情況三：在單鏈表頭部刪除一個節點

最後一種情況比較簡單，只需要把頭節點設為頭節點的 next 即可。

// 創建一條單鏈表 1 -> 2 -> 3 -> 4 -> 5
var head = createLinkedList([1, 2, 3, 4, 5]);

// 刪除頭節點
head = head.next;

// 現在鏈表變成了 2 -> 3 -> 4 -> 5

學習總結

• 鏈表是通過每個節點上的 next, prev 指針，將零散的記憶體塊串連起來，形成一個鏈式結構
• 鏈表可以提高記憶體的利用效率，因為鏈表的節點不需要挨在一起
• 鏈表不需要考慮陣列的縮擴容和資料搬移等問題