資料結構概論

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

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

🔥 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)}")

如何選擇？

| 資料結構 | 適合場景 | 不適合場景 | |---------|---------|-----------| | 陣列 | 隨機存取多、大小固定 | 頻繁插入/刪除 | | 鏈結串列 | 頻繁插入/刪除、大小不固定 | 需要隨機存取 | | 雜湊表 | 鍵值對查詢、去重 | 需要有序遍歷 | | 二元搜尋樹 | 需要有序資料、範圍查詢 | 資料量極大（需平衡樹） |

總結

陣列: 隨機存取 O(1)，但插入/刪除慢
鏈結串列: 插入/刪除 O(1)，但隨機存取慢
雜湊表: 平均 O(1) 查詢，不保留順序
二元搜尋樹: O(log n) 操作，保留排序

實戰練習

💡 Vibe Coding 練習：請 AI 建立一個「資料結構效能比較工具」：

對陣列、鏈結串列、雜湊表、BST 進行 10000 次插入/搜尋/刪除操作

精確測量每種操作的時間

輸出比較圖表

分析每種資料結構的適用場景