鏈結串列(Linked list)

介紹

鏈結串列是線性的數據結構(linear collection)，與陣列不同，鏈結的元素不存儲在連續位置，元素使用指針鏈接。它們包括一系列連接的節點。每個節點存儲數據和下一個節點的位置(如下圖所示)，便於追加或刪除，但儲存數據很費時。

優缺點

優點

• 新增以及刪除資料比陣列來的更快
• 動態陣列，不會有陣列重新定義大小問題

缺點

• 數據儲存不連續記憶體位置
• 訪問指定位置必須從頭開始查找
• 需而外記憶體空間儲存儲存指標

複雜度

(圖片取自於bigocheatsheet)

時間複雜度

動作	時間複雜度
插入	$O(N)$ \/ $O(1)$ 插入頭節點
刪除	$O(N)$ \/ $O(1)$ 刪除頭節點
搜尋	$O(N)$
訪問index	$O(N)$

空間複雜度

$O(n)$

其中 n 是列表中元素的數量，因為列表中的每個節點都需要內存來存儲其數據和指向下一個節點的指針。

常見種類

• 單向鏈結串列（Singly Linked List）
• 雙向鏈結串列（Doubly Linked List）
• 迴圈鏈結串列（Circularly Linked List）

單向鏈結串列（Singly Linked List）

每兩個節點間只有一個單向的鏈結。

(圖片取自於types-of-linked-list)

雙向鏈結串列（Doubly Linked List）

帶有兩個指標指向前後數據，缺點是必須增加數據儲存領域，追加數據以及刪除數據時，要變更方向的指標也變多了。

• 查找值為Singly Linked List一半時間(平均)
• 可從前往後讀取，或從後往前讀取

(圖片取自於types-of-linked-list)

迴圈鏈結串列（Circularly Linked List）

沒有頭尾概念，用於想維持最新數據為固定數量時。

(圖片取自於types-of-linked-list)

實作鏈結串列

單向鏈結串列（Singly Linked List）

以下使用 JavaScript 實作

建立Node

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

建立鏈結串列

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}

新增push方法

將新節點新增至末端

1. 建立Node，value為傳入的值
2. 如果head為空，則將head設置為新節點
3. 否則，使用一個while循環，遍歷Linked List直到找到最後一個節點
4. 最後一個節點的next指向新節點
5. 增加Linked List的長度

(圖片來自於visualgo)

push(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
    this.length++;
}

新增pop方法

移除尾端節點

1. 如果head為空，則返回null
2. 如果鏈表長度為1，則將head設置為null並返回原本的head節點
3. 否則，使用一個for循環，遍歷Linked List直到找到倒數第二個節點
4. 將倒數第二個節點的next設置為null
5. 減少Linked List長度，並返回尾端節點

(圖片來自於visualgo)

pop() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let currentNode = this.head;
      for (let i = 1; i <= this.length - 2; i++) {
        currentNode = currentNode.next;
      }
      let temp = currentNode.next;
      currentNode.next = null;
      this.length--;
      return temp;
    }
}

新增shift方法

刪除開頭的節點

1. 如果head為空，則返回null
2. 如果Linked List長度為1，則將head設置為null並返回原本的head節點
3. 否則，將head設置為head的下一個節點
4. 減少Linked List長度，並返回原本的head節點

(圖片來自於visualgo)

shift() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let temp = this.head;
      this.head = this.head.next;
      this.length--;
      return temp;
    }
}

新增unshift方法

新增新節點在頭部

1. 如果head為空，則將head設置為新節點。
2. 否則，創建一個新節點，將head設置為新節點，並將新節點的next指向原本的head節點。
3. 增加Linked List的長度

(圖片來自於visualgo)

unshift(value) {
    if (!this.head) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      let newNode = new Node(value);
      this.head = newNode;
      this.head.next = temp;
    }
    this.length++;
}

新增insertAt方法

在Linked List中的特定索引位置新增一個新節點

1. 如果索引大於Linked List的長度或小於0，則返回null。
2. 如果索引等於0，則通過unshift方法在Linked List開頭添加一個新節點。
3. 如果索引等於Linked List的長度，則通過push方法在Linked List末尾添加一個新節點。
4. 否則，創建一個新節點，遍歷到索引位置的節點，將新節點的next指向當前節點的下一個節點，並將當前節點的next指向新節點。
5. 增加Linked List的長度

(圖片來自於visualgo)

insertAt(index, value) {
    if (index > this.length || index < 0) {
      return null;
    } else if (index === 0) {
      this.unshift(value);
      return;
    } else if (index === this.length) {
      this.push(value);
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(value);
    // for loop index - 1 steps
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    this.length++;
    return;
}

新增removeAt方法

在Linked List中的特定索引位置刪除一個節點

1. 首先檢查指定的索引是否在Linked List的範圍之外，在這種情況下返回null
2. 如果索引為0則使用shift方法刪除頭節點，返回刪除節點
3. 如果索引等於Linked List長度則使用pop方法刪除尾端節點並返回
4. 否則，遍歷Linked List找到要移除的索引位置減一，更新指針已移除目標節點，並返回刪除節點
5. 減少Linked List的長度

(圖片來自於visualgo)

removeAt(index) {
    if (index > this.length - 1 || index < 0) {
      return null;
    } else if (index === 0) {
      let result = this.shift();
      return result;
    } else if (index === this.length - 1) {
      let result = this.pop();
      return result;
    }

    let currentNode = this.head;
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    let temp = currentNode.next;
    currentNode.next = currentNode.next.next;
    this.length--;
    return temp;
}

新增get方法

返回索引位置的值

1. 檢查索引是否大於或等於Linked List的長度或小於 0，在範圍外則返回null
2. 範圍內則迭代至index位置則返回

(圖片來自於visualgo)

get(index) {
    if (index >= this.length || index < 0) {
      return null;
    }
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode.value;
}

完整程式碼

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

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  push(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
    this.length++;
  }

  pop() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let currentNode = this.head;
      for (let i = 1; i <= this.length - 2; i++) {
        currentNode = currentNode.next;
      }
      let temp = currentNode.next;
      currentNode.next = null;
      this.length--;
      return temp;
    }
  }

  shift() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let temp = this.head;
      this.head = this.head.next;
      this.length--;
      return temp;
    }
  }

  unshift(value) {
    if (!this.head) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      let newNode = new Node(value);
      this.head = newNode;
      this.head.next = temp;
    }
    this.length++;
  }

  insertAt(index, value) {
    if (index > this.length || index < 0) {
      return null;
    } else if (index === 0) {
      this.unshift(value);
      return;
    } else if (index === this.length) {
      this.push(value);
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(value);
    // for loop index - 1 steps
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    this.length++;
    return;
  }

  removeAt(index) {
    if (index > this.length - 1 || index < 0) {
      return null;
    } else if (index === 0) {
      let result = this.shift();
      return result;
    } else if (index === this.length - 1) {
      let result = this.pop();
      return result;
    }

    let currentNode = this.head;
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    let temp = currentNode.next;
    currentNode.next = currentNode.next.next;
    this.length--;
    return temp;
  }

  get(index) {
    if (index >= this.length || index < 0) {
      return null;
    }
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode.value;
  }

  printAll() {
    if (this.length === 0) {
      console.log("Nothing in this linked list.");
      return;
    }
    let currentNode = this.head;
    while (currentNode !== null) {
      console.log(currentNode.value);
      currentNode = currentNode.next;
    }
  }
}

let myLinkedList = new LinkedList();
myLinkedList.push("Joe");
myLinkedList.push("Cherry");
myLinkedList.push("Denny");
myLinkedList.push("Fred");
myLinkedList.removeAt(1);
myLinkedList.insertAt(1, "Ted");

myLinkedList.printAll(); // Joe Ted Denny Fred
// console.log(myLinkedList.length);

(圖片取自於GeeksforGeeks)

(圖片取自於GeeksforGeeks)

實戰

707. Design Linked List

題目說明

設計一個 Linked list 可以選擇使用單向鏈結或雙向鏈結，單向鏈結的 node 須包含 val 和 next，而雙向鏈結則需再多一個 prev 屬性。

code

詳細解法

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

var MyLinkedList = function() {
    this.head = null;
    this.tail = null;
    this.length = 0;
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this.length) return -1;
    let current = this.head;
    let i = 0;
    while (i !== index) {
        current = current.next;
        i++;
    }
    return current.val;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let newNode = new Node(val);
    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let newNode = new Node(val);
    if (!this.tail) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.length++;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    let newNode = new Node(val);
    if (index < 0 || index > this.length) return -1;
    if (index === 0) {
        this.addAtHead(val);
    } else if (index === this.length) {
        this.addAtTail(val);
    } else {
        let current = this.head;
        let i = 0;
        while (i !== index - 1) {
            current = current.next;
            i++;
        }
        newNode.next = current.next;
        current.next = newNode;
        this.length++;
    }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index < 0 || index >= this.length) return -1;
    if (index === 0) {
        this.head = this.head.next;
        this.length--;
    } else{
        let current = this.head;
        let i = 0;
        while (i !== index - 1) {
            current = current.next;
            i++;
        }
        current.next = current.next.next;
        if (index === this.length - 1) {
            this.tail = current;
        }
        this.length--;
    }
};

/** 
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

參考來源

資料結構與演算法 (JavaScript)