資料結構概論

程式 = 資料結構 + 演算法。

選擇正確的資料結構，往往比寫出完美的演算法更重要——因為資料結構決定了你的程式能跑多快、花多少記憶體。

🔥 Vibe Prompt

「用 Python 實作以下資料結構並比較效能：動態陣列 (Dynamic Array)、雙向鏈結串列 (Doubly Linked List)、雜湊表 (Hash Table) 與二元搜尋樹 (BST)。每個結構至少包含插入、刪除、搜尋操作，並用 10000 筆資料測試時間複雜度。」

陣列 (Array)

最基礎的資料結構。元素在記憶體中連續存放，可透過索引 O(1) 存取。

| 操作 | 時間複雜度 | 說明 | |------|-----------|------| | 存取 (Access) | O(1) | 透過索引直接取得 | | 搜尋 (Search) | O(n) | 需要遍歷（除非已排序） | | 插入 (Insert) | O(n) | 需要移動後續元素 | | 刪除 (Delete) | O(n) | 需要移動後續元素 |

# Python 動態陣列實作
class DynamicArray:
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.array = [None] * self.capacity
    
    def _resize(self, new_capacity):
        new_array = [None] * new_capacity
        for i in range(self.size):
            new_array[i] = self.array[i]
        self.array = new_array
        self.capacity = new_capacity
    
    def append(self, item):
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        self.array[self.size] = item
        self.size += 1
    
    def insert(self, index, item):
        if index < 0 or index > self.size:
            raise IndexError("Index out of range")
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        for i in range(self.size, index, -1):
            self.array[i] = self.array[i - 1]
        self.array[index] = item
        self.size += 1
    
    def delete(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        for i in range(index, self.size - 1):
            self.array[i] = self.array[i + 1]
        self.array[self.size - 1] = None
        self.size -= 1
    
    def __getitem__(self, index):
        if index < 0 or index >= self.size:
            raise IndexError("Index out of range")
        return self.array[index]
    
    def __len__(self):
        return self.size

# 測試
da = DynamicArray()
for i in range(10):
    da.append(i)
print(f"陣列內容: {[da[i] for i in range(len(da))]}")
print(f"容量: {da.capacity}, 大小: {len(da)}")
da.insert(0, 100)
print(f"插入後: {[da[i] for i in range(len(da))]}")
da.delete(5)
print(f"刪除後: {[da[i] for i in range(len(da))]}")

鏈結串列 (Linked List)

元素不連續存放，每個節點包含資料與指向下一個節點的指標。

| 操作 | 時間複雜度 | 說明 | |------|-----------|------| | 存取 (Access) | O(n) | 需要從頭遍歷 | | 搜尋 (Search) | O(n) | 需要遍歷 | | 插入 (Insert) | O(1) | 只需修改指標（已知位置） | | 刪除 (Delete) | O(1) | 只需修改指標（已知位置） |

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        node = Node(data)
        if not self.head:
            self.head = self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        self.size += 1
    
    def prepend(self, data):
        node = Node(data)
        if not self.head:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head.prev = node
            self.head = node
        self.size += 1
    
    def delete(self, data):
        current = self.head
        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                self.size -= 1
                return True
            current = current.next
        return False
    
    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next
    
    def __len__(self):
        return self.size

# 測試
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.prepend(0)
print(f"鏈結串列: {list(dll)}")  # [0, 1, 2, 3]
dll.delete(2)
print(f"刪除 2 後: {list(dll)}")  # [0, 1, 3]

雜湊表 (Hash Table)

透過雜湊函數將鍵映射到陣列索引，達到平均 O(1) 的存取速度。

| 操作 | 平均 | 最差 | |------|------|------| | 存取 | O(1) | O(n) | | 搜尋 | O(1) | O(n) | | 插入 | O(1) | O(n) | | 刪除 | O(1) | O(n) |

class HashTable:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def _resize(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)
    
    def put(self, key, value):
        if self.size >= self.capacity * 0.75:
            self._resize()
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (key, value)
                return
        self.buckets[idx].append((key, value))
        self.size += 1
    
    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)
    
    def delete(self, key):
        idx = self._hash(key)
        for i, (k, _) in enumerate(self.buckets[idx]):
            if k == key:
                del self.buckets[idx][i]
                self.size -= 1
                return
        raise KeyError(key)
    
    def __contains__(self, key):
        try:
            self.get(key)
            return True
        except KeyError:
            return False

# 測試
ht = HashTable()
ht.put("name", "Alice")
ht.put("age", 25)
ht.put("city", "Taipei")
print(f"name = {ht.get('name')}")
print(f"age = {ht.get('age')}")
print(f""city" 是否存在: {'city' in ht}")
ht.delete("age")
print(f""age" 是否存在: {'age' in ht}")

二元搜尋樹 (Binary Search Tree)

每個節點最多有兩個子節點：左子節點的值 < 父節點 < 右子節點的值。

| 操作 | 平均 | 最差（歪斜樹） | |------|------|---------------| | 搜尋 | O(log n) | O(n) | | 插入 | O(log n) | O(n) | | 刪除 | O(log n) | O(n) |

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        current = self.root
        while True:
            if val < current.val:
                if current.left:
                    current = current.left
                else:
                    current.left = TreeNode(val)
                    break
            else:
                if current.right:
                    current = current.right
                else:
                    current.right = TreeNode(val)
                    break
    
    def search(self, val):
        current = self.root
        while current and current.val != val:
            if val < current.val:
                current = current.left
            else:
                current = current.right
        return current is not None
    
    def inorder(self, node=None, result=None):
        if result is None:
            result = []
        if node is None:
            node = self.root
        if node:
            self.inorder(node.left, result)
            result.append(node.val)
            self.inorder(node.right, result)
        return result

# 測試
bst = BinarySearchTree()
for v in [5, 3, 7, 2, 4, 6, 8]:
    bst.insert(v)
print(f"中序遍歷: {bst.inorder()}")  # [2, 3, 4, 5, 6, 7, 8]
print(f"搜尋 4: {bst.search(4)}")
print(f"搜尋 9: {bst.search(9)}")

樹的遍歷 (Tree Traversal)

def inorder(node):
    """中序遍歷：左→根→右"""
    if node:
        inorder(node.left)
        print(node.val, end=" ")
        inorder(node.right)

def preorder(node):
    """前序遍歷：根→左→右"""
    if node:
        print(node.val, end=" ")
        preorder(node.left)
        preorder(node.right)

def postorder(node):
    """後序遍歷：左→右→根"""
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.val, end=" ")

# 測試
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print("中序:", end=" "); inorder(root)   # 4 2 5 1 3
print("\n前序:", end=" "); preorder(root)  # 1 2 4 5 3
print("\n後序:", end=" "); postorder(root) # 4 5 2 3 1

堆積 (Heap / Priority Queue)

堆積是一種特殊的完全二元樹，父節點的值總是大於（最大堆）或小於（最小堆）子節點。

| 操作 | 時間複雜度 | |------|-----------| | 插入 (push) | O(log n) | | 取出最大/最小 (pop) | O(log n) | | 取得最大/最小 (peek) | O(1) |

import heapq

# 最小堆
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heapq.heappop(heap))  # 1（最小值）
print(heap[0])  # 3（查看最小值）

圖形表示法

# 鄰接矩陣（適合稠密圖）
graph_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

# 鄰接串列（適合稀疏圖）
graph_list = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2],
}

總結

| 資料結構 | 存取 | 搜尋 | 插入 | 刪除 | |---------|------|------|------|------| | 陣列 | O(1) | O(n) | O(n) | O(n) | | 鏈結串列 | O(n) | O(n) | O(1) | O(1) | | 雜湊表 | O(1)* | O(1)* | O(1)* | O(1)* | | BST | O(log n)* | O(log n)* | O(log n)* | O(log n)* | | 堆積 | O(1) | O(n) | O(log n) | O(log n) |

*平均情況，最差可能為 O(n)

實戰練習

💡 Vibe Coding 練習：請 AI 建立一個「資料結構與演算法互動式學習工具」：

效能比較：比較陣列、鏈結串列、雜湊表、BST、堆積的 10000 次操作時間

樹遍歷可視化：動態展示前序/中序/後序遍歷的過程

堆積操作模擬：逐步展示 push/pop 時的 heapify 過程

圖形探索工具：輸入邊的資訊，自動產生鄰接矩陣和串列

四種你一定要知道的資料結構

Array vs Linked List

| 比較 | Array | Linked List | |:----|:----|:----------| | 隨機存取 | O(1) — 直接算位置 | O(n) — 要遍歷 | | 插入/刪除 | O(n) — 要搬移 | O(1) — 改指標 | | 記憶體 | 連續區塊 | 分散的節點 | | 大小 | 固定（動態陣列需重新分配） | 動態增長 |

Hash Table（雜湊表）

Hash Table 是最強大的資料結構——插入、刪除、查詢都是平均 O(1)。關鍵是雜湊函數把鍵均勻映射到 bucket。

Python 的 dict、JS 的 Map、Set 底層都是 Hash Table。

Tree（樹）

二元搜尋樹（BST）讓所有操作維持 O(log n)。但最關鍵的是——資料庫索引 B-Tree 是 BST 的泛化版本。

下一章預告：基本演算法

有了資料結構，下一章看看怎麼操作它們——排序和搜尋演算法。