跳轉到

2.2 單向與雙向鏈結串列#

概念說明#

鏈結串列（linked list） 用「節點 + 指標」把資料串起來。每個節點存放資料本身與指向下一個節點的參考。單向串列只能往一個方向走；雙向串列的節點額外記住前一個節點，因此可以反向走訪，也更容易在 O(1) 內刪除「已知節點」。

單向串列通常再多維護一個頭指標 head 指向第一個節點；雙向串列則常搭配哨兵節點（sentinel / dummy node）：一個不存資料的假節點環在頭尾之間，讓「第一個節點」與「最後一個節點」的增刪都變成普通的中間操作，省去一堆邊界判斷。

操作步驟（以雙向串列為例）#

  1. append(x)：在哨兵前插入新節點——new.prev = tail_prev、new.next = sentinel、再把兩側指標補上。
  2. insert_before(node, x)：新節點夾在 node.prev 與 node 之間，修改四個指標。
  3. remove(node)：把 node.prev.next = node.next、node.next.prev = node.prev，節點即脫離串列。
  4. search(x)：從第一個節點開始逐一比對，走到哨兵即為未找到。

Python 實作#

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

class DoublyLinkedList:
    def __init__(self):
        self._sent = Node(None)      # 哨兵節點
        self._sent.prev = self._sent
        self._sent.next = self._sent
        self._size = 0

    def __len__(self):
        return self._size

    def _insert_between(self, val, pred, succ):
        node = Node(val)
        node.prev, node.next = pred, succ
        pred.next = node
        succ.prev = node
        self._size += 1
        return node

    def append(self, val):           # 尾端加入
        return self._insert_between(val, self._sent.prev, self._sent)

    def appendleft(self, val):       # 頭端加入
        return self._insert_between(val, self._sent, self._sent.next)

    def remove(self, node):          # O(1) 刪除已知節點
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None
        self._size -= 1
        return node.val

    def search(self, val):           # O(n)
        cur = self._sent.next
        while cur is not self._sent:
            if cur.val == val:
                return cur
            cur = cur.next
        return None

    def reverse(self):               # 原地反轉
        cur = self._sent.next
        while cur is not self._sent:
            cur.prev, cur.next = cur.next, cur.prev
            cur = cur.prev           # 反轉後 prev 才是「下一個」
        self._sent.prev, self._sent.next = self._sent.next, self._sent.prev

    def __iter__(self):
        cur = self._sent.next
        while cur is not self._sent:
            yield cur.val
            cur = cur.next

# 動手玩
dll = DoublyLinkedList()
for x in [1, 2, 3]:
    dll.append(x)
dll.appendleft(0)
print(list(dll))          # [0, 1, 2, 3]
node = dll.search(2)
dll.remove(node)
print(list(dll))          # [0, 1, 3]
dll.reverse()
print(list(dll))          # [3, 1, 0]

單向串列是雙向串列的簡化版：節點只有 val 與 next，只需頭指標。代價是無法 O(1) 刪除已知節點（要先找到其前身），也無法反向走訪。練習題會請你實作它。

複雜度分析#

操作 單向 雙向
頭端插入 O(1) O(1)
尾端插入 O(n)（除非多維 tail） O(1)
刪除已知節點 O(n)（需找前身） O(1)
搜尋 O(n) O(n)
空間 每節點 1 個指標 每節點 2 個指標

練習#

  1. 實作 SinglyLinkedList：含 append、appendleft、remove_head、search、reverse，並用雙向版相同測試驗證。
  2. 「刪除值為 x 的節點」在單向串列為何是 O(n)？描述一個 O(1) 刪除的偷吃步（提示：複製下一節點的值來覆蓋，再刪下一節點），它有什麼限制？
  3. 用鏈結串列實作「迴圈偵測」：判斷單向串列是否有環（提示：快慢指標），分析其空間複雜度為何能是 O(1)。