🇹🇼
Data structure and Algorithm

Data structure and Algorithm

發佈時間

這個系列文章是針對資料結構跟演算法的複習，但我不會針對各個資料結構多做說明，因為相信能看到這篇文章的各位都已經很熟悉了，會直接帶入 Leetcode 上面的題目，這個系列主要是希望把這些觀念串起來，讓這些觀念可以應用在實際開發時的技能．

Screenshot 2025-09-06 at 12.54.28 PM.png

那這個系列第一篇就先針對上面這張資料結構跟演算法的心智圖做一些簡單的說明

Array#

Screenshot 2025-09-06 at 1.04.45 PM.png

sorting 演算法的部分不多做說明，但它提到如果是 string question，可以把它先轉成陣列，因為字串建立後是不能被修改的，所以轉為陣列為方便許多，像是

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 代表它本身的大小是不能改變，存放的資料型態也不能改變

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 雖然 append 快，但他也有缺點，因為他的記憶體分配是不連續的，相反的，static 因為型別一致，可以存放在連續的記憶體中，這樣一來 cache miss 的機率就會下降，所以才說 numpy 會適合數值計算．

最後還有提到 關於 searching 的部分

  • 已經 sort ，直接 Binary search O(log n) 解決
  • 還沒 sort ，但其實只需要找少量次數，直接 Linear search 就好
  • 還沒 sort ，且是字串的話，可以考慮用 Trie (字典樹) 這個資料結構

Stack && Queue#

Screenshot 2025-09-06 at 3.19.14 PM.png

Stacks (堆疊)#

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

這邊他有提到可以使用 array 或是 linked list 來實作，那在 python 中大部分都是用前面所提到的 動態陣列來處理

Queues (佇列)#

  • 定義：FIFO（First In First Out，先進先出）資料結構。

在 python 中是用 deque 來實作的

Hash table#

Screenshot 2025-09-06 at 3.32.00 PM.png

Hash table 就是用一個 hash function (雜湊函數) 把「key」轉換成「array index」。

  • 例：hash("apple") → 37
  • 然後把 (key, value) 存在對應的 bucket。
  • 優點就是查找很快，O(n)

在 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 (重建更大的陣列)。

如果需要查找的資料不會太大，用 set 會是一個加快查找的好方法．

Graph#

Screenshot 2025-09-06 at 3.40.09 PM.png

這邊主要重點就是 BFS 跟 DFS，這個會在之後講 針對 Graph 的練習時補充

除此之外，有提到關於有權圖的最短路徑，因為 BFS 所找到的最短路徑是在等權的情況下，如果是不等權的，他所找到的是 最短邊數 的選擇，而不是最短路徑， DFS 就更不用說了，針對有權圖的最短路徑演算法應該是底下這些 ：

  • Dijkstra
  • Bellmen-Ford
  • A*

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

Tree#

Screenshot 2025-09-06 at 3.40.21 PM.png

Tree 應該是這之中最重要的概念了

Linked List#

之所以會被放在這邊是因為，linked list 其實就是 tree 的一個特殊情況．

Binary Tree#

其中的 Binary Search Tree 代表的是對每一個節點 左子樹 < 根節點 < 右子樹，這樣一來查找的時候，只需要查找 O(h) = O(log n)，但在最壞的情況下，他一直往同一邊加，就會變成 Linked List，像是

1
 \
  2
   \
    3
     \
      4

這樣查找就會變成 O(n)，所以才會多出一個叫 Balanced BST，他會保證數的高度會是 log(log n)，

再細分還有 AVL 跟 Red-Black，這在之後的文章會介紹

Heap#

Binary Heap 本質上 就是一棵完全二元樹，它分為 Min heap 跟 Max heap，他主要是用在 Priority queue上，因為他沒有排序結構，查找是需要 O(n)

DP#

Dynamic programming 不算是一個資料結構，但是是一個很重要的觀念，之後也會出一篇文章，針對 DP 做詳細的介紹，包含一些經典的題目．

這篇大概就講到這．主要就是一個對 資料結構 跟 演算法 的 Roadmap，在未來遇到問題的時後可以知道要用哪個資料結構跟演算法可以更有效解決問題，當然演算法是一個非常大的領域，甚至他可以再做最佳化，針對最佳化演算法之後也會出一篇文章介紹．