書籍資訊

  • 書名：《圖解演算法：使用 C#》
  • 類型：演算法與資料結構入門讀書筆記

這篇在講什麼

這一篇把常見資料結構先做了一輪總整理，重點不是把名詞背下來，而是理解：

  • 每種資料怎麼存
  • 取資料和改資料的成本差在哪裡
  • 什麼問題比較適合用哪一種結構

資料結構的角色

資料結構可以理解成：

你打算怎麼擺放資料，讓之後的操作更有效率。

同樣一組資料，放在不同的結構裡，插入、刪除、搜尋、遍歷的成本都可能完全不同。
所以演算法不只是「流程怎麼走」，也包含「資料怎麼放」。

陣列

陣列的特點是：

  • 元素連續存放在記憶體中
  • 可以直接用索引讀取
  • 讀取與修改很快

它的優點很明顯：

  • 適合需要頻繁隨機存取的場景
  • 結構簡單，實作成本低

但代價也很直接：

  • 中間插入或刪除元素時，常常要搬動後面的資料
  • 長度固定的情境下，擴充不方便

鏈結串列

鏈結串列不是把資料排成一整塊，而是讓每個節點各自記住下一個節點的位置。

它比較適合：

  • 常常在中間插入資料
  • 常常刪除資料
  • 不強調用索引直接跳到第 i 個元素

和陣列相比，可以這樣記：

  • 陣列：查得快，改位置慢
  • 鏈結串列：改位置方便，查找慢

堆疊與佇列

這兩種結構都很常見，但規則不同。

堆疊 Stack

  • 後進先出，Last In First Out
  • 最後放進去的，最先拿出來

典型用途：

  • 函式呼叫堆疊
  • 括號匹配
  • DFS

佇列 Queue

  • 先進先出，First In First Out
  • 最先放進去的，最先拿出來

典型用途：

  • 排隊處理工作
  • BFS
  • 訊息緩衝

樹

樹用來描述有層級關係的資料。

常見名詞包括：

  • 根節點：最上層的起點
  • 父節點 / 子節點：上下層關係
  • 葉節點：沒有子節點的節點
  • 深度 / 高度 / 層數：描述節點位置與整棵樹規模

樹特別適合：

  • 組織分層資料
  • 表示決策流程
  • 支援搜尋與排序相關結構，例如 BST、Heap、Trie

圖

圖比樹更一般化，因為它不要求單一根節點，也不要求沒有環。

可以把圖理解成：

  • 節點：代表物件或狀態
  • 邊：代表關係或路徑

常見分類：

  • 無向圖：關係是雙向的
  • 有向圖：關係有方向
  • 加權圖：邊上帶有成本或距離

圖常被用在：

  • 路徑搜尋
  • 社群關係
  • 依賴分析

雜湊表

雜湊表的核心概念是：

  • 透過 hash function 把 key 映射到某個位置
  • 希望能在平均情況下快速查找、插入、刪除

它很適合：

  • 查某個值是否存在
  • 統計次數
  • 建立 key-value 對應

要注意的點是碰撞 collision。
不同 key 經過雜湊後，可能會落到同一格，所以雜湊表真正的重點不只是「快」，還包括：

  • hash function 是否分布均勻
  • 碰撞怎麼處理
  • 裝載因子是否過高

我自己的整理

這一篇讀下來，真正有用的不是記住一長串定義，而是先建立一個選型習慣：

  • 需要快速索引：先想到陣列
  • 需要頻繁插刪：先想到鏈結串列
  • 需要先進先出：先想到佇列
  • 需要後進先出：先想到堆疊
  • 需要層級關係：先想到樹
  • 需要複雜關係或路徑：先想到圖
  • 需要快速對照或統計：先想到雜湊表

先記住的重點

  • 演算法效率常常取決於資料怎麼放，不只是流程怎麼寫
  • 陣列適合快速索引，鏈結串列適合彈性插刪
  • Stack 與 Queue 的差別，本質上就是取出順序不同
  • 樹處理層級，圖處理一般關係
  • Hash Table 的價值在快速查找，但前提是碰撞控制得好