建立 2026-11-12 更新 2026-11-12 HL only

線性 ADT：鏈結串列、堆疊與佇列

線性抽象資料型別是元素依序排列的資料結構，包括鏈結串列（linked list）、堆疊（stack）與佇列（queue）。本頁說明鏈結串列如何用節點與指標串接資料、如何插入與刪除節點，以及如何用陣列或鏈結串列實作堆疊與環狀佇列。本頁屬於 HL 專屬的 B4 單元。

HL 專屬內容

本頁屬於 B4.1，只有 HL 需要學。

鏈結串列如何運作？

鏈結串列由一連串 節點（node） 組成，每個節點存放資料與指向下一個節點的 指標（pointer／reference）。串列由 head 指向第一個節點，最後一個節點的指標為 None／null。

flowchart LR
    H((head)) --> A["10 | next"] --> B["25 | next"] --> C["37 | next"] --> N((None))

單向鏈結串列（singly linked list）：只能往後走。
雙向鏈結串列（doubly linked list）：每個節點同時有 prev 與 next，可以雙向走訪，但多佔記憶體。
環狀鏈結串列（circular linked list）：最後一個節點指回第一個，適合輪流處理（例如 Round Robin 排程）。

陣列和鏈結串列怎麼比較？

操作	陣列	鏈結串列
依索引存取第 i 個	O(1)	O(n)，必須從 head 一個個走
在開頭插入／刪除	O(n)，要搬移所有元素	O(1)，改指標即可
在已知節點後插入／刪除	O(n)	O(1)
大小	靜態陣列固定	動態，可隨時增減
記憶體	連續、無額外負擔	不連續，每個節點多存指標

如何實作鏈結串列？

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


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

    def insert_front(self, data):          # O(1)
        node = Node(data)
        node.next = self.head
        self.head = node

    def append(self, data):                # O(n)：走到尾端
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = node

    def search(self, target):              # O(n)
        cur = self.head
        while cur is not None:
            if cur.data == target:
                return True
            cur = cur.next
        return False

    def delete(self, target):
        if self.head is None:
            return False
        if self.head.data == target:       # 刪除第一個節點
            self.head = self.head.next
            return True
        prev, cur = self.head, self.head.next
        while cur is not None:
            if cur.data == target:
                prev.next = cur.next       # 跳過 cur
                return True
            prev, cur = cur, cur.next
        return False

    def display(self):
        items, cur = [], self.head
        while cur:
            items.append(str(cur.data))
            cur = cur.next
        print(" -> ".join(items) + " -> None")

刪除節點的關鍵是 讓前一個節點的 next 跳過要刪除的節點。Java 中沒有指標指向的節點會被垃圾回收（garbage collection）。

如何實作堆疊？

堆疊是 LIFO：只在頂端（top）操作。

操作	說明
`push(x)`	放到頂端
`pop()`	移除並回傳頂端元素；空堆疊時為下溢（underflow）
`peek()`	查看頂端但不移除
`is_empty()`／`is_full()`	用固定陣列實作時，滿了再 push 為溢位（overflow）

class Stack:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == len(self.items) - 1

    def push(self, x):
        if self.is_full():
            raise OverflowError("stack overflow")
        self.top += 1
        self.items[self.top] = x

    def pop(self):
        if self.is_empty():
            raise IndexError("stack underflow")
        x = self.items[self.top]
        self.top -= 1
        return x

    def peek(self):
        return None if self.is_empty() else self.items[self.top]

如何實作環狀佇列？

用一般陣列實作佇列時，前端取出後空間無法再利用。環狀佇列（circular queue） 讓 front 與 rear 指標用 % capacity 繞回陣列開頭，重複利用空間。

class CircularQueue:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.size = 0

    def enqueue(self, x):
        if self.size == self.capacity:
            raise OverflowError("queue is full")
        rear = (self.front + self.size) % self.capacity
        self.items[rear] = x
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("queue is empty")
        x = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return x

練習題

練習 1：鏈結串列操作

從空串列開始依序執行 insert_front(5)、append(9)、insert_front(2)、delete(5)，display() 會輸出什麼？

參考答案

5 → 5 -> 9 → 2 -> 5 -> 9 → 刪除 5 後為 2 -> 9 -> None。

練習 2：計算長度

為 LinkedList 新增方法 length()，回傳節點數。

參考答案

def length(self):
    count, cur = 0, self.head
    while cur is not None:
        count += 1
        cur = cur.next
    return count

練習 3：括號配對

用堆疊寫一個函式 balanced(s)，判斷字串中的 ()、[]、{} 是否正確配對。

參考答案

def balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0

print(balanced("{[()]}"))   # True
print(balanced("([)]"))     # False

練習 4：環狀佇列追蹤

容量 3 的環狀佇列依序執行：enqueue A、enqueue B、dequeue、enqueue C、enqueue D。寫出最後陣列內容與 front 的值。

參考答案

enqueue A → [A, _, _] front = 0；enqueue B → [A, B, _]；dequeue 取出 A → front = 1；enqueue C → [A, B, C]（索引 0 的 A 已無效）；enqueue D → rear = (1 + 2) % 3 = 0 → [D, B, C]，front = 1，佇列順序為 B、C、D。

練習 5：選擇實作

一個音樂播放清單經常在中間插入或刪除歌曲，但很少依位置直接跳到第 n 首。應用陣列還是雙向鏈結串列？

參考答案

雙向鏈結串列。在已知位置插入、刪除只要改指標 O(1)，且可以往前（上一首）往後（下一首）走訪；很少依索引存取，所以鏈結串列 O(n) 的存取缺點影響不大。

線性 ADT：鏈結串列、堆疊與佇列

鏈結串列如何運作？

陣列和鏈結串列怎麼比較？

如何實作鏈結串列？

如何實作堆疊？

如何實作環狀佇列？

推薦影音

鏈結串列（HackerRank）

堆疊與佇列（HackerRank）

練習題