ECCH5｜數據結構（Data Structures）

先把問題拆成數據與操作

數據結構不只是盛載資料的容器，而是「如何排列數據」與「允許怎樣操作」的整體設計。相同的學生紀錄可以放在陣列、鏈表或以學號作鍵的雜湊表；讀取第 k 筆、按學號搜尋及在中間加入紀錄時，各種結構的表現會不同。因此，選擇前要先列出真正需要的操作。

評估結構時通常比較時間成本與空間成本。直接按索引讀取可能很快，但保持連續次序會令中間插入需要移位；以指示標連接節點可減少搬移，卻要額外空間保存連結，亦可能需要逐節點搜尋。所謂「合適」是指它配合目前問題的主要操作及限制，而不是在所有方面都最快。

學習每一種結構時，可依次掌握核心規則、可用操作、操作前後的狀態變化及常見錯誤，再把現實情境翻譯成這些規則。以下分類表及成本比較表可作初步地圖；後續課題會以圖像、偽代碼、Python 活動及小測進一步驗證理解。

Check Point：數據結構導言

題目涵蓋定義、操作需求、現實例子、結構比較及常見選擇錯誤。

先判斷次數是否已知

當題目已清楚給出開始值、終止值或重複次數時，for 通常最容易閱讀，例如由 1 至 9 逐項處理。若執行次數要到運行期間才知道，例如「當仍有下一筆紀錄便繼續」，while 較合適。兩者都需要清楚的終止機制，否則可能多做一次、少做一次或永不停止。

前測與後測決定循環主體最少執行多少次。while 在進入主體前檢查條件，初始條件不成立時會執行 0 次；do while 及 repeat until 先做一次再檢查，所以至少執行 1 次。這個差異特別適合用來判斷「必須先取得一次輸入，之後才知道是否重複」的情境。

還要分辨條件的意思。while 與 do while 在條件為真時繼續；repeat until 則在條件為真時停止。追蹤時可依序寫下控制變量的初始值、每次條件結果、主體輸出及更新後的值，便較容易發現 off-by-one、條件方向錯誤與忘記更新等問題。

設 i 由 1至 9
    ...

當 x > 5
    ...

執行
    ...
當 x > 5

重複
    ...
直至 x > 5

Check Point：DSE 循環偽代碼四式

題目涵蓋結構辨認、執行次數、條件意義、前測／後測及常見錯誤。

重點

• 索引存取：用 index 直接讀取 arr[i]，概念上視作 O(1)。
• 插入／刪除會移位：若不是尾端操作，往往要搬移元素，時間多為 O(n)。
• 二維陣列定位：先列後欄，用 arr[row][col]；row/col 轉錯會取錯格。
• Row-major 理解：2D 可以攤平成 1D；線性索引 ≈ row * 欄數 + col（逐列掃描）。
• 走訪與搜尋：用循環逐格處理（例如找最大值、計算總和、掃描 2D 表格）。

按我顯示更多內容

概念講解：陣列的優勢與限制

陣列最核心的概念是「位置（index）」。當你寫 arr[i]，其實你是要求系統去第 i 個位置取數據。 因為位置是已知，所以不需要逐個比較來尋找，讀取通常快。

但陣列要維持「次序」：例如你想將一個新元素插入到中間，為了騰出空位，後面元素就要向後搬。 所以即使讀取快，插入／刪除位置錯了都可能很慢。

二維陣列可以視為「表格」。定位一格需要兩個索引：先列（row）後欄（col）。 如果你用 row-major 角度看，掃描表格其實是逐列掃過去，這個理解對之後 heap / graph 的陣列表示很有幫助。

表格整理：常見操作與直覺成本

圖像化 + 可操作示範

例子示範：偽代碼（4 種循環） vs Python（for + while）

例子：在陣列中找第一個等於 target 的索引；找不到回傳 -1。

arr = [4, 9, 2, 9]

target = 9
ans = -1

for i in range(len(arr)):
    if arr[i] == target:
        ans = i
        break

print(ans)

arr = [4, 9, 2, 9]

target = 9
ans = -1

i = 0
while i < len(arr):
    if arr[i] == target:
        ans = i
        break
    i += 1

print(ans)

ans ← -1
設 i 由 0至 n-1
    若 arr[i] = target
        ans ← i
        離開循環

ans ← -1
i ← 0
當 i < n
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1

ans ← -1
i ← 0
執行
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1
當 i < n

ans ← -1
i ← 0
重覆
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1
直至 i ≥ n

小遊戲：線性檢索（Linear Search）拖放挑戰

系統會隨機產生一個陣列與目標值 target。請由 index = 0 開始，依次把「指示標」拖到下一格進行檢查； 當找到 target 後，系統會產生「回傳索引」代幣，請把它拖到回傳框。
重點：線性檢索必須按次序逐格檢查，不能跳格。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Array / 2D Array）

重點

• LIFO：後進先出，只能由頂部進出。
• 三大操作：push（加入頂部）、pop（移除頂部）、peek（查看頂部）。
• 常見用途：括號配對、回溯（backtracking）、撤銷（undo）、深度優先搜索（DFS）。
• 空堆疊與安全檢查：pop 前先判斷是否為空，避免錯誤與邏輯漏洞。
• 封裝成 ADT：用函數／類別把 push/pop/peek/is_empty 包起來，令程式更清晰。

按我顯示更多內容

概念講解：LIFO 的典型應用

Stack 的特別之處不是它「功能多寡」，而是它限制了你如何存取資料：只准由頂部進出。 這個限制反而令很多算法更清晰，例如「處理到一半想回到上一層」就直接 pop。

以括號配對為例：每遇到一個左括號，就等於開了一個「未完成的工作」；當遇到右括號，就要把最近未完成那個工作關閉。 由於要處理「最近」那個，LIFO 就非常適合。

實作上，你可以用 Python list 尾端做 stack：append 當 push，pop() 當 pop。 但記住：空 stack pop 會出錯，所以要先檢查長度。

表格整理：Stack 操作

可操作示範：Stack push/pop

例子示範：偽代碼（4 種循環） vs Python（for + while）

例子：括號配對（只處理 '(' 與 ')'）。

s = "(()())()"
stack = []
ok = True

for ch in s:
    if ch == "(":
        stack.append(ch)
    else:
        if len(stack) == 0:
            ok = False
            break
        stack.pop()

if ok and len(stack) != 0:
    ok = False

print(ok)

s = "(()())()"
stack = []
ok = True

i = 0
while i < len(s):
    ch = s[i]
    if ch == "(":
        stack.append(ch)
    else:
        if len(stack) == 0:
            ok = False
            break
        stack.pop()
    i += 1

if ok and len(stack) != 0:
    ok = False

print(ok)

ok ← True
設 i 由 0至 n-1
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
當 i < n
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
執行
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
當 i < n
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
重覆
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
直至 i ≥ n
若 ok = True 且 stack 非空
    ok ← False

小遊戲：堆疊（Stack）指令拖放練習

系統會提供一個初始堆疊、一些「新數據」以及一串指令（push/pop）。 請按指令次序完成操作：
・push：把指定的新數據拖到堆疊區（會放在頂部）。
・pop：把頂部元素拖到「回傳區」。
做錯時會提示「正確下一步」。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Stack）

重點

• FIFO：先進先出；入隊加尾、出隊移頭。
• 避免慢操作：如果用 list 直接 pop(0) 會慢；可用 head 指示標/循環隊列思路。
• 常見用途：排隊系統、BFS、任務排程。
• 常見實作：在 Python 可用 collections.deque 做 O(1) 的入隊／出隊（概念更貼近真・隊列）。
• 封裝成 ADT：把 enqueue / dequeue / front / is_empty / size 寫成一套介面，做題目更穩。

按我顯示更多內容

概念講解：FIFO 與實作技巧

Queue 的概念其實非常貼近生活：排隊就是 FIFO。 但寫程式時，重點是你用甚麼方式實作 dequeue。 如果你用 Python list 的 pop(0)，每次都要把後面元素向前搬，會慢。

一個常見技巧是用 head 指示標：入隊仍然 append，出隊不搬陣列，只是 head += 1。 最後真正隊列內容就是 q[head:]。 這個思路亦是循環隊列（circular queue）的基礎。

在偽代碼中，亦常見用一個（可以很長的）陣列配合「隊列開始 front」及「隊列結束 rear」（或 head / tail），再加上一個「項目數量 count」。入隊時把新值寫到 rear；出隊時不需要把元素真的從陣列移除，只要把 front 往後移一格（或把 count 減一）即可完成更新。陣列內舊位置的值可以保留，但會被視為『不再屬於隊列』。

當你理解到 queue 的 FIFO 特性，你就會自然明白 BFS 為甚麼會「逐層」走訪：因為先發現的節點先出隊、先展開。

可操作示範（一）：移位式隊列（像排隊般全隊向前）

這個版本最貼近「現實排隊」的直覺：enqueue 就在隊尾加入新元素；dequeue 就把隊首元素移走， 然後整隊人向前移一格（也就是把陣列內的元素逐個向前搬移）。

你應該觀察：每次 dequeue 後，原本在第 1、2、3… 位的人都會「搬位」，因此在陣列實作中，dequeue 往往是 O(n)。

# 假設隊列儲存在 arr[0..size-1]
# enqueue(x)：加到尾端
arr[size] ← x
size ← size + 1

# dequeue()：取 arr[0]，其餘向前移一格
若 size = 0
    回傳 NULL
y ← arr[0]
設 i 由 0至 size-2
    arr[i] ← arr[i+1]
size ← size - 1
回傳 y

q = [10, 20, 30]

# enqueue
x = 99
q.append(x)      # 加到隊尾

# dequeue（會把後面元素向前搬）
front = q.pop(0) # 取走隊首
print("dequeue ->", front)
print("queue =", q)

可操作示範（二）：指示標式隊列（只移動 head / tail，不搬移元素）

提示：在「指示標式隊列」中，dequeue 後不必把元素從陣列刪走；只要 head 往後移一格即可。 你會看到舊值仍留在格子內，但已不再屬於隊列。

例子示範：偽代碼（4 種循環） vs Python（for + while）

例子：處理隊列中所有任務（直到 queue 清空），並累計總時間。

tasks = [2, 5, 1, 3]

total = 0
for t in tasks:
    total += t

print(total)

tasks = [2, 5, 1, 3]
q = tasks[:]
head = 0

total = 0
while head < len(q):
    total += q[head]
    head += 1

print(total)

total ← 0
設 i 由 0至 n-1
    total ← total + task[i]

total ← 0
head ← 0
當 head < n
    total ← total + task[head]
    head ← head + 1

total ← 0
head ← 0
執行
    total ← total + task[head]
    head ← head + 1
當 head < n

total ← 0
head ← 0
重覆
    total ← total + task[head]
    head ← head + 1
直至 head ≥ n

小遊戲：隊列（Queue）指令拖放練習（FIFO）

你會得到一個初始隊列與一串指令（enqueue/dequeue）。 請按次序完成：enqueue 時把指定新數據拖到隊尾；dequeue 時把隊首元素拖到回傳區。
重點：隊列是 FIFO（先進先出），只能從隊首取出。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（隊列）

重點

• 固定容量：用一個大小為 n 的陣列作為儲存區（buffer），空位可重用。
• 兩個指示標：head 指向下一個出隊位置；tail 指向下一個入隊位置。
• 循環（wrap-around）：指示標到達尾端後回到 0；用 (i+1) mod n 表示。
• 滿／空判斷：常見方法是用 size 記錄元素數；或用「下一格是否等於 head」判斷滿。
• 覆蓋模式：當隊列已滿仍入隊時，會覆蓋最舊元素，並把 head 亦向前推一格（常見於資料串流／固定緩衝區）。
• 避免假溢出：普通隊列若只向前移 head，尾端可能有空位但無法再入隊；循環隊列可重用空位。

按我顯示更多內容

概念講解：為何需要循環隊列

在「隊列」的題目中，我們希望維持 FIFO（先進先出）。如果用固定大小的陣列實作，最直觀的方法是用兩個指示標： head 指向隊首、tail 指向下一個可放入的位置。每次出隊後，head 向前移動。

問題是：當 tail 走到陣列尾端時，即使前面已經出隊騰出了空位，尾端也「看似」沒有位置可以再入隊，這就是假溢出（false overflow）。 循環隊列的做法是把陣列當作一個「環」，讓指示標到尾端後回到 0，從而重用空位。

實作時最關鍵是兩點：第一是用 (i+1) mod n 處理循環；第二是清楚定義「空」與「滿」。 最穩的方法是用 size 記錄目前元素數，避免 head==tail 造成判斷混亂。

本頁示範採用「覆蓋模式」：當 size==n（已滿）仍然 enqueue，新元素會寫入 tail（此時 tail==head），然後 head 會同步向前推一格，代表最舊元素被覆蓋而離開隊列。這種設計常用於固定容量的緩衝區，例如保留最近 n 筆資料。

表格整理：操作、指示標與條件

可操作示範：循環隊列（固定容量）

提示：本示範採用「覆蓋模式」。當 size==n（已滿）仍 enqueue，新值會覆蓋最舊元素（head 會同步向前移）。

例子示範：用循環隊列處理一串操作

示範重點：mod 處理循環；先判斷滿／空；enqueue 先寫入再移 tail，dequeue 先讀取再移 head。

ops = ["enq 5", "enq 8", "enq 3", "deq", "enq 9", "deq", "enq 1", "enq 7", "enq 6"]
n = 5
buf = [None] * n
head = 0
tail = 0
size = 0

for op in ops:
    if op.startswith("enq"):
        x = int(op.split()[1])
        if size == n:
            # 覆蓋最舊元素：在 tail（此時 tail==head）寫入，並同步推進 head
            buf[tail] = x
            tail = (tail + 1) % n
            head = (head + 1) % n
            print("滿：覆蓋最舊 -> enqueue", x)
        else:
            buf[tail] = x
            tail = (tail + 1) % n
            size += 1
    else:  # deq
        if size == 0:
            print("空：不能 dequeue")
        else:
            x = buf[head]
            buf[head] = None
            head = (head + 1) % n
            size -= 1
            print("dequeue ->", x)

print("buf =", buf)
print("head =", head, "tail =", tail, "size =", size)

# 假設 buf / head / tail / size 已由上面程式得到
out = []
while size > 0:
    x = buf[head]
    buf[head] = None
    head = (head + 1) % n
    size -= 1
    out.append(x)

print("全部出隊次序 =", out)

設每個 op 依序由 ops 取出
    若 op 為 enqueue(x)
        若 size == n
            輸出「滿」
        否則
            buffer[tail] = x
            tail = (tail + 1) mod n
            size = size + 1
    否則（op 為 dequeue）
        若 size == 0
            輸出「空」
        否則
            x = buffer[head]
            buffer[head] = 空
            head = (head + 1) mod n
            size = size - 1
            輸出 x

當 size > 0
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x

執行
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x
當 size > 0

重覆
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x
直至 size == 0

小遊戲：循環隊列（Circular Queue）拖放挑戰（覆蓋模式）

此小遊戲採用「覆蓋模式」：當循環隊列已滿仍然 enqueue，新元素會覆蓋最舊元素（同時把 head 推進一格）。 請按指令次序完成操作：
・enqueue：把指定新數據拖到tail 指向的格。
・dequeue：把head 指向的格拖到回傳區。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（循環隊列）

重點

• start 找首個節點：在這一節，start 用來指出首個節點的索引；D[i] 儲存內容，NP[i] 儲存下一個節點的索引。
• 真正次序要跟指示標讀：節點可以分散在不同索引位置，但整條鏈的先後次序要由 start 出發，沿 NP[current] 逐個讀出。
• 插入／刪除主要是重新接駁：若改的是首個節點，便更新 start；否則通常只需改動附近的少量 NP。
• 只有走得到的節點才算入鏈表：即使某些索引位置有資料，只要不能由 start 到達，它們便不屬於目前這條鏈表。
• 鏈表與陣列各有長短：鏈表方便重新接駁；陣列則較擅長直接存取／隨機存取。

按我顯示更多內容

概念講解：把節點想像成分散放置的導賞卡

想像學校要為開放日準備一條「校園導賞路線」。每一張導賞卡都記錄一個站點名稱，以及「下一站放在哪個索引」。 這些卡片未必按路線先後整齊排在 1、2、3、4；它們可以分散放在不同位置，但只要每張卡都寫清楚下一站在哪裏，整條路線仍然能順利走完。

例如 start = 5，便表示第一站放在索引 5；若 NP[5] = 3，就代表下一站在索引 3。 於是實際次序是 5 → 3 → 1 → 2，而不是單看索引大小。這就是線性鏈表最重要的觀念：索引只是一個存放位置，真正的先後次序由連接關係決定。

也正因如此，線性鏈表較適合描述「順著一條路逐站前進」的情況。要找第 3 個節點，你必須由第一個節點開始逐個跟著指示標前進； 但如果你已經知道前一個節點在哪裏，插入或刪除時通常只需改動少量連接，不必像陣列那樣把後面所有資料搬位。

圖像化 + 可操作示範：由 start 出發，沿路線前進

請按正確次序點擊索引：先找出 start 指向的站點，再沿 NP[current] 前進，直到 NULL。

可操作示範：修改校園導賞路線（以 D 及 NP 顯示）

你可以把新站點插入為第 n 個節點，或刪除第 n 個節點。 請留意：n 代表路線中的次序；i 只代表新節點存放在表內哪一個空位索引，兩者不一定相同。 每次操作後，下方都會列出哪些索引被更新，並顯示目前路線，方便你觀察「重新接駁」究竟發生了甚麼。

例子示範：以校園導賞路線理解偽代碼與 Python

以下例子全部以 start、D、NP 為主，讓你集中理解節點如何連接、更新與走訪。

D = ["", "圖書館", "電腦室", "禮堂", "", "校門", ""]
NP = [-1, 2, -1, 1, -1, 3, -1]
start = 5

current = start
out = []
while current != -1:
    out.append(D[current])
    current = NP[current]

print(" -> ".join(out))

def delete_n(D, NP, start, n):
    if n == 1:
        return NP[start]

    prev = start
    current = NP[start]
    for _ in range(2, n):
        prev = current
        current = NP[current]

    NP[prev] = NP[current]
    return start

子程式 printList()
current ← start
當 current ≠ NULL
    輸出 D[current]
    current ← NP[current]

子程式 delete(n)
如果 n = 1 則
    start ← NP[start]
否則
    prev ← start
    current ← NP[start]
    設 k 由 2 至 n-1
        prev ← current
        current ← NP[current]
    NP[prev] ← NP[current]

子程式 insert(n, name, i)
D[i] ← name
如果 n = 1 則
    NP[i] ← start
    start ← i
否則
    prev ← start
    current ← NP[start]
    設 k 由 2 至 n-1
        prev ← current
        current ← NP[current]
    NP[i] ← current
    NP[prev] ← i

子程式 length()
count ← 0
current ← start
當 current ≠ NULL
    count ← count + 1
    current ← NP[current]
傳回 count

# ==========================================

# 最大可用節點數量
MAX_SIZE = 10

# data[i] 儲存第 i 個節點的資料
data = [None] * MAX_SIZE

# next_ptr[i] 儲存第 i 個節點下一個節點的索引
next_ptr = [-1] * MAX_SIZE

# head 儲存 linked list 第一個節點的位置
# 若 head = -1，代表 linked list 為空
head = -1

# free_ptr 只是記錄下一個未曾使用的空位
# 注意：這裡不會回收已刪除節點，所以 free_ptr 只會一路增加
free_ptr = 0


def initialize():
    """
    初始化 linked list
    一開始 linked list 為空，所以 head = -1
    下一個可用新位置由 0 開始，所以 free_ptr = 0
    """
    global head, free_ptr

    head = -1
    free_ptr = 0

    # 初始時將所有資料清空
    for i in range(MAX_SIZE):
        data[i] = None
        next_ptr[i] = -1


def get_node():
    """
    取得一個新節點位置

    由於本版本不做空位回收，
    所以每次只使用下一個未用過的位置。
    如果 free_ptr >= MAX_SIZE，代表已沒有新空位。
    """
    global free_ptr

    if free_ptr >= MAX_SIZE:
        return -1

    p = free_ptr
    free_ptr += 1
    return p


def is_empty():
    """
    檢查 linked list 是否為空
    """
    return head == -1


def insert_end(value):
    """
    在 linked list 尾部加入一個新節點

    步驟：
    1. 取一個新空位
    2. 將 value 存入該節點
    3. 若 linked list 原本為空，head 直接指向它
    4. 否則由 head 開始走到尾，再接上新節點
    """
    global head

    new_ptr = get_node()

    if new_ptr == -1:
        print("No more new space.")
        return

    data[new_ptr] = value
    next_ptr[new_ptr] = -1

    # 若原本為空表
    if head == -1:
        head = new_ptr
    else:
        current = head

        # 找最後一個節點
        while next_ptr[current] != -1:
            current = next_ptr[current]

        # 尾節點接去新節點
        next_ptr[current] = new_ptr


def display_list():
    """
    顯示 linked list 內容

    注意：
    只會由 head 開始沿 next_ptr 顯示真正屬於 linked list 的節點。
    即使陣列內有舊資料、已刪除節點，都不會顯示出來。
    """
    current = head

    if current == -1:
        print("Linked list is empty.")
        return

    print("Linked list:")
    while current != -1:
        print(f"[{current}] Data = {data[current]}, Next = {next_ptr[current]}")
        current = next_ptr[current]


def display_array():
    """
    顯示整個 array 狀態
    用來觀察：即使節點從 linked list 中刪除，
    它原本在 array 裡的資料仍可能保留。
    """
    print("Whole array:")
    for i in range(MAX_SIZE):
        print(f"[{i}] Data = {data[i]}, Next = {next_ptr[i]}")


def delete_at_position(position):
    """
    刪除 linked list 中第 position 個節點
    position 由 1 開始計

    本版本不做空位回收，
    所以 delete 的意思只是：
    將該節點從 linked list 中移除，
    即修改前一個節點的 next pointer，跳過它。

    被刪除節點原本在 array 中的 data 和 next_ptr 可以保留不變，
    因為它已不再由 head 可到達。
    """

    global head

    # 空表不能刪除
    if head == -1:
        print("Linked list is empty.")
        return

    # 位置必須大於 0
    if position <= 0:
        print("Invalid position.")
        return

    # -------------------------
    # 刪除第一個節點
    # -------------------------
    if position == 1:
        delete_ptr = head
        head = next_ptr[head]
        print("Deleted from list:", data[delete_ptr])
        return

    # -------------------------
    # 刪除第二個或之後的節點
    # -------------------------
    # prev 用來找被刪除節點的前一個節點
    prev = head
    count = 1

    # 由 head 開始沿 linked list 走到第 position-1 個節點
    while prev != -1 and count < position - 1:
        prev = next_ptr[prev]
        count += 1

    # 若 prev 不存在，或 prev 後面已沒有節點
    # 代表 position 超出範圍
    if prev == -1 or next_ptr[prev] == -1:
        print("Position out of range.")
        return

    # delete_ptr 是要刪除的節點
    delete_ptr = next_ptr[prev]

    # 將 prev 直接連到 delete_ptr 的下一個節點
    # 即跳過 delete_ptr
    next_ptr[prev] = next_ptr[delete_ptr]

    print("Deleted from list:", data[delete_ptr])


# ==========================================
# Example usage
# ==========================================

initialize()

insert_end("A")
insert_end("B")
insert_end("C")
insert_end("D")

print("Before delete:")
display_list()

print("\nDelete position 3:")
delete_at_position(3)
display_list()

print("\nWhole array after delete:")
display_array()

小遊戲：線性鏈表（start / D / NP）操作練習

系統會給你一條以陣列顯示的線性鏈表，以及一條操作指令。標準版會要求你先填出需要更新的 start 或 NP； 困難版則要直接把 start 和整張 D / NP 表改成操作後的結果，系統不會預先指出要改哪一格。做對後，再寫出更新後的節點次序，看看自己是否真的掌握「重新接駁」這個核心觀念。

請先閱讀上面的例子示範，再完成以下練習。以下填充題全部採用 start、D、NP 的表示方式，幫你練熟走訪、插入與刪除。

Python 小練習（填充題）

Check Point：小測（線性鏈表）

十一、小結與下一步

• 掌握 DSE 核心：陣列 Array／堆疊 Stack／隊列 Queue／循環隊列 Circular Queue／線性鏈表 Linked List（重點是「操作成本」與「適用情景」）。
• 增潤部分先建立直覺：Traversal（DFS/BFS）、Hash（collision）、Heap（priority queue）、Graph（visited）。
• 做練習時，先寫到「可運行」，再追求「寫得漂亮／快」。

重點

• 先由需求選結構：辨認最常做的存取、插入、刪除、搜尋、遍歷或優先處理，再比較操作成本。
• 分清規則與實作：堆疊、隊列等抽象數據類型規定取出次序；陣列、鏈表或 deque 則是底層表示法。
• 追蹤狀態不變量：索引範圍、head／tail／size、start／NP、heap property 及 visited 都必須在每次操作後仍然正確。
• 把結構互相連結：隊列支援寬度優先搜索，堆疊支援深度優先搜索，鏈表可處理雜湊碰撞，陣列可表示堆及鄰接矩陣。
• 以測試驗證邊界：空、單一元素、已滿、找不到、碰撞、循環及不連通情況，都是最容易揭示錯誤的測試。

按我顯示更多內容

使用腦圖整理本章概念：先由「問題需求與操作成本」開始，再比較按索引定位、端點限制、循環緩衝、指示標連接、階層、鍵值索引及關係網絡等不同儲存模型。

右上角的「樹狀圖導覽」會以文字顯示完整層級；點擊任何項目，畫布會以動畫移動及縮放到對應節點。開啟「聚焦模式」後，直接點擊畫布節點亦會自動移至合適大小，方便閱讀程式碼、公式、比較及常見錯誤。

腦圖亦整合 20 條偽代碼轉 Python 綜合挑戰。學生可在瀏覽器本機新增、刪除、編輯或重新接駁節點，並以 .ictmap 匯入及匯出；這些修改不會寫回網站原本的 JSON 檔案。