iT邦幫忙

2025 iThome 鐵人賽
DAY 6
0
自我挑戰組

苦痛之路：在聖巢中修煉演算法系列 第 6 篇

苦痛之路 Day 06 - 鏈表程式碼實現

17th鐵人賽
77 瀏覽

  • 分享至 

  • xImage
    •  

https://ithelp.ithome.com.tw/upload/images/20250918/201038173ttRPUgR6R.png

學習資源

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

學習記錄

今天是學習的第 5 天，主要學習了鏈表程式碼實現：

實作鏈表有幾個關鍵點需要注意：

關鍵點一：同時持有頭尾節點的引用

雙鏈表一般會同時持有頭尾節點的引用，因為在容器尾部添加元素是很頻繁的操作，持有尾部節點的引用，就可以在 O(1) 的時間複雜度內完成尾部添加元素的操作。

對於單鏈表來說，持有尾部節點的引用也有優化效果。比如要在單鏈表尾部添加元素，如果沒有尾部節點的引用，就需要遍歷整個鏈表找到尾部節點，時間複雜度是 O(n)；如果有尾部節點的引用，就可以在 O(1) 的時間複雜度內完成尾部添加元素的操作。

head -> 1 -> 2 -> 3 -> 4 -> null
↑       ↑              ↑
指標    頭節點          尾節點

關鍵點二：虛擬頭尾節點

它的原理是在創建雙鏈表的時候，就創建一個虛擬頭節點和一個虛擬尾節點，無論雙鏈表是否為空，這兩個節點都存在。

舉個例子，假設虛擬頭尾節點分別是 dummyHead 和 dummyTail，那麼一條空的雙鏈表長這樣：

dummyHead <-> dummyTail

如果添加 1,2,3 幾個元素，那麼雙鏈表長這樣：

dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

現在有了虛擬頭尾節點，都只需要考慮在中間插入元素的情況就可以了。

關鍵點三：記憶體洩漏

在刪除節點的時候，最好把被刪除節點的指針都設為 null，養成好習慣，這可以避免一些潛在的問題。

// 假設單鏈表頭節點 head = 1 -> 2 -> 3 -> 4 -> 5

// 記錄要刪除的節點
var toDelete = head;

// 刪除單鏈表頭節點
head = head.next;

// 此時 head = 2 -> 3 -> 4 -> 5

// 清理被刪除節點的指針
toDelete.prev = null;
toDelete.next = null;

單鏈表程式碼

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class MyLinkedList {
    constructor() {
        this.head = new Node(null);
        this.tail = this.head;
        this.size = 0;
    }

    addFirst(e) {
        const newNode = new Node(e);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (this.size === 0) {
            this.tail = newNode;
        }
        this.size++;
    }

    addLast(e) {
        const newNode = new Node(e);
        this.tail.next = newNode;
        this.tail = newNode;
        this.size++;
    }

    add(index, element) {
        this.checkPositionIndex(index);

        if (index === this.size) {
            this.addLast(element);
            return;
        }

        let prev = this.head;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        const newNode = new Node(element);
        newNode.next = prev.next;
        prev.next = newNode;
        this.size++;
    }

    removeFirst() {
        if (this.isEmpty()) {
            throw new Error("NoSuchElementException");
        }
        const first = this.head.next;
        this.head.next = first.next;
        if (this.size === 1) {
            this.tail = this.head;
        }
        this.size--;
        return first.val;
    }

    removeLast() {
        if (this.isEmpty()) {
            throw new Error("NoSuchElementException");
        }

        let prev = this.head;
        while (prev.next !== this.tail) {
            prev = prev.next;
        }
        const val = this.tail.val;
        prev.next = null;
        this.tail = prev;
        this.size--;
        return val;
    }

    remove(index) {
        this.checkElementIndex(index);

        let prev = this.head;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }

        const nodeToRemove = prev.next;
        prev.next = nodeToRemove.next;
        // 刪除的是最後一個元素
        if (index === this.size - 1) {
            this.tail = prev;
        }
        this.size--;
        return nodeToRemove.val;
    }

    // ***** 查 *****

    getFirst() {
        if (this.isEmpty()) {
            throw new Error("NoSuchElementException");
        }
        return this.head.next.val;
    }

    getLast() {
        if (this.isEmpty()) {
            throw new Error("NoSuchElementException");
        }
        return this.tail.val;
    }

    get(index) {
        this.checkElementIndex(index);
        const p = this.getNode(index);
        return p.val;
    }

    // ***** 改 *****

    set(index, element) {
        this.checkElementIndex(index);
        const p = this.getNode(index);

        const oldVal = p.val;
        p.val = element;

        return oldVal;
    }

    // ***** 其他工具函式 *****
    size() {
        return this.size;
    }

    isEmpty() {
        return this.size === 0;
    }

    isElementIndex(index) {
        return index >= 0 && index < this.size;
    }

    isPositionIndex(index) {
        return index >= 0 && index <= this.size;
    }

    // 檢查 index 索引位置是否可以存在元素
    checkElementIndex(index) {
        if (!this.isElementIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    // 檢查 index 索引位置是否可以添加元素
    checkPositionIndex(index) {
        if (!this.isPositionIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    // 返回 index 對應的 Node
    // 注意：請保證傳入的 index 是合法的
    getNode(index) {
        let p = this.head.next;
        for (let i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }
}

// 範例
const list = new MyLinkedList2();
list.addFirst(1);
list.addFirst(2);
list.addLast(3);
list.addLast(4);
list.add(2, 5);

console.log(list.removeFirst()); // 2
console.log(list.removeLast());  // 4
console.log(list.remove(1));     // 5

console.log(list.getFirst());    // 1
console.log(list.getLast());     // 3
console.log(list.get(1));        // 3

雙鏈表程式碼

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class MyLinkedList {
    // 虛擬頭尾節點
    constructor() {
        this.head = new Node(null);
        this.tail = new Node(null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.size = 0;
    }

    // ***** 增 *****

    addLast(e) {
        const x = new Node(e);
        const temp = this.tail.prev;
        temp.next = x;
        x.prev = temp;
        // temp <-> x

        x.next = this.tail;
        this.tail.prev = x;
        // temp <-> x <-> tail
        this.size++;
    }

    addFirst(e) {
        const x = new Node(e);
        const temp = this.head.next;
        // head <-> temp
        temp.prev = x;
        x.next = temp;

        this.head.next = x;
        x.prev = this.head;
        // head <-> x <-> temp
        this.size++;
    }

    add(index, element) {
        this.checkPositionIndex(index);
        if (index === this.size) {
            this.addLast(element);
            return;
        }

        // 找到 index 對應的 Node
        const p = this.getNode(index);
        const temp = p.prev;
        // temp <-> p

        // 要插入的新 Node
        const x = new Node(element);

        p.prev = x;
        temp.next = x;

        x.prev = temp;
        x.next = p;

        // temp <-> x <-> p

        this.size++;
    }

    // ***** 刪 *****

    removeFirst() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        // 虛擬節點的存在是我們不用考慮空指針的問題
        const x = this.head.next;
        const temp = x.next;
        // head <-> x <-> temp
        this.head.next = temp;
        temp.prev = this.head;

        // head <-> temp

        this.size--;
        return x.val;
    }

    removeLast() {
        if (this.size < 1) {
            throw new Error("No elements to remove");
        }
        const x = this.tail.prev;
        const temp = x.prev;
        // temp <-> x <-> tail

        this.tail.prev = temp;
        temp.next = this.tail;

        // temp <-> tail

        this.size--;
        return x.val;
    }

    remove(index) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const x = this.getNode(index);
        const prev = x.prev;
        const next = x.next;
        // prev <-> x <-> next
        prev.next = next;
        next.prev = prev;

        this.size--;

        return x.val;
    }

    // ***** 查 *****

    get(index) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const p = this.getNode(index);

        return p.val;
    }

    getFirst() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.head.next.val;
    }

    getLast() {
        if (this.size < 1) {
            throw new Error("No elements in the list");
        }

        return this.tail.prev.val;
    }

    // ***** 改 *****

    set(index, val) {
        this.checkElementIndex(index);
        // 找到 index 對應的 Node
        const p = this.getNode(index);

        const oldVal = p.val;
        p.val = val;

        return oldVal;
    }

    // ***** 其他工具函式 *****

    size() {
        return this.size;
    }

    isEmpty() {
        return this.size === 0;
    }

    getNode(index) {
        this.checkElementIndex(index);
        let p = this.head.next;
        // TODO: 可以優化，通過 index 判斷從 head 還是 tail 開始遍歷
        for (let i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }

    isElementIndex(index) {
        return index >= 0 && index < this.size;
    }

    isPositionIndex(index) {
        return index >= 0 && index <= this.size;
    }

    // 檢查 index 索引位置是否可以存在元素
    checkElementIndex(index) {
        if (!this.isElementIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    // 檢查 index 索引位置是否可以添加元素
    checkPositionIndex(index) {
        if (!this.isPositionIndex(index)) {
            throw new Error(`Index: ${index}, Size: ${this.size}`);
        }
    }

    display() {
        console.log(`size = ${this.size}`);
        let p = this.head.next;
        let str = "";
        while (p !== this.tail) {
            str += `${p.val} <-> `;
            p = p.next;
        }
        console.log(str + "null\n");
    }
}

// 範例
const list = new MyLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addFirst(0);
list.add(2, 100);

list.display();
// size = 5
// 0 <-> 1 <-> 100 <-> 2 <-> 3 <-> null

學習總結

在實作鏈表的時候，有幾個關鍵點要注意：

  1. 同時持有頭尾節點的引用，可方便我們做後續的操作
  2. 創建虛擬頭尾節點，讓我們只需要考慮在中間操作元素的情況
  3. 為了避免記憶體洩漏，在刪除節點的時候，最好把被刪除節點的指針都設為 null

上一篇
苦痛之路 Day 05 - 雙鏈表（鏈式儲存）基本原理
下一篇
苦痛之路 Day 07 - 環形陣列技巧及實現
系列文
苦痛之路：在聖巢中修煉演算法 共 31 篇
  1. 27
    苦痛之路 Day 27 - 二叉搜索樹的應用
  2. 28
    苦痛之路 Day 28 - TreeMap / TreeSet 實現原理
  3. 29
    苦痛之路 Day 29 - 紅黑樹的平衡
  4. 30
    苦痛之路 Day 30 - Trie / 字典樹 / 前綴樹原理
  5. 31
    苦痛之路 Day 31 - 學習回顧
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
902 組
團體組數
37 組
累計文章數
19796 篇
完賽人數
529 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# linux windows server css react
熱門問題
熱門回答
熱門文章
IT邦幫忙