從零開始寫程式，輕鬆搞懂資料結構、演算法

Ch.01

陣列與單向鏈結串列（Array & Singly Linked List）

理解連續記憶體配置（Array）與指標節點串接（Linked List）的本質差異，並以 Python Generic 型別實作單向鏈結串列的增刪查與 O(1) 額外空間原地反轉。

⏱️ 時間／空間複雜度：頭部插入 O(1) ・尾部附加 / 搜尋 / 刪除 / 原地反轉 O(n) 📄 原始碼路徑：examples/ch01_array_linked_list.py

#!/usr/bin/env python3
"""
Ch.01 陣列與單向鏈結串列（Array & Singly Linked List）
展示基礎節點（ListNode）與單向鏈結串列（SinglyLinkedList）的插入、刪除、搜尋與反轉操作。
"""

from __future__ import annotations
from dataclasses import dataclass
from typing import Generic, Iterable, Optional, TypeVar

T = TypeVar("T")


@dataclass
class ListNode(Generic[T]):
    val: T
    next: Optional[ListNode[T]] = None


class SinglyLinkedList(Generic[T]):
    """教學用單向鏈結串列實作（支援頭尾插入、指定值刪除、搜尋與原地反轉）。"""

    def __init__(self, values: Optional[Iterable[T]] = None) -> None:
        self.head: Optional[ListNode[T]] = None
        self._size: int = 0
        if values is not None:
            for v in values:
                self.append(v)

    def __len__(self) -> int:
        return self._size

    def prepend(self, val: T) -> None:
        """在串列頭部插入新節點，時間複雜度 O(1)。"""
        self.head = ListNode(val=val, next=self.head)
        self._size += 1

    def append(self, val: T) -> None:
        """在串列尾部附加新節點，時間複雜度 O(n)。"""
        new_node = ListNode(val=val)
        if self.head is None:
            self.head = new_node
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = new_node
        self._size += 1

    def find(self, target: T) -> int:
        """搜尋目標值首次出現的索引（0-based），若不存在回傳 -1。"""
        idx = 0
        curr = self.head
        while curr is not None:
            if curr.val == target:
                return idx
            curr = curr.next
            idx += 1
        return -1

    def remove(self, target: T) -> bool:
        """刪除首次出現的目標值節點，成功回傳 True，不存在回傳 False。"""
        prev: Optional[ListNode[T]] = None
        curr = self.head
        while curr is not None:
            if curr.val == target:
                if prev is None:
                    self.head = curr.next
                else:
                    prev.next = curr.next
                self._size -= 1
                return True
            prev = curr
            curr = curr.next
        return False

    def reverse(self) -> None:
        """原地（in-place）反轉鏈結串列，時間複雜度 O(n)，空間複雜度 O(1)。"""
        prev: Optional[ListNode[T]] = None
        curr = self.head
        while curr is not None:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

    def to_list(self) -> list[T]:
        result: list[T] = []
        curr = self.head
        while curr is not None:
            result.append(curr.val)
            curr = curr.next
        return result


if __name__ == "__main__":
    sll = SinglyLinkedList([10, 20, 30])
    sll.prepend(5)
    sll.remove(20)
    sll.reverse()
    print("Ch.01 SinglyLinkedList 範例結果:", sll.to_list())

▶ 實機執行輸出驗證（CI 自動實測結果）

Ch.01 SinglyLinkedList 範例結果: [30, 10, 5]

Ch.02

堆疊與佇列（Stack & Queue）

掌握後進先出（LIFO）與先進先出（FIFO）兩大抽象資料型態（ADT），並透過 Stack 實作經典的面試常考題：多層括號平衡檢查器。

⏱️ 時間／空間複雜度：Push / Pop / Enqueue / Dequeue 均為 O(1) 📄 原始碼路徑：examples/ch02_stack_queue.py

#!/usr/bin/env python3
"""
Ch.02 堆疊與佇列（Stack & Queue）
展示 LIFO 堆疊（含經典括號平衡檢查）與 FIFO 佇列的物件導向封裝實作。
"""

from collections import deque
from typing import Generic, Optional, TypeVar

T = TypeVar("T")


class Stack(Generic[T]):
    """後進先出（LIFO）堆疊。"""

    def __init__(self) -> None:
        self._items: list[T] = []

    def push(self, item: T) -> None:
        self._items.append(item)

    def pop(self) -> T:
        if not self._items:
            raise IndexError("pop from empty Stack")
        return self._items.pop()

    def peek(self) -> T:
        if not self._items:
            raise IndexError("peek from empty Stack")
        return self._items[-1]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def __len__(self) -> int:
        return len(self._items)


class Queue(Generic[T]):
    """先進先出（FIFO）佇列。"""

    def __init__(self) -> None:
        self._items: deque[T] = deque()

    def enqueue(self, item: T) -> None:
        self._items.append(item)

    def dequeue(self) -> T:
        if not self._items:
            raise IndexError("dequeue from empty Queue")
        return self._items.popleft()

    def peek(self) -> Optional[T]:
        return self._items[0] if self._items else None

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def __len__(self) -> int:
        return len(self._items)


def is_balanced_brackets(expr: str) -> bool:
    """利用 Stack 檢查字串中的 (), [], {} 括號是否成對且順序正確。"""
    pairs = {")": "(", "]": "[", "}": "{"}
    opening = set(pairs.values())
    stack: Stack[str] = Stack()

    for ch in expr:
        if ch in opening:
            stack.push(ch)
        elif ch in pairs:
            if stack.is_empty() or stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()


if __name__ == "__main__":
    print("Ch.02 括號平衡檢查 '{[()]}':", is_balanced_brackets("{[()]}"))
    q: Queue[str] = Queue()
    q.enqueue("Task-1")
    q.enqueue("Task-2")
    print("Ch.02 Queue dequeue:", q.dequeue())

▶ 實機執行輸出驗證（CI 自動實測結果）

Ch.02 括號平衡檢查 '{[()]}': True
Ch.02 Queue dequeue: Task-1

Ch.03

搜尋與排序演算法（Search & Sort Algorithms）

比較線性搜尋與二分搜尋的效率跨越，並以分治法（Divide & Conquer）實作穩定排序演算法 Merge Sort。

⏱️ 時間／空間複雜度：二分搜尋法 O(log n) ・合併排序法（Merge Sort）O(n log n) 📄 原始碼路徑：examples/ch03_search_sort.py

#!/usr/bin/env python3
"""
Ch.03 搜尋與排序演算法（Search & Sort Algorithms）
展示二分搜尋法（Binary Search）與合併排序法（Merge Sort）。
"""

from typing import Sequence


def binary_search(sorted_nums: Sequence[int], target: int) -> int:
    """在已排序遞增序列中搜尋 target，回傳索引（0-based）；若不存在則回傳 -1。"""
    left = 0
    right = len(sorted_nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        val = sorted_nums[mid]
        if val == target:
            return mid
        if val < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


def merge_sort(nums: Sequence[int]) -> list[int]:
    """使用分治法（Divide & Conquer）實作穩定合併排序，時間複雜度 O(n log n)。"""
    arr = list(nums)
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    merged: list[int] = []
    i = j = 0
    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            merged.append(left_half[i])
            i += 1
        else:
            merged.append(right_half[j])
            j += 1

    if i < len(left_half):
        merged.extend(left_half[i:])
    if j < len(right_half):
        merged.extend(right_half[j:])
    return merged


if __name__ == "__main__":
    sample = [38, 27, 43, 3, 9, 82, 10]
    sorted_sample = merge_sort(sample)
    idx = binary_search(sorted_sample, 27)
    print("Ch.03 Merge Sort 結果:", sorted_sample, "| 27 的索引:", idx)

▶ 實機執行輸出驗證（CI 自動實測結果）

Ch.03 Merge Sort 結果: [3, 9, 10, 27, 38, 43, 82] | 27 的索引: 3