Linked List

Linked List 是一種線性資料結構，與 Array 不同，Linked List 在電腦記憶體裡不需要連續的空間。它是把資料分散在記憶體各處，並透過每個 Node 內附帶的「pointer 」指向下一個 Node 的位址。

概念就像是一列「火車」，一節車廂連著一節車廂地串接起來。

核心組成： Node（Node）

Linked List 由數個 Node 組成，每個 Node 通常包含兩個部分：

• 資料（Data/Value）：實際要儲存的內容。
• 指標（Next）：記憶體位址，指向下一個 Node。最後一個 Node 的 next 則指向 null。

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

常見種類

Singly Linked List

每個 Node 只知道「下一個」是誰，只能從頭往後逛，不能回頭。

class SinglyLinkedList {
  constructor() {
    this.head = null;   // 指向「開頭」的 Node
    this.tail = null;   // 指向「結尾」的 Node
    this.length = 0;    // 記錄目前 Node 總數
  }

  // 1. 尾端新增 Node：O(1)
  push(val) {
    const newNode = new Node(val);
    
    if (!this.head) {
      // 如果原先 Linked List 是空的，新增 Node 同時是頭也是尾
      this.head = newNode;
      this.tail = this.head;
    } else {
      // Linked List 已有資料，新增 Node 接到目前尾巴的後面，並更新尾巴指標
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  // 2. 尾端刪除 Node：O(n) - 因為 Linked List 必須從頭走到倒數第二個 Node 來找新尾巴
  pop() {
    if (this.length === 0) return undefined;
    
    let currentNode = this.head; // 用來跑迴圈走到最後
    let newTail = currentNode;   // 用來追蹤倒數第二個 Node（即將成為新尾巴）
    
    // 當 currentNode 後面還有 Node 時，繼續往後移
    while (currentNode.next) {
      newTail = currentNode;
      currentNode = currentNode.next;
    }
    
    this.tail = newTail;     // 更新 tail 為倒數第二個 Node 上
    this.tail.next = null;   // 斷開連結
    this.length--;
    
    // 如果刪除後 Linked List 變空了，要把頭尾指針都清空
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return currentNode; // 回傳被刪除的 Node
  }

  // 3. 開頭刪除 Node：O(1)
  shift() {
    if (this.length === 0) return undefined;
    
    let shiftedNode = this.head;   // 暫存原本的頭
    this.head = shiftedNode.next;
    this.length--;
    
    // 如果刪到變空 Linked List，尾巴指標也要清空
    if (this.length === 0) {
      this.tail = null;
    }
    return shiftedNode;
  }

  // 4. 開頭新增 Node：O(1)
  unshift(val) {
    let newNode = new Node(val);
    
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  // 5. 獲取指定位置的 Node：O(n)
  get(index) {
    // 檢查邊界
    if (index < 0 || index >= this.length) return null;
    
    let count = 0;
    let currentNode = this.head;
    
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  // 6. 修改指定位置的 Node value：O(n) - 效能取決於 get()
  set(index, val) {
    let setNode = this.get(index);
    if (!setNode) return false;
    
    setNode.val = val;
    return true;
  }

  // 7. 在指定位置插入新 Node：O(n) - 尋找前一個 Node 需要 O(n)，但插入動作本身是 O(1)
  insert(index, val) {
    if (index < 0 || index > this.length) return false;

    // 如果要在最後面插入，直接用 push (!! 用來將回傳值強制轉成布林值 true)
    if (index === this.length) return !!this.push(val);

    // 如果要在最前面插入，直接用 unshift
    if (index === 0) return !!this.unshift(val);
    
    const newNode = new Node(val);
    const prevNode = this.get(index - 1);
    
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    this.length++;
    return true;
  }

  // 8. 刪除指定位置的 Node：O(n)
  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === this.length - 1) return this.pop();
    if (index === 0) return this.shift();
    
    var prevNode = this.get(index - 1);  // 找到要刪除位置的「前一個 Node」
    var removedNode = prevNode.next;     // 暫存即將被刪除的 Node
    
    prevNode.next = removedNode.next;    // 讓前一個 Node 跳過被刪除者，直接指向下下一個
    this.length--;
    return removedNode;
  }
}

Doubly Linked List

每個 Node 同時記錄「上一個」與「下一個」，可以雙向穿梭，但比較佔記憶體。

實作內容和 Singly Linked List 大同小異，只是雙向的 Node 多了一個指標。

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

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

  // 1. 尾端新增 Node：O(1)
  push(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

  // 2. 尾端刪除 Node：O(1) - 因為 Node 有前後指針，所以不需要寫迴圈來找到要刪除的 Node
  pop() {
    if (!this.head) return undefined;
    const poppedNode = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      poppedNode.prev = null;
    }
    this.length--;
    return poppedNode;
  }
  
  // 3. 開頭刪除 Node：O(1)
  shift() {
    if (!this.head) return undefined;
    const shiftedNode = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = shiftedNode.next;
      this.head.prev = null;
      shiftedNode.next = null;
    }
    this.length--;
    return shiftedNode;
  }

  // 4. 開頭新增 Node：O(1)
  unshift(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

  // 5. 獲取指定位置的 Node：O(n)
  get(index) {
    if (index < 0 || index >= this.length) return null;
    let count, currentNode;
    
    // 如果要找的位置靠近前半段，從「頭 (head)」出發往後找
    if (index <= this.length / 2) {
      count = 0;
      currentNode = this.head;
      while (count !== index) {
        currentNode = currentNode.next;
        count++;
      };
    } 
    // 如果要找的位置靠近後半段，從「尾 (tail)」出發往前找
    else {
      count = this.length - 1;
      currentNode = this.tail;
      while (count !== index) {
        currentNode = currentNode.prev;
        count--;
      }
    }
    return currentNode
  }

  // 6. 修改指定位置的 Node資料：O(n)
  set(index, val) {
    const setNode = this.get(index);
    if (!setNode) return false;
    setNode.val = val;
    return true;
  }

  // 7. 在指定位置插入新 Node：O(n) - 插入本身的指針重連動作是 O(1)
  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return !!this.unshift(val);
    if (index === this.length) return !!this.push(val);
    const newNode = new Node(val);
    const beforeNode = this.get(index - 1);
    const afterNode = beforeNode.next;

    beforeNode.next = newNode;
    newNode.prev = beforeNode;

    newNode.next = afterNode;
    afterNode.prev = newNode;

    this.length++;
    return true;
  }
  
  // 8. 刪除指定位置的 Node：O(n)
  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 removedNode = this.get(index);

    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;
    removedNode.prev = null;
    removedNode.next = null;

    this.length--;
    return removedNode;
  }
}

複雜度

操作種類	時間複雜度	原因與說明
開頭新增 / 刪除	O(1)	完美效能。只需更改 Head 的 pointer 指向，完全不影響其他 Node。
尾端新增 / 刪除	O(1) 或 O(n)	如果有記錄 Tail 就是 O(1)；若沒有，必須從 Head 數到尾，則是 O(n)。
中間特定位置新增/刪除	O(1)	只要已知該 Node，把 next 指標斷開並重新連上即可，不需挪移資料。
讀取資料 (Access)	O(n)	不支援隨機存取。想看第 50 個 Node，必須從第一個一路連過去。
搜尋資料 (Search)	O(n)	必須從 Head 開始，一個一個比對資料值直到找到為止。

適用情況

主要在以下 4 種情況下使用 Linked List：

1. 頻繁在一連串資料裡進行新增、刪除

• 情境：如果用 Array，在開頭插入一筆資料，則後面 100 萬筆資料都必須在記憶體中全部往後移一格（O(n)），極度消耗 CPU。
• 應用：用 Linked List 只需要改動新增 Node 與前後 Node 的指標（O(1)），後面 100 萬筆資料完全不用動。

2. 資料量完全無法預測、變動極大時

• 情境：Array 在底層需要連續空間。當 Array 滿了，電腦必須在記憶體找一塊更大的「連續空地」，把舊資料全部複製搬家過去（動態擴容）。
• 應用：Linked List 的記憶體是散落各處的。多一個資料就多申請一個小格子，不需要預先知道大小，也不需要搬動全部資料。

3. 作為其他進階資料結構的底層

許多經典資料結構，為了追求新增與刪除的極致效能，底層都會採用 Linked List：

• Queue 與 Stack：用 Linked List 實作可以確保新增和移除都是最佳效率的 O(1)。
• 處理 Hash Collision：發生碰撞時，最常用的「Separate Chaining」，即在格子後面掛一個 Linked List 串流同個 hash value 的 key-value pairs。
• Graph / Tree：Binary Tree 的左右子 Node、Graph 的 Adjacency List，本質上都是 Linked List 的變形。

4. 實際生活中的軟體功能

• 音樂播放器的「下一首 / 上一首」：通常會使用 Doubly Linked List，每首歌是一個 Node，記錄著前一首與下一首的歌是誰，還可以把最後一首連回第一首變成「循環播放」。
• 圖片檢視器、投影片切換：按下左右鍵切換上一張、下一張圖，邏輯與音樂播放器完全相同。
• 區塊鏈（Blockchain）：每一個 Block 都包含資料，並透過 hash 指向前一個區塊，這在結構上就是一個只能往前追溯的單向 Linked List。