Data structure and Algorithm Roadmap

前言#

這個系列文章是針對資料結構跟演算法的複習。我不會逐一介紹每個資料結構的定義，因為相信能看到這篇文章的各位都已經很熟悉了，而是會直接帶入 Leetcode 上的題目。

這個系列的重點在於把觀念串起來：知道一個資料結構是什麼，跟知道什麼時候該用它，是兩件不同的事。前者看一次就會，後者要靠反覆遇到問題才建立得起來。

系列第一篇就先針對上面這張心智圖做一些說明，後續的文章再逐項展開。

Array#

排序演算法的部分不多做說明，但這裡提到一個實用的技巧：如果是字串的題目，可以先把它轉成陣列。因為字串建立後是不可變的（immutable），每次修改都會產生新的字串，轉成陣列處理會方便許多：

Copied!
s = " I am a student. I love programming. "
words = s.split()
# ['I', 'am', 'a', 'student.', 'I', 'love', 'programming.']

s = "hello"
arr = list(s)
# ['h', 'e', 'l', 'l', 'o']

Static array 與 Dynamic array#

因為我大部分都使用 Python，而 Python 自己的靜態陣列不太常被使用，大部分的人都用 NumPy；Python 的 list 本身則是動態陣列。

Static 代表它的大小不能改變，存放的資料型態也是固定的：

Copied!
import numpy as np

a = np.array([[1, 2, 3]])

a[0] = [1, 2]          # error：形狀不符

a[0] = ['a', 'b', 'c'] # error：型別不符

NumPy 中也有 append，但它會複製原本的 array 再回傳，所以是 O(n)；list 的 append 才是攤銷後的 O(1)。

Dynamic array 雖然 append 快，但也有代價：它為了保留擴充空間，記憶體配置不像靜態陣列那麼緊密，而且 Python 的 list 存的是物件指標而不是數值本身。相反地，static array 因為型別一致、大小固定，資料可以連續存放在記憶體中，cache miss 的機率就會下降——這也是為什麼 NumPy 適合數值計算。

關於搜尋#

心智圖最後提到搜尋策略的選擇，這其實是一個很好的決策範例：

已經排序：直接 Binary Search，O(log n) 解決。
還沒排序，而且只需要找少數幾次：直接 Linear Search 就好。排序本身要 O(n log n)，為了找一次而先排序並不划算。
還沒排序，且是字串：可以考慮用 Trie（字典樹），特別是需要做前綴比對的時候。

Stack 與 Queue#

Stacks（堆疊）#

定義：LIFO（Last In First Out，後進先出）
常見操作：
- push → 放入元素
- pop → 移除頂端元素
- peek → 查看頂端元素
- lookup → 找特定元素

這邊提到可以使用 array 或是 linked list 來實作，在 Python 中大部分都是直接用前面提到的動態陣列（list）處理，append 和 pop 都是 O(1)。

Stack 最常出現的場景是需要回溯的問題：括號配對、DFS、函式呼叫堆疊，本質上都是「最後放進去的最先要處理掉」。

Queues（佇列）#

定義：FIFO（First In First Out，先進先出）

在 Python 中是用 collections.deque 來實作。這裡有一個很常見的錯誤是直接用 list.pop(0) 當作 dequeue，但那是 O(n)，因為後面所有元素都要往前搬；deque.popleft() 才是 O(1)。

Hash Table#

Hash Table 就是用一個 hash function（雜湊函數） 把 key 轉換成 array index：

例：hash("apple") → 37
然後把 (key, value) 存在對應的 bucket
優點是查找非常快，平均 O(1)

在 Python 裡，dict 和 set 就是 Hash Table。

心智圖上有一個註解：

could be O(n) with hash collisions and dynamic array resizing but unlikely

意思是：

在理想情況下，hash function 分布均勻 → O(1)
如果發生 hash collision（碰撞），可能退化成 O(n)，例如全部 key 都算到同一個 bucket

常見的碰撞解法有：

Chaining：每個 bucket 存一條 linked list
Open addressing：碰撞時往下一格找位置
Resize + Rehash：Python dict 採用的做法

另一個註解是 Fast Access O(1), tradeoff: more memory O(n)，意思是 Hash Table 為了維持 O(1)，必須刻意留出空位（load factor < 1），所以會多耗一些記憶體。例如 Python dict 的 load factor 大約在 2/3 左右，超過就會 resize，重建一個更大的陣列。

實務上，如果需要查找的資料量不會太大，把 list 換成 set 往往是最省力的加速方式——一行的改動，就把 O(n) 的成員檢查變成 O(1)。

Graph#

這邊主要的重點就是 BFS 跟 DFS，這部分會在之後講 Graph 練習題時補充。

除此之外，關於加權圖的最短路徑要特別留意：BFS 找到的最短路徑只在等權的情況下成立，如果邊有不同權重，BFS 找到的是「邊數最少」的路徑，而不是「總權重最小」的路徑，DFS 就更不用說了。

針對加權圖的最短路徑，應該使用底下這些演算法：

Dijkstra：權重皆為非負時的標準解
Bellman-Ford：可以處理負權重的邊
A*：有額外的啟發式資訊（例如地圖上的直線距離）時，能大幅縮小搜尋範圍

這些演算法也會在之後的文章中介紹。

Tree#

Tree 應該是這之中最重要的概念了，因為後面很多結構都是它的變形。

Linked List#

之所以會被放在這邊，是因為 linked list 其實就是 tree 的一個特殊情況——每個節點只有一個子節點的樹。

Binary Tree#

其中的 Binary Search Tree 代表對每一個節點都滿足「左子樹 < 根節點 < 右子樹」。這樣一來查找時只需要 O(h)，h 是樹的高度，在平衡的情況下 h = O(log n)。

但在最壞的情況下，如果一直往同一邊加，它就會退化成 linked list：

Copied!
1
 \
  2
   \
    3
     \
      4

這樣查找就變成 O(n)，完全失去 BST 的意義。所以才會多出 Balanced BST 這個概念，它會在插入與刪除時自動調整，保證樹的高度維持在 O(log n)。

再細分還有 AVL 跟 Red-Black Tree，兩者的差別在於平衡的嚴格程度：AVL 查找更快但調整更頻繁，Red-Black 則在插入刪除較多的情境下表現更好。這在之後的文章會介紹。

Heap#

Binary Heap 本質上就是一棵完全二元樹，分為 Min Heap 跟 Max Heap。它主要用在 Priority Queue 上，取出最小（或最大）值只要 O(log n)。

要注意的是 heap 只保證「父節點與子節點之間的大小關係」，兄弟節點之間沒有順序，所以要查找一個任意的值仍然需要 O(n)。它是拿來取極值的，不是拿來搜尋的。

DP#

Dynamic Programming 不算是一個資料結構，但是一個非常重要的觀念。它的核心是辨認出「重複計算的子問題」，把算過的結果記下來重複使用。

之後也會出一篇文章針對 DP 做詳細的介紹，包含一些經典的題目。

結語#

這篇主要就是一份資料結構跟演算法的 Roadmap。真正的價值不在於記住每個結構的複雜度表，而在於未來遇到問題時，能快速判斷「這個問題的形狀」對應到哪一個工具：需要回溯就想到 stack、需要最短路徑就想到 BFS、查找變成瓶頸就想到 hash table。

當然演算法是一個非常大的領域，甚至還可以再往最佳化的方向深入，針對最佳化演算法之後也會出一篇文章介紹。