Linked List

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

白話理解

概念就像是一列「火車」，一節車廂連著一節車廂串接起來，車廂彼此不需要緊貼在一起，只要知道「下一節車廂在哪裡」就能一路連下去。要在車廂中間加掛一節新車廂，也只需要重新勾住前後兩節，不用把整列火車搬家。

核心組成： Node（Node）

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

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

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

JavaScript

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

Java

class Node<T> {
    T val;
    Node<T> next;

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

常見種類

Singly Linked List

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

Python

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 指向「開頭」的 Node
        self.tail = None  # 指向「結尾」的 Node
        self.length = 0   # 記錄目前 Node 總數

    # 1. 尾端新增 Node：O(1)
    def push(self, val):
        new_node = Node(val)

        if not self.head:
            # 如果原先 Linked List 是空的，新增 Node 同時是頭也是尾
            self.head = new_node
            self.tail = self.head
        else:
            # Linked List 已有資料，新增 Node 接到目前尾巴的後面，並更新尾巴指標
            self.tail.next = new_node
            self.tail = new_node
        self.length += 1
        return self

    # 2. 尾端刪除 Node：O(n) - 因為 Linked List 必須從頭走到倒數第二個 Node 來找新尾巴
    def pop(self):
        if self.length == 0:
            return None

        current_node = self.head  # 用來跑迴圈走到最後
        new_tail = current_node   # 用來追蹤倒數第二個 Node（即將成為新尾巴）

        # 當 current_node 後面還有 Node 時，繼續往後移
        while current_node.next:
            new_tail = current_node
            current_node = current_node.next

        self.tail = new_tail    # 更新 tail 為倒數第二個 Node 上
        self.tail.next = None   # 斷開連結
        self.length -= 1

        # 如果刪除後 Linked List 變空了，要把頭尾指針都清空
        if self.length == 0:
            self.head = None
            self.tail = None
        return current_node  # 回傳被刪除的 Node

    # 3. 開頭刪除 Node：O(1)
    def shift(self):
        if self.length == 0:
            return None

        shifted_node = self.head  # 暫存原本的頭
        self.head = shifted_node.next
        self.length -= 1

        # 如果刪到變空 Linked List，尾巴指標也要清空
        if self.length == 0:
            self.tail = None
        return shifted_node

    # 4. 開頭新增 Node：O(1)
    def unshift(self, val):
        new_node = Node(val)

        if not self.head:
            self.head = new_node
            self.tail = self.head
        else:
            new_node.next = self.head
            self.head = new_node
        self.length += 1
        return self

    # 5. 獲取指定位置的 Node：O(n)
    def get(self, index):
        # 檢查邊界
        if index < 0 or index >= self.length:
            return None

        count = 0
        current_node = self.head

        while count < index:
            count += 1
            current_node = current_node.next
        return current_node

    # 6. 修改指定位置的 Node value：O(n) - 效能取決於 get()
    def set(self, index, val):
        set_node = self.get(index)
        if not set_node:
            return False

        set_node.val = val
        return True

    # 7. 在指定位置插入新 Node：O(n) - 尋找前一個 Node 需要 O(n)，但插入動作本身是 O(1)
    def insert(self, index, val):
        if index < 0 or index > self.length:
            return False

        # 如果要在最後面插入，直接用 push
        if index == self.length:
            return bool(self.push(val))

        # 如果要在最前面插入，直接用 unshift
        if index == 0:
            return bool(self.unshift(val))

        new_node = Node(val)
        prev_node = self.get(index - 1)

        new_node.next = prev_node.next
        prev_node.next = new_node
        self.length += 1
        return True

    # 8. 刪除指定位置的 Node：O(n)
    def remove(self, index):
        if index < 0 or index >= self.length:
            return None
        if index == self.length - 1:
            return self.pop()
        if index == 0:
            return self.shift()

        prev_node = self.get(index - 1)  # 找到要刪除位置的「前一個 Node」
        removed_node = prev_node.next    # 暫存即將被刪除的 Node

        prev_node.next = removed_node.next  # 讓前一個 Node 跳過被刪除者，直接指向下下一個
        self.length -= 1
        return removed_node

JavaScript

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;
  }
}

Java

class SinglyLinkedList<T> {
    Node<T> head; // 指向「開頭」的 Node
    Node<T> tail; // 指向「結尾」的 Node
    int length;   // 記錄目前 Node 總數

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

    // 1. 尾端新增 Node：O(1)
    SinglyLinkedList<T> push(T val) {
        Node<T> newNode = new Node<>(val);

        if (this.head == null) {
            // 如果原先 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 來找新尾巴
    Node<T> pop() {
        if (this.length == 0) return null;

        Node<T> currentNode = this.head; // 用來跑迴圈走到最後
        Node<T> newTail = currentNode;   // 用來追蹤倒數第二個 Node（即將成為新尾巴）

        // 當 currentNode 後面還有 Node 時，繼續往後移
        while (currentNode.next != null) {
            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)
    Node<T> shift() {
        if (this.length == 0) return null;

        Node<T> shiftedNode = this.head; // 暫存原本的頭
        this.head = shiftedNode.next;
        this.length--;

        // 如果刪到變空 Linked List，尾巴指標也要清空
        if (this.length == 0) {
            this.tail = null;
        }
        return shiftedNode;
    }

    // 4. 開頭新增 Node：O(1)
    SinglyLinkedList<T> unshift(T val) {
        Node<T> newNode = new Node<>(val);

        if (this.head == null) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }

    // 5. 獲取指定位置的 Node：O(n)
    Node<T> get(int index) {
        // 檢查邊界
        if (index < 0 || index >= this.length) return null;

        int count = 0;
        Node<T> currentNode = this.head;

        while (count < index) {
            count++;
            currentNode = currentNode.next;
        }
        return currentNode;
    }

    // 6. 修改指定位置的 Node value：O(n) - 效能取決於 get()
    boolean set(int index, T val) {
        Node<T> setNode = get(index);
        if (setNode == null) return false;

        setNode.val = val;
        return true;
    }

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

        // 如果要在最後面插入，直接用 push
        if (index == this.length) return push(val) != null;

        // 如果要在最前面插入，直接用 unshift
        if (index == 0) return unshift(val) != null;

        Node<T> newNode = new Node<>(val);
        Node<T> prevNode = get(index - 1);

        newNode.next = prevNode.next;
        prevNode.next = newNode;
        this.length++;
        return true;
    }

    // 8. 刪除指定位置的 Node：O(n)
    Node<T> remove(int index) {
        if (index < 0 || index >= this.length) return null;
        if (index == this.length - 1) return pop();
        if (index == 0) return shift();

        Node<T> prevNode = get(index - 1);   // 找到要刪除位置的「前一個 Node」
        Node<T> removedNode = prevNode.next; // 暫存即將被刪除的 Node

        prevNode.next = removedNode.next;    // 讓前一個 Node 跳過被刪除者，直接指向下下一個
        this.length--;
        return removedNode;
    }
}

Doubly Linked List

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

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

Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    # 1. 尾端新增 Node：O(1)
    def push(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = self.head
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return self

    # 2. 尾端刪除 Node：O(1) - 因為 Node 有前後指針，所以不需要寫迴圈來找到要刪除的 Node
    def pop(self):
        if not self.head:
            return None
        popped_node = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.tail = popped_node.prev
            self.tail.next = None
            popped_node.prev = None
        self.length -= 1
        return popped_node

    # 3. 開頭刪除 Node：O(1)
    def shift(self):
        if not self.head:
            return None
        shifted_node = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = shifted_node.next
            self.head.prev = None
            shifted_node.next = None
        self.length -= 1
        return shifted_node

    # 4. 開頭新增 Node：O(1)
    def unshift(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = self.head
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node
        self.length += 1
        return self

    # 5. 獲取指定位置的 Node：O(n)
    def get(self, index):
        if index < 0 or index >= self.length:
            return None

        # 如果要找的位置靠近前半段，從「頭 (head)」出發往後找
        if index <= self.length / 2:
            count = 0
            current_node = self.head
            while count != index:
                current_node = current_node.next
                count += 1
        # 如果要找的位置靠近後半段，從「尾 (tail)」出發往前找
        else:
            count = self.length - 1
            current_node = self.tail
            while count != index:
                current_node = current_node.prev
                count -= 1
        return current_node

    # 6. 修改指定位置的 Node 資料：O(n)
    def set(self, index, val):
        set_node = self.get(index)
        if not set_node:
            return False
        set_node.val = val
        return True

    # 7. 在指定位置插入新 Node：O(n) - 插入本身的指針重連動作是 O(1)
    def insert(self, index, val):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return bool(self.unshift(val))
        if index == self.length:
            return bool(self.push(val))
        new_node = Node(val)
        before_node = self.get(index - 1)
        after_node = before_node.next

        before_node.next = new_node
        new_node.prev = before_node

        new_node.next = after_node
        after_node.prev = new_node

        self.length += 1
        return True

    # 8. 刪除指定位置的 Node：O(n)
    def remove(self, index):
        if index < 0 or index >= self.length:
            return None
        if index == 0:
            return self.shift()
        if index == self.length - 1:
            return self.pop()
        removed_node = self.get(index)

        removed_node.prev.next = removed_node.next
        removed_node.next.prev = removed_node.prev
        removed_node.prev = None
        removed_node.next = None

        self.length -= 1
        return removed_node

JavaScript

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;
  }
}

Java

class Node<T> {
    T val;
    Node<T> next;
    Node<T> prev;

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

class DoublyLinkedList<T> {
    Node<T> head;
    Node<T> tail;
    int length;

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

    // 1. 尾端新增 Node：O(1)
    DoublyLinkedList<T> push(T val) {
        Node<T> newNode = new Node<>(val);
        if (this.head == null) {
            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
    Node<T> pop() {
        if (this.head == null) return null;
        Node<T> 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)
    Node<T> shift() {
        if (this.head == null) return null;
        Node<T> 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)
    DoublyLinkedList<T> unshift(T val) {
        Node<T> newNode = new Node<>(val);
        if (this.head == null) {
            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)
    Node<T> get(int index) {
        if (index < 0 || index >= this.length) return null;
        int count;
        Node<T> currentNode;

        // 如果要找的位置靠近前半段，從「頭 (head)」出發往後找
        if (index <= this.length / 2.0) {
            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)
    boolean set(int index, T val) {
        Node<T> setNode = get(index);
        if (setNode == null) return false;
        setNode.val = val;
        return true;
    }

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

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

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

        this.length++;
        return true;
    }

    // 8. 刪除指定位置的 Node：O(n)
    Node<T> remove(int index) {
        if (index < 0 || index >= this.length) return null;
        if (index == 0) return shift();
        if (index == this.length - 1) return pop();
        Node<T> removedNode = 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。

5. 搭配 Two Pointers 解題

Linked List 相關的題目時常會搭配 Two Pointers 的「Fast & Slow Pointers」手法，用來判斷是否有環、找出中點，或是找出倒數第 k 個節點，這是刷題時非常常見的組合。

判斷是否有環、找出環的起點，可以參考 Floyd's Cycle Detection 的詳細說明。

常見誤區

• 斷開指標的順序寫錯，導致「斷了線」：例如在 insert 時，如果先把 prevNode.next 指向新節點，卻忘記事先把新節點的 next 接到原本 prevNode.next 的對象，後面的節點就會直接遺失，永遠找不回來。動手前建議先畫圖，確認「新指標接好之後，才能覆蓋舊指標」。
• 忘記同步更新 head、tail 或 length：尤其是刪到只剩最後一個元素、或刪光整個 Linked List 時，很容易漏掉把 head／tail 設回 null，導致之後的操作出現意外行為。
• 誤以為可以像 Array 一樣直接用 index 存取：Linked List 沒有隨機存取的能力，get(index) 必須從頭（或利用 Doubly Linked List 從尾）一步步走過去，是 O(n) 而不是 O(1)，這也是它和 Array 最核心的取捨差異。