📊 資料結構總複習

1️⃣ 為什麼要學習資料結構？

資料結構是程式的基石，選擇正確的資料結構可以讓程式更高效、更簡潔。

• 效率：不同的資料結構有不同的时间复杂度
• 組織：幫助我們有效地組織和存取資料
• 解決問題：許多經典問題都有對應的最佳資料結構解決方案

3️⃣ 連結串列（Linked List）

基本概念

每個節點包含資料和指向下一個節點的指標。

* 如果有尾指針則為 O(1)

單向串列實作

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node
    
    def delete(self, val):
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return
            current = current.next

5️⃣ 佇列（Queue）

基本概念

先進先出（FIFO, First In First Out）的資料結構。

Python 實作（使用 collections.deque）

from collections import deque

queue = deque()

# enqueue
queue.append(10)
queue.append(20)
queue.append(30)

# dequeue
front = queue.popleft()  # front = 10

# 查看前端
print(queue[0])  # 20

# 判斷空
if not queue:
    print("佇列為空")

雙端佇列（Deque）

兩端都可以進行插入和刪除：

# 雙端操作
queue.appendleft(5)   # 在前端插入
queue.append(40)      # 在尾端插入
queue.popleft()       # 從前端刪除
queue.pop()           # 從尾端刪除

7️⃣ 樹（Tree）

基本概念

由節點組成的層級資料結構，有一個根節點。

常用術語

• 根節點（Root）：樹的最頂端節點
• 葉節點（Leaf）：沒有子節點的節點
• 深度（Depth）：根到該節點的路徑長度
• 高度（Height）：該節點到最深葉節點的路徑長度
• 子樹（Subtree）：節點及其所有後代

二元樹遍歷

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

# 前序遍歷（根 -> 左 -> 右）
def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

# 中序遍歷（左 -> 根 -> 右）
def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

# 後序遍歷（左 -> 右 -> 根）
def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

📊 資料結構比較總表

* 頭部操作 | ** 平均情況 | *** 平衡樹