Linked list (鏈結串列) | 資料結構&演算法

資料結構 鏈結串列（Linked List） 是一種基本的資料結構，用於存儲一系列元素。在 JavaScript 中，可以使用物件來實現鏈結串列。鏈結串列由節點（Node）組成，每個節點包含一個數據元素和一個指向下一個節點的連結。

鏈結串列（Linked List） 在記憶體中並不是連續的保存

Linked List In Memory

Javascript中的陣列(Array)，才是連續性的保存在同一個地方

Array In Memory

鏈結串列（Linked List）的優勢，並且在特定的情況下是更適合使用的：

  1. 動態大小： 鏈結串列的大小可以動態調整，不像陣列（Array）需要事先指定大小。這使得鏈結串列更靈活，可以根據需要動態調整大小。
  2. 插入和刪除操作效率高： 在鏈結串列中插入和刪除節點的效率較高，特別是在頭部和尾部進行操作。這是因為只需要調整相應節點的指針，而不需要移動其他節點。
  3. 無須連續的記憶體空間： 相較於陣列，鏈結串列的節點在記憶體中可以分散存儲，不需要連續的記憶體空間。這有助於減少記憶體碎片化，尤其在動態環境中。
  4. 不需預先分配大小： 鏈結串列不需要事先指定大小，而陣列在創建時需要指定大小。這使得鏈結串列更容易應對動態數據。
  5. 簡單的插入和刪除操作： 在鏈結串列中，插入和刪除節點通常只需要改變相應節點的指針，而不需要移動其他節點。這在某些應用中可以提供更高效的操作。

鏈結串列適用於以下情況：

  • 頻繁的插入和刪除操作： 鏈結串列在插入和刪除節點的效率上優於陣列，特別是在中間插入或刪除節點的情況下。
  • 不確定數據大小： 如果不知道數據的大小，並且需要動態調整大小，鏈結串列是一個不錯的選擇。
  • 不需要隨機訪問： 如果主要是需要順序訪問數據而不是根據索引隨機訪問，鏈結串列可以提供一個簡單且有效的解決方案。

以下是一個簡單的 JavaScript 鏈結串列（Linked List） 的實現：

  1. Node 類別：
  • Node 類別用於創建鏈結串列的節點。每個節點包含一個值 (value) 和指向下一個節點的引用 (next)。
  1. LinkedList 類別：
  • 建構子 (constructor)：初始化一個鏈結串列，創建一個具有給定值的新節點，並將其設為 head 和 tail。初始長度為 1。
  • printList 方法：列印鏈結串列的所有節點的值。
  • getHead 方法：獲取並列印鏈結串列的頭部值。
  • getTail 方法：獲取並列印鏈結串列的尾部值。
  • getLength 方法：獲取並列印鏈結串列的長度。
  • makeEmpty 方法：清空鏈結串列，將 head、tail 和長度都設為零。
  • push 方法：在鏈結串列的尾部插入一個新節點。
  • pop 方法：刪除鏈結串列的尾部節點。
  • unshift 方法：在鏈結串列的頭部插入一個新節點。
  • shift 方法：刪除鏈結串列的頭部節點。
  • get 方法：根據索引獲取並返回相應位置的節點。
  • set 方法：根據索引設置相應位置的節點的值。
  • insert 方法：在指定索引處插入一個新節點。
  • remove 方法：刪除指定索引處的節點。
  • reverse 方法：反轉整個鏈結串列。
class Node {
  constructor(value){
    this.value = value;
    this.next = null;
  }
}
 
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }

  printList() {
    let temp = this.head;
    while (temp !== null) {
        console.log(temp.value);
        temp = temp.next;
    }
  }

  getHead() {
    if (this.head === null) {
        console.log("Head: null");
    } else {
        console.log("Head: " + this.head.value);
    }
  }

  getTail() {
    if (this.tail === null) {
        console.log("Tail: null");
    } else {
        console.log("Tail: " + this.tail.value);
    }
  }

  getLength() {
    console.log("Length: " + this.length);
  }

  makeEmpty() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.length++;
    return this;
  }

  pop() {
    if (this.length === 0) return undefined;
    let temp = this.head;
    let pre = this.head;
    while (temp.next) {
        pre = temp;
        temp = temp.next;
    }
    this.tail = pre;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
        this.head = null;
        this.tail = null;
    }
    return temp;
  }

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

  shift() {
    if (this.length === 0) return undefined;
    let temp = this.head;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
        this.tail = null;
    }
    temp.next = null;
    return temp;
  }

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

  set(index, value) {
    let temp = this.get(index);
    if (temp) {
        temp.value = value;
        return true;
    }
    return false;
  }

  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return this.push(value);
    if (index === 0) return this.unshift(value);
    
    const newNode = new Node(value);
    const temp = this.get(index - 1);
    newNode.next = temp.next;
    temp.next = newNode;
    this.length++;
    return true;
  }

  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const before = this.get(index - 1);
    const temp = before.next;

    before.next = temp.next;
    temp.next = null;
    this.length--;
    return temp;
  }

  reverse() {
    let temp = this.head;
    this.head = this.tail;
    this.tail = temp;

    let next = null;
    let prev = null;

    for (let i = 0; i < this.length; i++) {
      next = temp.next;
      temp.next = prev;
      prev = temp;
      temp = next;
    }
    return this;
  }
}

Linked List 跟 Array Operation 時間複雜度比較:

鏈結串列（Linked List） 陣列(Array)
Push O(1) O(1)
Pop O(n) O(1)
Shift O(1) O(n)
Unshift O(1) O(n)
Insert O(n) O(n)
Delete O(n) O(n)
Lookup by Index O(n) O(1)
Lookup by Value O(n) O(n)