深度探秘

什麼讓一個結構叫做「線性」？

線性結構的本質

堆疊 (stack)、佇列 (queue)、雙端佇列 (deque)、串列 (list) 都是同一家族：它們的項目會依照「何時、從哪一端被加入或移除」而保持一個固定的排列順序。

關鍵觀念：一個項目一旦放進去，它相對於前後鄰居的位置就固定了，不會自己亂跑。

我們可以把線性結構想成有兩端：

• 有時叫「左 / 右」
• 有時叫「前 (front) / 後 (rear)」
• 有時叫「頂 (top) / 底 (base)」

名字不重要，真正決定一個結構是哪一種的，是「加入」和「移除」分別發生在哪一端。

生活妙喻

一條走廊，兩個門

想像一條只有兩個門的走廊

把線性結構想成一條狹窄的走廊，裡面排著人，走廊只有頭尾兩個門。

• 如果規定「只能從同一個門進出」，那後進來的人擋在門口，反而最先出去——這就是堆疊。
• 如果規定「從後門進、從前門出」，先進來的人先到前門出去——這就是佇列。
• 如果兩個門都能自由進出——這就是雙端佇列。

走廊本身（資料）都一樣，是「門的規則」造就了完全不同的結構與用途。

flowchart LR
  A[後門 rear] --> B[人 人 人 人] --> C[前門 front]

實用超能力

為什麼這四個觀念這麼重要？

簡單卻威力強大

這四個觀念看似簡單，卻是電腦科學中最常用的工具，出現在無數演算法裡：

• 瀏覽器的「上一頁」用堆疊
• 印表機排隊、作業系統排程用佇列
• 編譯器檢查括號是否成對用堆疊
• 鍵盤打字緩衝區用佇列

辨認問題的訣竅：當你發現一個問題有「最後處理的要先回頭」（反轉）的味道，多半是堆疊；當你發現「先來先服務」的公平排隊味道，多半是佇列。

接下來幾節我們會一個一個深入，先從堆疊開始。

深度探秘

後進先出 LIFO

top) 進出的有序集合，後進先出。">堆疊 Stack

堆疊是一種有序集合，新增與移除永遠發生在同一端，這一端叫 top（頂），另一端叫 base（底）。

• 越靠近 base 的項目，待在堆疊裡越久（最早放進去）。
• 最近加入的項目在 top，會最先被移除。

這個排序原則叫做 LIFO（last-in first-out，後進先出）：新的在上，舊的在下。

flowchart TD
  T[top 最新 最先離開] --> A[項目3]
  A --> B[項目2]
  B --> C[項目1 base 最舊 最後離開]

生活妙喻

桌上的一疊書

桌上的一疊書

想像你在桌上一本一本疊書。能看到封面的，只有最上面那一本。要拿下面的書，必須先把上面的搬開。

餐廳的托盤架也是：你拿走最上面那個，露出下一個給後面的人。

最神奇的是反轉性質：你依序疊上 A、B、C，拿下來的順序卻是 C、B、A——移除順序剛好是加入順序的相反。

這個「反轉」特性，正是堆疊在無數演算法中大放異彩的原因。

flowchart LR
  subgraph 放入
  P[A 然後 B 然後 C]
  end
  subgraph 取出
  Q[C 然後 B 然後 A]
  end
  P --> Q

實用超能力

反轉就是它的拿手好戲

堆疊能做什麼？

因為堆疊天生會反轉順序，許多需要「回頭」的場景都靠它：

• 瀏覽器上一頁：每造訪一頁就把網址 push 進堆疊，按上一頁就 pop 出來，順著反方向走回去。
• 反轉字串：把字元一個個 push 進去，再一個個 pop 出來，就得到反過來的字串。
• 撤銷 (undo)：每個動作 push 進堆疊，按撤銷就 pop 出最近的動作。

下一節我們會把堆疊的行為正式定義成抽象資料型別 (ADT)，並用 Python 實作出來。

深度探秘

六個操作定義堆疊

堆疊抽象資料型別 (ADT)

ADT 只描述「能做什麼」，不管「怎麼做到」。堆疊 ADT 有六個操作：

當我們給 ADT 一個實際的程式實作，這個實作就稱為資料結構 (data structure)。

peek 和 pop 的差別很關鍵：peek 只「偷看」不動堆疊，pop 會「拿走」並改變堆疊。

生活妙喻

餐廳點餐單 vs 廚房做法

菜單與廚房

ADT 就像餐廳的菜單：上面寫著「你可以點什麼」（push、pop、peek…），但沒寫廚房怎麼煮。

資料結構則是廚房的做法：同一道菜，可以用不同方式煮出來。

用 Python list 實作堆疊時，我們可以選「list 的末端當 top」或「list 的開頭當 top」——兩種菜單看起來一樣，但廚房效率差很多：

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)   # 末端當 top，O(1)
    def pop(self):
        return self.items.pop()   # O(1)
    def peek(self):
        return self.items[len(self.items) - 1]
    def size(self):
        return len(self.items)

實用超能力

選對那一端，效能差很多

末端 vs 開頭：O(1) vs O(n)

若改成「list 開頭當 top」，push 要用 insert(0, item)、pop 要用 pop(0)：

def push(self, item):
    self.items.insert(0, item)   # 開頭插入，O(n)
def pop(self):
    return self.items.pop(0)     # 開頭移除，O(n)

兩種實作在邏輯上完全等價（這正是抽象的威力），但效能不同：

• 用末端：append 與 pop() 都是 $O(1)$，不管堆疊多大都一樣快。
• 用開頭：insert(0) 與 pop(0) 都是 $O(n)$，因為其餘元素都要往後挪一格。

結論：實作可以換，但要懂得選效能好的那一種。

深度探秘

什麼叫括號平衡？

巢狀。">平衡的括號

平衡 (balanced) 指每個開符號都有對應的閉符號，而且配對正確巢狀。

正確的例子：(()()())、(((())))、(()((())()))

不正確的例子：((((((())、()))、(()()(()

關鍵觀察：由左往右處理時，最近的那個開括號，必須和下一個閉括號配對。閉括號是由內而外、依出現的相反順序去配對的。

「相反順序配對」＝反轉的味道＝堆疊！

flowchart LR
  A[讀到 開括號] --> B[push 進堆疊]
  C[讀到 閉括號] --> D[pop 一個來配對]

生活妙喻

俄羅斯娃娃

一層層的俄羅斯娃娃

把每個開括號想成打開一個俄羅斯娃娃，每個閉括號想成把它蓋回去。

• 你最後打開的那個，必須最先蓋回去（後進先出）。
• 全部蓋完後，桌上應該一個沒蓋的都不剩——這就是「堆疊最後必須為空」。

如果你想蓋回去卻發現桌上根本沒有打開的娃娃（堆疊是空的），代表多了一個閉括號——不平衡！

實用超能力

演算法與多種括號

par_checker 演算法

def par_checker(symbol_string):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbol_string) and balanced:
        symbol = symbol_string[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.is_empty():
                balanced = False   # 沒有開括號可配對
            else:
                s.pop()
        index = index + 1
    return balanced and s.is_empty()

推廣到多種括號 ()[]{}：閉括號出現時，不只要堆疊非空，還要檢查 pop 出的開符號型別相符。用一個 matches 輔助函式比對 ([{與)]}在字串中的相同位置即可。

所以 {{([][])}()} 平衡，但 [{()] 不平衡（型別不符）。

深度探秘

Divide by 2 演算法

為什麼又是堆疊？

要把十進位整數轉成二進位，用的是 餘數、用堆疊反轉，得到二進位表示的演算法。">Divide by 2（不斷除以 2） 演算法：

1. 把數字不斷除以 2，每次記下餘數（0 或 1）。
2. 第一次的餘數告訴你個位是奇是偶；但它其實會是二進位結果的最後一位。
3. 也就是說，先算出的餘數要排在最後——又是反轉！所以用堆疊。

例如 $233_{10} = 11101001_2$，可拆解為：

$$233 = 1\times2^7 + 1\times2^6 + 1\times2^5 + 0\times2^4 + 1\times2^3 + 0\times2^2 + 0\times2^1 + 1\times2^0$$

生活妙喻

撕號碼牌再倒著貼

撕號碼牌

想像你一邊除以 2，一邊把每個餘數寫在便條紙上，疊在桌上。

• 第一張（最先算出）壓在最底下。
• 全部算完後，你從最上面一張張撕下來貼成一排。

這樣最後算出的餘數排在最前面，最先算出的排在最後——順序剛好被堆疊反轉過來，得到正確的二進位字串。

flowchart TD
  A[233 除2 餘1 push] --> B[116 除2 餘0 push]
  B --> C[58 除2 餘0 push]
  C --> D[繼續直到 0]
  D --> E[從 top 一個個 pop 串成結果]

實用超能力

推廣到任意進位

從 Divide by 2 到 Divide by base

def base_converter(dec_number, base):
    digits = "0123456789ABCDEF"
    rem_stack = Stack()
    while dec_number > 0:
        rem = dec_number % base
        rem_stack.push(rem)
        dec_number = dec_number // base
    new_string = ""
    while not rem_stack.is_empty():
        new_string = new_string + digits[rem_stack.pop()]
    return new_string

把「除以 2」換成「除以 base」就能轉任意進位（2 到 16）。

超過 10 進位的小麻煩：餘數可能是 10～15，沒辦法用單一數字表示。解法是準備一個字元表 "0123456789ABCDEF"，餘數當索引——餘數 13 就取出 D。這就是十六進位用 A～F 的由來。

深度探秘

運算子站在哪？

三種運算式表示法

差別只在於運算子相對於運算元的位置：

• 優先序與括號輔助。">中序 (infix)：運算子在兩個運算元中間，如 A + B。這是我們最熟悉的寫法。
• 前序 (prefix)：運算子在運算元前面，如 + A B。
• 後序 (postfix)：運算子在運算元後面，如 A B +。

注意：不管哪種表示法，運算元的相對順序都不變，只有運算子在移動。

生活妙喻

為什麼中序最麻煩？

中序需要『額外規矩』

看 A + B * C，到底是先加還是先乘？中序之所以不會搞混，是因為我們腦中偷偷套用了兩條額外規矩：

1. 優先序 (precedence)：乘除高於加減。
2. 結合律 (associativity)：同優先序由左到右。
3. 還可以用括號強制改變順序。

中序就像講話需要靠語氣與上下文才懂的語言——容易產生歧義。

而前序與後序就像把每個動作的順序講得清清楚楚的機器指令，完全不需要括號，因為運算子的位置已經把順序講死了。

實用超能力

用全括號法手動轉換

全括號 (fully parenthesized) 轉換法

要把中序轉成前序或後序，先依優先序把式子完全加上括號，每個運算子一對括號：

A + B * C + D → ((A + (B * C)) + D)

然後把每個運算子搬到它那對括號的位置：

• 搬到右括號位置、刪掉對應左括號 → 後序：A B C * + D +
• 搬到左括號位置、刪掉對應右括號 → 前序：+ + A * B C D

flowchart TD
  A[中序 A加B乘C] --> B[全括號 開A加開B乘C閉閉]
  B --> C[運算子移到右括號 變後序]
  B --> D[運算子移到左括號 變前序]

為什麼電腦愛用後序？因為求值時不需要回頭看優先序，也不需要括號，一路掃過去用堆疊就能算。

深度探秘

中序轉後序：用堆疊暫存運算子

為什麼運算子要被暫存？

處理 A + B * C 時，讀到 + 還不能馬上輸出，因為後面可能有更高優先序的運算子（這裡是 *）要先處理。所以運算子要先存進堆疊等待。

演算法（運算元用 split 切成 token）：

1. 建立空 op_stack 與輸出 list。
2. 由左到右掃描每個 token：
   • 運算元 → 直接放進輸出 list。
   • 左括號 ( → push 進 op_stack。
   • 右括號 ) → 持續 pop 直到遇到對應的 (，pop 出的運算子加進輸出。
   • 運算子 → 先把堆疊上優先序大於等於它的運算子 pop 出來加進輸出，再 push 自己。
3. 掃完後，把堆疊剩下的運算子全 pop 出來加進輸出。

用 prec 字典記錄優先序：* / = 3、+ - = 2、( = 1（最低，這樣任何運算子都會疊在它上面）。

生活妙喻

後序求值：運算元排隊等運算子

求值時換運算元等待

中序轉後序時是運算子在等；後序求值時剛好相反，是運算元在等。

想像櫃台前排著一群數字，每當來了一位『運算子』，他就把最近的兩位數字叫出來算，算完的結果再回到隊伍當作新數字。

演算法（後序求值）：

1. 建立空 operand_stack。
2. 掃描每個 token：
   • 運算元 → 轉成整數 push 進堆疊。
   • 運算子 → pop 兩次取得兩個運算元，運算後把結果 push 回去。
3. 掃完後，堆疊上唯一剩下的就是答案。

flowchart TD
  A[讀到運算元] --> B[push 進堆疊]
  C[讀到運算子] --> D[pop 兩個運算元]
  D --> E[運算後 push 結果回堆疊]

實用超能力

小心非交換運算的順序

pop 順序的陷阱

後序求值有個容易出錯的地方：減法與除法不可交換，15 / 5 ≠ 5 / 15。

從堆疊 pop 兩次時，第一個 pop 出的是『第二個運算元』，第二個 pop 出的才是『第一個運算元』：

def postfix_eval(postfix_expr):
    operand_stack = Stack()
    for token in postfix_expr.split():
        if token in "0123456789":
            operand_stack.push(int(token))
        else:
            operand2 = operand_stack.pop()   # 先 pop 的是第二運算元
            operand1 = operand_stack.pop()   # 後 pop 的是第一運算元
            result = do_math(token, operand1, operand2)
            operand_stack.push(result)
    return operand_stack.pop()

例如 7 8 + 3 2 + /：先算 7+8=15、3+2=5，最後 15 / 5 = 3。順序若搞反就會得到錯誤答案。

深度探秘

先進先出 FIFO

front 移除的有序集合，先進先出。">佇列 Queue

佇列是一種有序集合：新增發生在一端叫 rear（後端），移除發生在另一端叫 front（前端）。

• 元素從 rear 進來，慢慢往 front 移動，輪到它在最前面時才被移除。
• 待最久的在 front，最新加入的在 rear。

這個排序原則叫 FIFO（first-in first-out，先進先出），也就是「先來先服務」。

flowchart LR
  R[rear 新加入] --> A[項目] --> B[項目] --> C[項目] --> F[front 先離開]

和堆疊最大的不同：堆疊同一端進出（後進先出），佇列兩端分開（先進先出）。

生活妙喻

排隊買票

規規矩矩的一條隊伍

佇列就是我們最熟悉的排隊：買電影票、超市結帳、餐廳取餐。

好的隊伍很有規矩：

• 只有一個入口（rear）、一個出口（front）。
• 不能中途插隊。
• 不能還沒輪到就先走。

所以先來的人先買到票——這就是 FIFO 的精神：公平地依到達順序服務。

實用超能力

電腦裡到處是佇列

佇列無所不在

電腦科學裡佇列的例子非常多：

• 印表機排隊：30 台電腦共用一台印表機，列印工作排成一列，先送的先印。
• 作業系統排程：用佇列管理待執行的程序，盡量公平且快速地服務多個使用者。
• 鍵盤緩衝區：打字太快時，按鍵先進入一個像佇列的緩衝區，再依正確順序顯示到螢幕。

辨認訣竅：當問題有「先來先服務、依到達順序處理」的味道，就該想到佇列。後面我們會用它做兩個有趣的模擬。

深度探秘

佇列 ADT 與 Python 實作

佇列的五個操作

Python 實作（假設 list 的位置 0 是 rear）：

class Queue:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.insert(0, item)   # 加到開頭(rear)，O(n)
    def dequeue(self):
        return self.items.pop()      # 從末端(front)移除，O(1)
    def size(self):
        return len(self.items)

這個設計下 enqueue 是 $O(n)$、dequeue 是 $O(1)$。

生活妙喻

燙手山芋的圍圈圈

Hot Potato 燙手山芋

小朋友圍成一圈傳一個東西，傳到某個時刻喊停，拿著東西的人出局，直到剩下一人。

這是經典的 Josephus 問題的現代版。怎麼用佇列模擬一個『圈圈』？

訣竅：dequeue 後立刻 enqueue。

• 拿著山芋的人在 front。
• 傳一次＝把 front 的人 dequeue 再 enqueue 到 rear（等於排到隊伍最後）。
• 數 num 次之後，front 的人被永久 dequeue（出局）。
• 重複直到佇列只剩一人。

flowchart LR
  A[front 拿山芋] --> B[dequeue]
  B --> C[立刻 enqueue 到 rear]
  C --> D[模擬出圍成一圈不斷循環]

實用超能力

完整模擬程式

hot_potato 實作

def hot_potato(name_list, num):
    sim_queue = Queue()
    for name in name_list:
        sim_queue.enqueue(name)
    while sim_queue.size() > 1:
        for i in range(num):
            sim_queue.enqueue(sim_queue.dequeue())  # 傳 num 次
        sim_queue.dequeue()                          # 第 num+1 個出局
    return sim_queue.dequeue()

幾個重點：

• 名單照順序載入，第一個名字在 front。
• num 可以大於人數，沒問題——佇列像圓圈，數到底會繞回開頭繼續算。
• 每輪傳 num 次後，當前 front 永久出局，再開始下一輪。

這展示了佇列模擬真實『繞圈計數』情境的威力。

深度探秘

用模擬回答 what-if

印表機該調快還是調慢？

情境：實驗室有 10 位學生，每人每小時平均列印 2 次，每份 1～20 頁。印表機草稿模式每分鐘 10 頁、高品質模式每分鐘 5 頁。調慢換品質會不會讓學生等太久？

我們用模擬 (simulation) 來回答。需要三個物件：

• Task：一個列印工作，建立時隨機產生 1～20 頁，並記下 timestamp（建立時間）。
• Printer：記錄是否忙碌、剩餘時間；tick() 每秒倒數一秒。
• PrintQueue：用佇列存等待中的工作，先送先印。

我們關心的是平均等待時間＝工作在佇列裡待的平均時間。

生活妙喻

用機率擲骰子模擬事件

一秒一秒地擲骰子

怎麼決定『這一秒有沒有人送列印工作』？用機率。

10 人 × 每人 2 次 = 每小時 20 個工作，換算下來平均每 180 秒一個：

$$\frac{20\ \text{tasks}}{1\ \text{hour}} \times \frac{1\ \text{hour}}{3600\ \text{seconds}} = \frac{1\ \text{task}}{180\ \text{seconds}}$$

所以每一秒就擲一個 1～180 的隨機數，如果剛好是 180，就說『這秒產生了一個列印工作』。

這就像每秒擲一顆 180 面的骰子，擲到特定一面才有事件發生。可能連續好幾個工作湧入，也可能很久都沒人印——這正是真實世界的隨機性。

實用超能力

主迴圈與結論

模擬主迴圈

每一秒 (current_second) 做：

1. 是否有新工作？有就帶著 timestamp 加入佇列。
2. 若印表機不忙且佇列非空：dequeue 下一個工作，用 current_second - timestamp 算出它的等待時間並記錄，指派給印表機。
3. 印表機 tick() 一秒。
4. 工作印完就把印表機設為閒置。

最後用記錄下來的等待時間算平均。

結論：模擬顯示 5 頁/分時平均等待從 17 到 376 秒（約 6 分鐘），且常有工作沒印完；10 頁/分時等待僅 1～28 秒，幾乎都印完。所以為了品質調慢，代價是學生等太久——不划算。

提醒：模擬好壞取決於假設是否貼近真實。要有可靠的真實資料（每小時工作數、學生數）才能建出可信的模擬。

深度探秘

兩端都能進出的混合體

雙端佇列 Deque

Deque（發音「deck」，雙端佇列 double-ended queue）也是線性結構，有 front 與 rear 兩端，但限制非常少：

• 新項目可以從 front 或 rear 任一端加入。
• 既有項目可以從任一端移除。

等於把堆疊與佇列的能力合而為一。但要注意：deque 不強制 LIFO 或 FIFO，順序規則要由你自己維持一致。

flowchart LR
  FF[front 可進可出] --> A[項目] --> B[項目] --> RR[rear 可進可出]

小提醒：別把資料結構 deque 和佇列的移除操作 dequeue 搞混了，拼法不同。

生活妙喻

兩頭都能上下車的車廂

兩頭都有門的車廂

堆疊像只有一個門的車廂（同門進出）；佇列像前後門固定方向（後門上、前門下）。

Deque 則像前後兩個門都能自由上下車：你可以從前門上、也可以從後門上；可以從前門下、也可以從後門下。

這份自由很強大，但也代表規矩要你自己訂並遵守——如果你想用它當堆疊，就只在同一端進出；想當佇列，就一端進、另一端出。結構不會幫你把關。

實用超能力

Deque ADT 的操作

Deque 的操作

因為兩端都能操作，移動項目時務必清楚誰是 front、誰是 rear，否則很容易搞混。

下一節我們會看到 deque 的一個漂亮應用：用『同時從兩端取出比較』來檢查回文。

深度探秘

用 list 實作 Deque

Deque 的 Python 實作

假設 list 的 rear 在位置 0、front 在末端：

class Deque:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def add_front(self, item):
        self.items.append(item)     # 末端=front，O(1)
    def add_rear(self, item):
        self.items.insert(0, item)  # 開頭=rear，O(n)
    def remove_front(self):
        return self.items.pop()     # O(1)
    def remove_rear(self):
        return self.items.pop(0)    # O(n)
    def size(self):
        return len(self.items)

效能觀察：因為 front 對應 list 末端，front 端操作是 $O(1)$、rear 端操作是 $O(n)$。重點還是要清楚哪一端被指定為 front、哪一端為 rear。

生活妙喻

回文：從兩頭往中間夾

回文 Palindrome

回文是正著讀、反著讀都一樣的字串，如 radar、toot、madam。

用 deque 檢查回文的妙處在於：可以同時從兩端各取一個字元來比較。

做法：把字串的每個字元依序 add_rear 進 deque（此時像普通佇列）。然後：

• remove_front() 取出第一個字元、remove_rear() 取出最後一個字元。
• 兩者相等就繼續往內夾，不相等就不是回文。

flowchart LR
  A[remove_front 取頭] --> C[比較]
  B[remove_rear 取尾] --> C
  C --> D[相等就繼續往中間夾]

就像兩隻手分別從字串頭尾往中間靠攏，一對一對核對。

實用超能力

pal_checker 與終止條件

pal_checker 實作

def pal_checker(a_string):
    char_deque = Deque()
    for ch in a_string:
        char_deque.add_rear(ch)
    still_equal = True
    while char_deque.size() > 1 and still_equal:
        first = char_deque.remove_front()
        last = char_deque.remove_rear()
        if first != last:
            still_equal = False
    return still_equal

為什麼條件是 size() > 1？ 因為每次比較會移除兩個字元：

• 字串長度為偶數：最後會剛好取完（size 變 0）。
• 字串長度為奇數：最後會剩中間一個字元（size 變 1），它不需和任何人比，本來就對稱。

所以只要每一對都相等，不論奇偶，都是回文。

深度探秘

什麼是串列？為什麼要自己做？

自己打造 list

Python 內建的 list 很好用，但不是每個語言都內建。這時就得自己實作。

串列 (list) 是一個項目集合，每個項目相對於其他項目有個相對位置：有第一個、第二個、第三個……有開頭也有結尾。本節討論無序串列 (unordered list)（為簡化，假設不含重複項目）。

無序串列 ADT 的常見操作：

例如分數 54, 26, 93, 17, 77, 31 就是一個簡單的無序串列。

生活妙喻

尋寶遊戲的線索紙條

一張接一張的尋寶線索

鏈結串列不要求項目存放在連續的記憶體裡。項目可以散落各處，只要每個項目都記著『下一個在哪裡』就行。

這就像一場尋寶遊戲：每張線索紙條除了寫著寶物（資料），還寫著『下一張紙條藏在哪』（參照 reference）。

• 你只要知道第一張紙條在哪（稱為 head），就能順著一張找一張，走完全程。
• 最後一張紙條會說『沒有下一張了』——用特殊值 None 表示盡頭。

flowchart LR
  H[head] --> N1[節點 資料93 next]
  N1 --> N2[節點 資料17 next]
  N2 --> N3[節點 資料77 next]
  N3 --> X[None 盡頭]

實用超能力

Node 節點類別

基本磚塊：Node

鏈結串列的基本單位是節點 (node)，每個節點至少存兩樣東西：

1. data：項目本身的值。
2. next：指向下一個節點的參照（一開始是 None）。

class Node:
    def __init__(self, init_data):
        self.data = init_data
        self.next = None
    def get_data(self):
        return self.data
    def get_next(self):
        return self.next
    def set_data(self, new_data):
        self.data = new_data
    def set_next(self, new_next):
        self.next = new_next

建立節點：temp = Node(93)，temp.get_data() 會得到 93。

None 的角色很重要：節點一建立時 next 就設為 None，代表『目前沒有下一個』。明確把初始 next 設成 None 是好習慣，這讓我們之後能用『是不是 None』來判斷是否走到了串列盡頭。

深度探秘

串列只記住 head

UnorderedList 類別

鏈結串列由一串節點組成，彼此用 next 連著。只要知道第一個節點在哪，後面都能順著找到。因此 UnorderedList 只需維護一個指向第一個節點的參照——head。

class UnorderedList:
    def __init__(self):
        self.head = None

重要：串列物件本身不包含任何節點，它只持有指向第一個節點的單一參照。

空串列時 head 就是 None。所以判斷是否為空很簡單：

def is_empty(self):
    return self.head == None

建構子（head=None）與 is_empty 的判斷彼此一致，這正是用 None 標示盡頭的好處。

生活妙喻

從最容易的地方加新成員

新人插在最前面

要把新項目加進串列，該放哪裡？因為是無序串列，位置無所謂，那就放在最容易的地方。

鏈結串列只有一個入口——head。所以最簡單的就是把新節點放在最前面，當作新的第一個節點。

這也解釋了一個有趣現象：先加入的項目反而會被推到串列尾端。例如依序 add(31)、add(77)…add(54)，最先加的 31 會在最後，最後加的 54 會在最前。

flowchart LR
  H[head] --> NEW[新節點 54] --> OLD[原本的第一個節點 26] --> R[其餘節點]

實用超能力

add 的兩步驟，順序不能反

add 的兩個步驟

def add(self, item):
    temp = Node(item)        # 1. 建立新節點
    temp.set_next(self.head) # 2. 新節點的 next 指向原本的第一個節點
    self.head = temp         # 3. head 改指向新節點

關鍵在於第 2、3 步的順序絕對不能反：

• 正確：先讓新節點接上舊的第一個節點，再把 head 移過去。
• 錯誤：若先改 head 指向新節點，原本那串節點就沒有任何參照指著它們，整串資料就此遺失、再也找不回來！

教訓：在鏈結串列裡改動連結時，務必確保『接上新的之前，不要先斷開唯一的舊連結』。

深度探秘

走訪 traversal 與 size、search

current 從 head 沿 next 逐一拜訪節點的過程。">走訪：沿著 next 一個個拜訪

走訪 (traversal) 是系統性地拜訪每個節點：用一個外部參照 current 從 head 出發，每拜訪一個就沿著 next 移到下一個，直到遇上 None。

size：邊走邊數。

def size(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.get_next()
    return count

search：邊走邊找，找到就提早停。

def search(self, item):
    current = self.head
    found = False
    while current != None and not found:
        if current.get_data() == item:
            found = True
        else:
            current = current.get_next()
    return found

size 一定走到底（$O(n)$）；search 找到就停，最壞也是 $O(n)$。

生活妙喻

remove 為何要兩個人同行

一前一後的『毛毛蟲爬行』

要移除一個節點，得讓它的前一個節點改指向它的後一個節點，把它『跳過』。

但鏈結串列無法往回走！當 current 停在要刪的節點上，已經來不及回頭改前一個的連結了。

解法：用兩個參照同行——

• current：照常標記目前位置。
• previous：永遠跟在 current 後面一個節點。

移動時 previous 要先追上 current 的位置，current 才往前——這個一前一後的動作叫 inch-worming（毛毛蟲爬行）。當 current 停在目標，previous 剛好停在它前面，就能動手改連結了。

flowchart LR
  P[previous] --> C[current 目標節點] --> N[下一個節點]
  P -. 改指向 .-> N

實用超能力

remove 的程式與頭節點特例

remove 實作

def remove(self, item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.get_data() == item:
            found = True
        else:
            previous = current          # previous 先追上
            current = current.get_next()  # current 再前進
    if previous == None:               # 特例：要刪的是第一個節點
        self.head = current.get_next()
    else:
        previous.set_next(current.get_next())

頭節點特例：若要刪的就是第一個節點，迴圈一次都沒移動，previous 還是 None。這時不是改 previous，而是把 head 直接指向 current 的下一個，等於把第一個節點移除。

注意移動 previous 與 current 的順序也很重要：一定要 previous 先到 current 的位置，current 才能前進。