資料結構
前言
程式 = 資料結構 + 演算法。 前面我們學了 CPU 如何執行指令、作業系統如何管理資源。但程式要處理的核心物件是資料——使用者資訊、商品列表、社交關係……這些資料怎麼在記憶體裡組織，直接決定了程式的快慢。
這篇文章會帶你學什麼？
學完這章後，你將獲得：
- 直覺判斷力：看到一個需求，腦子裡自動浮現該用什麼資料結構
- 效能分析視角：能判斷效能瓶頸是資料結構選錯了，還是演算法效率低
- 權衡思維：理解「空間換時間」與「時間換空間」
- 程式碼閱讀能力：看到 HashMap、Stack、Queue 這些詞不再陌生
| 章节 | 內容 | 核心概念 |
|---|---|---|
| 第 1 章 | 全景圖 | 四大類資料結構 |
| 第 2 章 | 線性結構 | 陣列、鏈結串列、堆疊、佇列 |
| 第 3 章 | 雜湊表 | 雜湊函式、衝突處理、O(1) 搜尋 |
| 第 4 章 | 樹形結構 | 二元樹、檔案系統樹、DOM 樹 |
| 第 5 章 | 圖結構 | 有向圖、無向圖、遍歷演算法 |
| 第 6 章 | 效能對比 | 時間複雜度、空間複雜度 |
| 第 7 章 | 選型指南 | 場景分析、決策流程 |
1. 全景圖：資料結構是什麼？
想象你要整理一堆書：
- 堆在地上：找書要一本本翻——這就是最原始的儲存
- 按編號放書架：直接去對應位置拿——這就是陣列
- 按類別分櫃子：先確定櫃子再找書——這就是雜湊表
- 按書名排序放多層架：每次排除一半——這就是樹
Data Structure OverviewChoose a data organization model for each scenario
Data structures are like ways to organize a room: clothes in a wardrobe, books on shelves, and small items in drawers.
Linear structures
Data arranged in order, like a row of books
ArrayLinked listStackQueue
Hash structures
Fast lookup through a key
Hash tableDictionarySet
Tree structures
Hierarchy, like a family tree
Binary treeB-treeHeap
Graph structures
Complex relationship networks
Directed graphUndirected graphNetwork graph
Linear structures
Features
One-to-one relationship between elements
A clear before-and-after order
Can use contiguous storage or linked storage
Use Cases
Arrays: list data
Store ordered data such as student scores or product prices
Stacks: undo operations
Text editor undo history, last in first out
Queues: task scheduling
Print queues and task queues, first in first out
Operation Complexity
OperationAverage time
Access elementO(1)
Insert/deleteO(n)
Everyday Analogy
Like train cars connected in order
To find car 5, count directly to it; to insert a new car, you need to break and reconnect links.
所有資料結構可以歸為四大類：
| 類型 | 資料關係 | 典型代表 | 生活類比 |
|---|---|---|---|
| 線性結構 | 一對一，排成一排 | 陣列、鏈結串列、堆疊、佇列 | 火車車廂、排隊隊伍 |
| 雜湊結構 | 鍵→值對應 | 雜湊表、字典、集合 | 圖書館索引卡片 |
| 樹形結構 | 一對多，層級關係 | 二元樹、B樹、堆積 | 家族族譜、資料夾 |
| 圖結構 | 多對多，網狀關係 | 有向圖、無向圖 | 捷運路線圖、社交網路 |
2. 線性結構：最基礎的組織方式
Four Forms of Linear StructuresHow arrays, linked lists, stacks, and queues differ
ArrayContiguous memory, indexed access
0
10
1
25
2
33
3
47
4
59
5
62
✓ Contiguous memory | ✓ Fast access (O(1)) | ✗ Slow insert/delete (O(n))
Operation Comparison
| Data structure | Access | Insert | Delete | Feature |
|---|---|---|---|---|
| 📊 Array | O(1) fast | O(n) slow | O(n) slow | Fixed size |
| 🔗 Linked list | O(n) slow | O(1) fast | O(1) fast | Variable size |
| 🥞 Stack | O(n) | O(1) fast | O(1) fast | One-end operations |
| 🚶 Queue | O(n) | O(1) fast | O(1) fast | Two-end operations |
Real-World Uses
List data
Student scores or product price lists
Image processing
Pixel matrix storage
Charts
Data ordered by time
2.1 陣列 vs 鏈結串列
| 對比維度 | 陣列 | 鏈結串列 |
|---|---|---|
| 記憶體佈局 | 連續的一整塊 | 散落各處，用指標串起來 |
| 存取第 n 個 | 直接算地址，O(1) | 從頭一個個找，O(n) |
| 中間插入 | 後面的都要挪，O(n) | 改兩個指標就行，O(1) |
| 大小 | 建立時就固定了 | 隨時可以增長 |
2.2 堆疊和佇列
| 結構 | 規則 | 操作 | 類比 |
|---|---|---|---|
| 堆疊 | 後進先出 (LIFO) | push / pop | 一疊盤子 |
| 佇列 | 先進先出 (FIFO) | enqueue / dequeue | 排隊買票 |
3. 雜湊表：最快的搜尋
Hash Tables: Super-Fast LookupFind data directly through a key
A hash table is like a library index card: instead of searching shelf by shelf, you use the index to find the book location directly.
Store data
Hashing process
Input key
apple
↓
Hash function
hash(key) % 10
↓
Array index
0
Hash table
0
apple: apple
1
Empty
2
Empty
3
Empty
4
Empty
5
Empty
6
orange: orange
7
Empty
8
Empty
9
banana: banana
Performance Comparison
Hash table lookup
O(1)
Found instantly
Array lookup
O(n)
Requires traversal
Binary search
O(log n)
Requires sorted data
Common Uses
User table (user ID → profile)
Shopping cart (product ID → quantity)
Cache system (URL → page content)
Dictionary (word → definition)
3.1 雜湊表的核心思想
- 你給一個鍵（比如 "apple"）
- 雜湊函式把鍵算成一個數字
- 直接到陣列的對應位置找——不用遍歷，一步到位
3.2 雜湊衝突
兩個不同的鍵可能算出同一個索引——這叫雜湊衝突。
3.3 雜湊表的效能
| 操作 | 平均情況 | 最壞情況 |
|---|---|---|
| 搜尋 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 刪除 | O(1) | O(n) |
雜湊表在你的程式碼裡無處不在
- JavaScript 的
{}物件和Map→ 雜湊表 - Python 的
dict→ 雜湊表 - Java 的
HashMap→ 雜湊表
4. 樹形結構：層級關係的表達
Tree Structures: Representing HierarchiesAn organization model like a family tree
Choose a tree type:
Tree Structure Features
Hierarchy
Nodes have one-to-many parent-child relationships
Single root node
Except for the root, each node has exactly one parent
Efficient lookup
Binary search tree lookup is O(log n)
Multiple traversals
Preorder, inorder, postorder, and level-order traversal
Use Cases
File systems
Hierarchical organization of folders and files
HTML DOM
Nested structure of web page elements
Organization charts
Company management hierarchy
Decision trees
Classification algorithms in machine learning
4.1 二元搜尋樹：有序的樹
一個簡單但強大的規則：左小右大。
4.2 平衡樹：防止退化
| 類型 | 平衡策略 | 典型應用 |
|---|---|---|
| AVL 樹 | 嚴格平衡 | 需要頻繁搜尋的場景 |
| 紅黑樹 | 近似平衡 | Java TreeMap、Linux 核心 |
| B 樹 | 多路平衡 | 資料庫索引 |
樹在你的程式碼裡在哪？
- 檔案系統：資料夾巢狀就是樹結構
- HTML DOM：就是一棵樹
- 資料庫索引：B+ 樹讓百萬級資料的搜尋只需要 3-4 次磁碟讀取
- JSON/XML：巢狀的資料格式本質上就是樹
5. 圖結構：複雜關係的網路
Graph Structures: Representing Complex RelationshipsA network of nodes and edges
Graph properties
Vertices (V)
5
Edges (E)
6
Degree
2.4
Use Cases
Map navigation (shortest path)
Social networks (friend relationships)
Web links (PageRank)
Dependencies (package management)
5.1 圖的三種形態
| 類型 | 特點 | 類比 | 典型應用 |
|---|---|---|---|
| 無向圖 | 邊沒有方向 | 微信好友（互相的） | 社交網路 |
| 有向圖 | 邊有方向 | 微博關注（單向的） | 網頁連結 |
| 帶權圖 | 邊有權重 | 城市間的公路（有里程數） | 地圖導航 |
5.2 圖的遍歷
| 遍歷方式 | 策略 | 類比 |
|---|---|---|
| BFS（廣度優先） | 先訪問所有鄰居 | 水波紋擴散 |
| DFS（深度優先） | 一條路走到底 | 走迷宮 |
6. 效能對比：一張表看清所有資料結構
Data Structures: Containers for DataChoose different storage models for different scenarios
ArrayContiguous memory and fast indexed access
010
120
230
340
450
560
670
780
Access arr[2] = O(1), insert/delete = O(n)
Time Complexity Comparison
| Operation | Array | Linked list | Hash table | Tree |
|---|---|---|---|---|
| Access | O(1) | O(n) | O(1) | O(log n) |
| Search | O(n) | O(n) | O(1) | O(log n) |
| Insert | O(n) | O(1) | O(1) | O(log n) |
| Delete | O(n) | O(1) | O(1) | O(log n) |
Core idea:Data structures are containers for data. Different containers have different tradeoffs. Choosing the right data structure can improve program efficiency by orders of magnitude.
| 資料結構 | 存取 | 搜尋 | 插入 | 刪除 | 空間 |
|---|---|---|---|---|---|
| 陣列 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 鏈結串列 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 堆疊/佇列 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 雜湊表 | — | O(1) | O(1) | O(1) | O(n) |
| 二元搜尋樹 | — | O(log n) | O(log n) | O(log n) | O(n) |
| 圖 | — | O(V+E) | O(1) | O(E) | O(V+E) |
7. 選型指南：該用哪種資料結構？
How Do You Choose the Right Data Structure?Make the best choice based on scenario needs
What is your use case?
Fast lookup
Find matching data quickly by key
Preserve order
Data must stay in insertion order or a specific order
Last in, first out
The most recent item is processed first
First in, first out
Earlier items are processed first
Hierarchy
Data has parent-child relationships
Complex relationships
Data has many-to-many connections
Quick Reference
| Scenario need | Recommended structure | Time complexity |
|---|---|---|
| Random access | Array | O(1) |
| Fast lookup | Hash table | O(1) |
| Ordered lookup | Binary search tree | O(log n) |
| Frequent insertion/deletion | Linked list | O(1) |
| Undo operations | Stack | O(1) |
| Task scheduling | Queue | O(1) |
Decision Flow
Need fast element access?
Yes
Array / Hash table
No
Need frequent insertion and deletion?
Yes
Linked list
No
Need to preserve order?
Yes
Stack / Queue
No
Tree / Graph
| 你的需求 | 推薦結構 | 原因 |
|---|---|---|
| 按位置快速存取 | 陣列 | O(1) 隨機存取 |
| 頻繁在中間插入刪除 | 鏈結串列 | O(1) 插入刪除 |
| 後進先出（復原、遞迴） | 堆疊 | LIFO 語義 |
| 先進先出（任務佇列） | 佇列 | FIFO 語義 |
| 按鍵快速搜尋 | 雜湊表 | O(1) 平均搜尋 |
| 有序資料 + 快速搜尋 | 二元搜尋樹 | O(log n) 搜尋且保持有序 |
| 複雜多對多關係 | 圖 | 能表達任意節點間的連線 |
總結
資料結構是程式的骨架。陣列像一排編號置物櫃；鏈結串列像尋寶線索鏈；雜湊表像圖書館索引；樹像家族族譜；圖像捷運路線圖。沒有最好的資料結構，只有最合適的。
延伸閱讀
| 主題 | 推薦資源 |
|---|---|
| 資料結構視覺化 | VisuAlgo |
| 演算法與資料結構 | 《演算法圖解》- Aditya Bhargava |
| 刷題練習 | LeetCode |