資料結構 Data Structure - paulip114/blog GitHub Wiki

🧩 常見資料結構分類總表

我們可以用以下方式分類：

  1. 線性資料結構（Linear Data Structures）
  2. 非線性資料結構（Non-linear Data Structures）
  3. 抽象資料型態（Abstract Data Types, ADT）
  4. 雜湊資料結構（Hashing）

🧱 一、線性資料結構（Linear Data Structures）

資料結構 說明
Array（陣列） 固定長度、可快速用索引存取，插入/刪除較慢
Linked List（連結串列） 每個節點連到下一個，插入/刪除快，但查找慢
- Singly Linked List 單向連結串列（只能往後）
- Doubly Linked List 雙向連結串列（可前後）
Stack（堆疊） LIFO（後進先出），如：網頁瀏覽歷史、函式呼叫堆疊
Queue（佇列） FIFO（先進先出），如：印表機佇列、任務排程
- Circular Queue 首尾相連的 Queue，空間利用率更高
- Priority Queue 根據優先權排序的佇列（底層可用 Heap 實作）

🌳 二、非線性資料結構（Non-linear Data Structures）

資料結構 說明
Tree（樹） 層級關係的資料，常用於表示結構（如 DOM、檔案系統）
- Binary Tree（每個節點最多兩個子節點）
- Binary Search Tree（BST）
- AVL Tree / Red-Black Tree（平衡樹，查找效率高）
- N-ary Tree（每個節點可有 N 個子節點）
- Segment Tree / Fenwick Tree（區間查詢）
Heap（堆） 一種特殊的 Tree，常用於 Priority Queue 和排序（HeapSort）
- Min Heap（父節點 ≤ 子節點）
- Max Heap（父節點 ≥ 子節點）
Trie（前綴樹） 優化字串搜尋，例如：自動補字、拼字檢查器
Graph（圖） 節點 + 邊，適合表示網路、地圖、社交關係等結構
- Directed / Undirected Graph（有向 / 無向）
- Weighted Graph（邊有權重，例如距離）

🧠 三、抽象資料型態（Abstract Data Types, ADT）

這些是「概念模型」，可用多種資料結構實作：

ADT 常見實作方式
List Array、Linked List
Stack Array、Linked List
Queue Array、Linked List、Circular Queue
Deque（雙端佇列） 可從兩端插入/刪除
Set（集合） Hash Table、BST
Map（字典） Hash Table、TreeMap

🧊 四、雜湊資料結構（Hashing）

資料結構 說明
Hash Table（Hash Map） 利用 key → value 的快速查找，如：字典、快取系統、資料庫索引
- Collision Handling（碰撞處理）：Open Addressing、Separate Chaining 等方式
Bloom Filter 空間效率高但有誤差的查找結構，用於快取預查詢、垃圾過濾等

📦 其他進階資料結構

資料結構 用途
Disjoint Set（Union-Find） 常用於圖論中的聯通性問題（如：Kruskal 最小生成樹）
LRU Cache 結合 Hash Map + Doubly Linked List 實作快取淘汰策略
Suffix Tree / Array 用於字串比對、重複字串搜尋等高效處理
Interval Tree 區間交集查詢，適用日曆、排程衝突檢查等

🧭 資料結構怎麼選？

選資料結構最重要的就是：

  • 操作需求： 插入多？查找多？排序需求？
  • 資料大小： 記憶體有限嗎？
  • 資料關係： 線性？階層？網狀？

一、需要快速查找（Key → Value）

✅ 情境：

  • 根據使用者 ID 查找使用者資料
  • 根據商品代碼查價格

🧰 選擇：

  • Hash Map / Object / Dictionary
    • 快速查找：O(1) 平均時間
    • TypeScript 可用：Record<string, T>、Map<K, V>

二、需要儲存排序後的資料並支援快速插入/查找

✅ 情境：

  • 排行榜、分數表
  • 保持一組數據有序（並不是一次全部排序）

🧰 選擇：

  • Binary Search Tree（BST）
  • AVL Tree / Red-Black Tree（自動保持平衡）

JS/TS 沒有內建 Tree，可以用外部函式庫或自己實作
Java 的 TreeSet、C++ 的 std::set 就是基於平衡 BST

三、先進先出（FIFO）邏輯

✅ 情境：

  • 任務排程
  • 網路請求佇列
  • 打印機列隊

🧰 選擇：

  • Queue（佇列）

在 TypeScript 中可以用 Array 模擬：

const queue: number[] = [];
queue.push(1);     // enqueue
const item = queue.shift(); // dequeue

四、後進先出（LIFO）邏輯

✅ 情境：

  • 函式呼叫堆疊
  • 括號匹配（像是 ()[]{} 檢查）
  • Undo 功能

🧰 選擇：

  • Stack（堆疊）

在 TS 中可以用 Array：

const stack: number[] = [];
stack.push(1);     // 入堆疊
const item = stack.pop();  // 出堆疊

五、需要儲存階層/父子資料

✅ 情境：

  • 檔案總管（資料夾 → 子資料夾）
  • 類別分類（主分類 → 子分類）
  • 選單系統（Menu / Submenu）

🧰 選擇：

  • Tree（Binary Tree / N-ary Tree）

六、需要表示網狀關係（節點互相連接）

✅ 情境：

  • 社交網路（人與人的關係）
  • 地圖導航（城市、路徑）
  • 網頁跳轉圖（Page → Link）

🧰 選擇：

  • Graph（圖）
    • 可使用鄰接表（Adjacency List）或鄰接矩陣（Adjacency Matrix）實作

七、要快速找最大或最小值

✅ 情境：

  • 頂部 N 個高分
  • 優先級處理（像任務優先順序）

🧰 選擇：

  • Heap（Min Heap / Max Heap）

JS/TS 沒有內建 heap，可以用外部函式庫或自己實作。

八、需要儲存大量字串並快速搜尋前綴

✅ 情境：

  • 自動補字（autocomplete）
  • 字典系統
  • 拼字檢查

🧰 選擇：

  • Trie（前綴樹）

比用陣列搜尋每一筆快非常多，尤其對大量字串處理。

九、資料需要頻繁插入 / 刪除

✅ 情境：

  • 不固定長度的資料流
  • 中間插入資料

🧰 選擇：

  • Linked List（連結串列）

如果要支援雙向移動：

  • 使用 Doubly Linked List

十、需要快速查找、合併集合（像是判斷兩人是否屬於同一群）

✅ 情境：

  • 社群聯通性
  • 團體判斷
  • 最小生成樹（MST）

🧰 選擇：

  • Disjoint Set / Union-Find

🎯 加碼：查詢資料範圍（Range）

✅ 情境：

  • 找出某段時間內的總和 / 最大值
  • 區間更新

🧰 選擇：

  • Segment Tree
  • Fenwick Tree（Binary Indexed Tree）

📌 快速整理成圖表：

需求 建議資料結構
根據鍵快速查找 Hash Map / Dictionary
排序且動態插入 BST / AVL Tree / Red-Black Tree
先進先出佇列 Queue
後進先出堆疊 Stack
儲存階層資料 Tree (Binary / N-ary)
網路圖結構 Graph
快速找最大/最小值 Heap
字串搜尋 / 自動補字 Trie
快速插入 / 刪除 Linked List
判斷是否同一群組 Union-Find
快速區間查詢 Segment Tree / Fenwick Tree
⚠️ **GitHub.com Fallback** ⚠️