演算法圖鑑
Linked List · 01 / 05

Singly Linked List單向鏈結串列

節點、指標、頭節點與哨兵節點。

用在：理解指標、實作佇列與堆疊

時間複雜度插入 O(1)、查 O(n)
空間複雜度O(n)
難度入門
前置知識Array & Dynamic Array

01為什麼需要它

作業系統怎麼管理「等著跑的程序」

程序隨時會建立、結束、被暫停。要在任何位置 O(1) 插入或移除，而且沒有人知道最多會有幾個。

為什麼用它串列的節點散落在記憶體各處，靠指標串起來。插入刪除只改兩個指標，不用搬其他元素，也不用預留連續空間。Linux 核心到處都是串列。

雜湊表裡碰撞的那條鏈

上一章的雜湊表用「鏈結法」處理碰撞：同一個桶裡的 key 串在一起。那條鏈就是單向串列。

為什麼用它鏈通常很短、只在尾端加、只會整條掃過，串列剛好夠用又不浪費空間。學會它，就看懂了雜湊表的實作。

指標操作的基本功

樹、圖、LRU 快取、跳躍串列，全部是「節點 + 指標」的結構。接錯一個指標，整條就斷了或繞成環。

為什麼用它單向串列是最簡單的指標結構。在這裡練熟「先接新的、再拆舊的」、哨兵節點、邊界情況，之後所有指標題都是同一套動作。

看到這些關鍵字就想到它：不知道總共幾個、頻繁在中間插入刪除、node.next、head、指標接來接去、面試裡的 ListNode。

02核心概念

單向鏈結串列由節點組成，每個節點只記兩件事：自己的值，和下一個節點在哪（next）。最後一個節點的 next 是 None。整條串列只靠一個 head 指標抓住開頭，其他節點都要從 head 沿著 next 走過去。

它和陣列是一組對照。陣列靠連續記憶體算位址，所以隨機存取 O(1)、中間插入 O(n)。串列放棄連續，所以已知位置的插入刪除 O(1)（只改指標），但存取第 i 個要走 i 步，O(n)。查找一個值兩者都是 O(n)。一句話：陣列擅長「讀」，串列擅長「在已知位置改結構」。

實務上單向串列本身不常直接用，因為每個節點多一個指標、又對快取不友善。它真正的價值是指標操作的訓練與作為更複雜結構的零件。兩個習慣要養成：哨兵節點（dummy head）讓「刪 head」「插在最前面」不用特判；改指標時先接新的再拆舊的，才不會弄丟後半段。

03演算法步驟

  1. 1插入在節點 p 之後：新節點的 next 先指向 p.next，再把 p.next 改指向新節點。順序反了會弄丟 p 後面整段。
  2. 2刪除節點 p 之後的那個：p.next = p.next.next。被跳過的節點沒人指向它，就等於消失了（C++ 要手動 delete）。
  3. 3任何要碰 head 的操作，先建一個 dummy 節點指向 head，操作完回傳 dummy.next。這樣「刪除 head」和「刪除中間」是同一段程式。
  4. 4走訪用 while cur:，需要「前一個節點」時多留一個 prev。要停在最後一個節點用 while cur.next:。
  5. 5寫完先用三種輸入檢查：空串列、只有一個節點、目標在最後一個。指標題的 bug 幾乎都在邊界。

04互動示範

比較每個操作走過幾個節點。開頭插入不用走，尾端插入和讀取第 4 個都得從 head 一路走；刪除只改一個指標，後面的節點完全不動。

節點（值 | next）
head→12•→7•→3•→9•→15•→null
走過的節點新節點目標節點
成本 05 個節點，每個節點記自己的值和「下一個在哪」。只能從 head 開始一個一個往後走。

05程式碼

手寫一個最小的串列類別，每個方法標上複雜度；最後用哨兵節點示範「刪除所有等於 val 的節點」怎麼把 head 的特判消掉。

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next          # 指向下一個節點，最後一個是 None


class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def push_front(self, val):            # O(1)
        self.head = Node(val, self.head)  # 新節點的 next 指向舊 head
        self.size += 1

    def push_back(self, val):             # O(n)：沒有 tail 指標就得走到底
        node = Node(val)
        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 get(self, index):                 # O(n)：只能一個一個走
        cur = self.head
        for _ in range(index):
            cur = cur.next
        return cur.val

    def insert_after(self, node, val):    # O(1)：已經拿到節點的話
        node.next = Node(val, node.next)
        self.size += 1

    def remove_after(self, node):         # O(1)：跳過下一個節點
        if node.next:
            node.next = node.next.next
            self.size -= 1

    def find(self, val):                  # O(n)
        cur = self.head
        while cur and cur.val != val:
            cur = cur.next
        return cur


# 哨兵（dummy）節點：讓「刪除 head」不用特判
def remove_all(head, val):
    dummy = Node(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next      # 跳過
        else:
            cur = cur.next
    return dummy.next

06練習題

  • LeetCode 707Design Linked ListMedium
  • LeetCode 203Remove Linked List Elements（哨兵節點）Easy
  • LeetCode 83Remove Duplicates from Sorted ListEasy
  • LeetCode 237Delete Node in a Linked List（沒有前一個節點怎麼刪）Medium
  • LeetCode 19Remove Nth Node From End of ListMedium
上一篇—下一篇Doubly Linked List