Python 資料結構：鏈結串列（Linked List）(02)

Linked List（鏈結串列）是一種由節點（Node）組成的動態線性結構。每個節點像火車車廂般彼此相連：前者指向後者，最後一節以 None 作為終點。理解鏈結串列，能為後續的 Stack、Queue、Tree、Graph 打下穩固基礎。

什麼是 Linked List？

基本概念

• Linked List：由多個節點依序串接而成的線性資料結構。
• 非連續記憶體：節點在記憶體中不需連續存放，靠「連結（指標）」維持關係。

節點的組成

• 資料（Data）：任意型別（數字、字串、物件…）。
• 連結（Link/Pointer）：指向下一個節點；最後一節指向 None。

與陣列的比較

• Linked List 優勢
  • 動態大小：可彈性增刪節點
  • 插入/刪除高效：更新指標即完成（通常 O(1)）
  • 無需預先分配連續空間
• 陣列優勢
  • 隨機存取 O(1)
  • 記憶體局部性佳、快取友善

鏈結串列基本功能

有了節點類別後，我們可以開始建構實際的鏈結串列。根據使用需求，可以定義各種方法。

取得頭節點

獲取串列的第一個節點，就像查看隊伍中的第一個項目

新增節點

在串列開頭添加新的節點

列印串列

按順序印出串列中的所有值

移除節點

刪除具有特定值的節點

LinkedList 類別：初始化與基本結構

class LinkedList:
    def __init__(self, value=None):
        self.head_node = Node(value) if value else None
    
    def get_head_node(self):
        return self.head_node

• head_node 是整個串列的起點；藉由它能遍歷全串列。
• 可選擇以初始值建立第一個節點，或以空串列（None）起步。

插入新節點（O(1)）

將新節點插在串列開頭，不需遍歷，效率極高。

def insert_beginning(self, new_value):
    new_node = Node(new_value)
    new_node.set_link_node(self.head_node)
    self.head_node = new_node

流程

1. 以 new_value 建立新節點
2. 新節點連到目前的 head
3. 更新 head 為新節點

列印串列（遍歷）

將整條串列轉為易讀字串（如 "a -> b -> c"）：

def stringify_list(self):
    values = []
    current_node = self.head_node
    while current_node:
        values.append(str(current_node.get_value()))
        current_node = current_node.get_link_node()
    return " -> ".join(values)

遍歷步驟

1. 從 head 開始
2. 逐一取值並前進到下一節點
3. None 代表結束

---

刪除節點（移除第一個匹配值）

需要處理兩種情況：刪除 head、刪除中間節點。

def remove_node(self, value_to_remove):
    current_node = self.head_node
    
    # 刪除 head
    if current_node and current_node.get_value() == value_to_remove:
        self.head_node = current_node.get_link_node()
        return
    
    # 刪除中間節點
    while current_node:
        next_node = current_node.get_link_node()
        if next_node and next_node.get_value() == value_to_remove:
            current_node.set_link_node(next_node.get_link_node())
            break
        current_node = next_node

• 刪除 head：直接把 head 指向下一個節點。
• 刪除中間節點：讓前一節點跳過目標節點，改連到其下一節點。
• Python 會自動進行 垃圾回收（Garbage Collection），無參考的節點會被釋放。

使用範例

# 建立新串列
ll = LinkedList()

# 插入（頭插，逆序形成 a -> b -> c）
ll.insert_beginning("c")
ll.insert_beginning("b")
ll.insert_beginning("a")

print(ll.stringify_list())      # a -> b -> c

# 刪除節點
ll.remove_node("b")
print(ll.stringify_list())      # a -> c

執行流程

1. 空串列起步
2. 依序頭插 c, b, a → 實際順序為 a -> b -> c
3. 移除 b → a -> c