鏈結串列（Linked List）教學：原理、程式碼與時間複雜度

鏈結串列解決什麼問題

陣列（Python 的 list）把元素放在一塊連續的記憶體中。讀取 a[i] 很快，但在最前面插入時，其餘元素都要往右移一格，成本是 O(n)。鏈結串列避開了這種搬移：每個元素各自存在一個節點裡，節點之間用參考相連，插入時只需改動幾個參考。

鏈結串列是許多其他資料結構的基礎：堆疊、佇列、雜湊表的桶（鏈結法處理碰撞）、LRU 快取，以及圖的相鄰串列。

用白話理解

想像一場尋寶遊戲：每條線索都告訴你下一條線索在哪裡。你無法直接跳到第 7 條線索，必須先依序走完第 1 到第 6 條。串列本身只記得第一個節點，稱為頭節點（head）；最後一個節點則不指向任何東西（None）。

實例演練：插入與刪除

從串列 3 -> 7 -> 9 開始。我們在 3 後面插入 5，再刪除 7。

1. 建立一個值為 5 的新節點。
2. 把 new.next 設為 3 後面的節點（也就是節點 7）。
3. 把 node3.next 設為新節點。此時串列變成 3 -> 5 -> 7 -> 9。
4. 要刪除 7，先從頭開始走，找到它前面的節點（5）。
5. 設定 node5.next = node5.next.next，就會跳過 7。串列變成 3 -> 5 -> 9。Python 的垃圾回收機制會釋放無法再被存取的節點。

以 Python 實作單向鏈結串列

這個類別保存頭節點的參考和一個大小計數器，支援在前端與尾端新增、刪除第一個符合的值，以及迭代走訪。

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    def push_front(self, value):
        self.head = Node(value, self.head)
        self.size += 1
    def push_back(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1
    def remove(self, value):
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False          # not found
        if prev is None:
            self.head = cur.next  # removing the head
        else:
            prev.next = cur.next
        self.size -= 1
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next

items = LinkedList()
for x in [3, 7, 9]:
    items.push_back(x)
items.push_front(1)
items.remove(7)
print(list(items), items.size)  # [1, 3, 9] 3

這裡的 push_back 要走過整個串列，所以是 O(n)。多維護一個 tail 參考就能降到 O(1)，實際的佇列實作就是這麼做的。

經典操作：反轉與環偵測

原地反轉串列是鏈結串列最常見的面試題。只要走過串列一次，把每個 next 指標轉向即可。

def reverse(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next     # remember the rest
        cur.next = prev    # turn the pointer around
        prev, cur = cur, nxt
    return prev            # new head
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
head = Node(1, Node(2, Node(3)))
head = reverse(head)
print(head.value, head.next.value, head.next.next.value)  # 3 2 1
print(has_cycle(head))  # False

has_cycle 使用 Floyd 龜兔賽跑演算法：慢指標每次走一步，快指標每次走兩步。如果串列有環，快指標最終會追上慢指標；如果沒有，快指標會走到 None。它只需要 O(1) 的額外記憶體。

時間與空間複雜度

實務上，即使某些操作鏈結串列的 Big O 較好，陣列往往還是更快，因為陣列元素在記憶體中相鄰，能充分利用 CPU 快取，而鏈結串列的節點是分散的。

變體與常見錯誤

• 忘記處理空串列：讀取 head.next 之前，一定要先檢查 head is None。
• 在儲存 next 之前就覆寫它，導致串列其餘部分遺失（見 reverse 中的 nxt）。
• 刪除第一個節點時沒有更新 head，或刪除最後一個節點時沒有更新 tail。
• 對很長的串列使用遞迴：Python 預設的遞迴上限約為 1000 層，用迴圈會更安全。
• 使用虛擬（哨兵）頭節點可以省去大部分特殊情況：每個真正的節點之前都會有一個節點。
• 在雙向鏈結串列中，每次插入和刪除都必須更新四個參考；漏掉一個就會悄悄破壞串列。

什麼時候該用鏈結串列，Python 又該用什麼

當你需要在兩端或中間已持有參考的位置插入、刪除，而且很少需要隨機存取時，就適合用鏈結串列。例如：LRU 快取（雙向鏈結串列加雜湊表）、記憶體配置器的空閒串列、復原歷史紀錄，或雜湊表的桶。

日常的 Python 程式碼很少需要自己寫。要用佇列或雙端佇列，請用 collections.deque，兩端的新增與彈出都是 O(1)；一般序列則用 list。自己寫鏈結串列適合用來學習、準備面試，以及需要像 LRU 快取那樣以 O(1) 拼接節點的時候。

from collections import deque
q = deque([1, 2, 3])
q.appendleft(0)
q.append(4)
print(q.popleft(), q.pop(), list(q))  # 0 4 [1, 2, 3]