各種資料結構優點整理

1. Array

優點

可以透過 index 直接存取元素
Random Access 很快
記憶體連續，效率高
適合已知大小、常做查詢的資料

時間複雜度

Access: O(1)
Search: O(n)
Insert/Delete: O(n)

適合

頻繁用 index 查資料
Heap
Matrix
Dynamic Programming table

一句話記憶

Array：查位置很快，插刪較慢

2. Linked List

優點

不需要連續記憶體
插入、刪除方便
不需要搬動其他元素
大小可以動態改變

時間複雜度

Access: O(n)
Search: O(n)
Insert/Delete:
- 已知位置：O(1)
- 找位置：O(n)

適合

常做插入、刪除
資料數量經常改變

一句話記憶

Linked List：插刪方便，但不能直接跳到某個位置

3. Stack

特性

LIFO

Last In First Out

後進先出

優點

Push / Pop 都很快
適合處理「最近加入的資料」
很適合遞迴、括號匹配、Expression

時間複雜度

Push: O(1)
Pop: O(1)
Top: O(1)

適合

Function Call / Recursion
DFS
括號匹配
Infix / Prefix / Postfix
Undo

一句話記憶

Stack：最後進來的先處理

4. Queue

特性

FIFO

First In First Out

先進先出

優點

Enqueue / Dequeue 很快
可以按照到達順序公平處理

時間複雜度

Enqueue: O(1)
Dequeue: O(1)
Front: O(1)

適合

BFS
工作排隊
Printer Queue
CPU Scheduling
Buffer

一句話記憶

Queue：先來先服務

5. Circular Queue

優點

可以重複利用 Array 前面被刪除後留下的空間
避免一般 Array Queue 的空間浪費
Enqueue / Dequeue 都可以 O(1)

適合

Buffer
Producer / Consumer
循環排程

一句話記憶

Circular Queue：把 Array 繞一圈使用，不浪費空間

6. Heap

特性

Complete Binary Tree

常見：

Max-Heap
Min-Heap

優點

可以非常快取得最大值或最小值
Insert / Delete 效率高
很適合實作 Priority Queue
可以直接用 Array 儲存，不需要 pointer

時間複雜度

Find Max / Min: O(1)
Insert: O(log n)
Delete-Max / Delete-Min: O(log n)
Build Heap: O(n)

適合

Priority Queue
Job Scheduling
Heap Sort
找 Top-K

一句話記憶

Heap：想快速拿最大或最小就用它

7. Binary Search Tree, BST

特性

左子樹 < Root < 右子樹

優點

可以維持資料的大小順序
Search / Insert / Delete 平均都很快
Inorder Traversal 可以得到排序結果

平均時間複雜度

Search: O(log n)
Insert: O(log n)
Delete: O(log n)

最壞情況

如果 BST 歪掉：

O(n)

適合

動態搜尋
維持有序資料
Range Query

一句話記憶

BST：一邊存資料，一邊維持大小關係

8. Balanced BST

例如：

AVL Tree
Red-Black Tree

優點

避免普通 BST 歪掉
Search / Insert / Delete 都能維持 O(log n)

適合

需要穩定搜尋效率
Ordered Set
Ordered Map

一句話記憶

Balanced BST：BST 的穩定版本

9. Hash Table

優點

Search 非常快
Insert 非常快
Delete 非常快
平均可以做到 O(1)

平均時間複雜度

Search: O(1)
Insert: O(1)
Delete: O(1)

缺點

不會自動排序
可能發生 Collision
最壞可以到 O(n)

適合

Dictionary
Symbol Table
查某個 key 是否存在
Frequency Count

一句話記憶

Hash Table：只想快速查 key，不在乎順序

10. Tree

優點

適合表示階層式資料
可以表示 Parent / Child 關係
搜尋範圍可以逐層縮小

適合

File System
Organization Chart
Expression Tree
Syntax Tree

一句話記憶

Tree：最適合表示階層關係

11. Graph

優點

可以表示非常複雜的多對多關係
不限制只能有 Parent / Child
可以處理路徑、連通性、網路問題

適合

Social Network
地圖
Computer Network
Dependency
最短路徑

一句話記憶

Graph：最適合表示任意關係

12. Disjoint Set

又稱：

Union-Find
Disjoint Set Union

優點

可以快速判斷兩個元素是否屬於同一集合
可以快速合併兩個集合
搭配 Path Compression、Union by Rank / Size 非常快

操作

Find
Union

時間複雜度

經過最佳化後接近：

O(1)

更精確：

O(α(n))

適合

判斷 Connectivity
Kruskal MST
Dynamic Connectivity

一句話記憶

Disjoint Set：專門處理「是不是同一組」

考試快速比較表

Data Structure	最大優點	常見用途
Array	index 存取 O(1)	查位置
Linked List	插刪方便	動態資料
Stack	LIFO	DFS、遞迴
Queue	FIFO	BFS、排隊
Circular Queue	重複利用空間	Buffer
Heap	快速取 Max / Min	Priority Queue
BST	維持排序	動態搜尋
Balanced BST	保證 O(log n)	Ordered Set / Map
Hash Table	平均查找 O(1)	Key 查詢
Tree	階層關係	File System
Graph	任意關係	Network、路徑
Disjoint Set	判斷是否同集合	Kruskal、Connectivity

最重要的選資料結構口訣

如果題目說：

「用 index 快速找」
→ Array
「常常插入刪除」
→ Linked List
「後進先出」
→ Stack
「先進先出」
→ Queue
「Priority」
→ Heap
「一直找最大 / 最小」
→ Heap
「用 key 快速搜尋」
→ Hash Table
「資料要維持排序」
→ BST / Balanced BST
「階層關係」
→ Tree
「路徑、網路、連通」
→ Graph
「判斷兩個東西是不是同一組」
→ Disjoint Set