1.1 什麼是資料結構#
概念說明#
資料結構（data structure） 是組織、儲存資料的方式，目的在於讓特定的操作（查詢、插入、刪除、排序……）能夠有效率地進行。同一批資料可以用不同結構承載，例如全班 30 位同學的成績：
- 放進一條串列：加名單很快，但找某人要從頭翻。
- 放進雜湊表（字典）：用學號查成績一秒命中，但按名次排序列印就得多做工。
- 放進有序的樹：查詢快、按排名範圍列出也快，但實作較複雜。
由此可見，資料結構的選擇取決於「最常執行的是哪一種操作」。這是本書反覆出現的主題。
抽象資料型別（ADT）#
在實作之前，我們常用抽象資料型別描述一個結構「提供哪些操作、遵守哪些規則」，而不先管內部怎麼寫。例如「堆疊」的 ADT 只說：可以 push（放入）、pop（取出最後放入的）、peek（偷看頂端）——至於內部用陣列還是鏈結串列，是實作細節。先定 ADT 再實作，能讓程式碼更容易替換與測試。本書每一章都會先給出該結構的 ADT 契約（介面），再進入實作。
操作與複雜度的觀察#
資料結構的效率，用「各操作的時間複雜度」來衡量。下表是本書即將介紹的幾個主角的速覽（n 為元素個數）：
| 結構 | 查詢 | 插入 | 刪除 | 適合場景 |
|---|---|---|---|---|
| 動態陣列 | O(n) | 攤攤 O(1)（尾端） | O(n) | 按位置存取、走訪 |
| 鏈結串列 | O(n) | O(1)（已知節點） | O(1)（已知節點） | 頻繁頭尾增刪 |
| 雜湊表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | 鍵值查詢 |
| 二元搜尋樹（平衡） | O(log n) | O(log n) | O(log n) | 有序資料 + 範圍查詢 |
| 堆積 | O(1)（看最值） | O(log n) | O(log n)（刪最值） | 優先權排程 |
不必現在記住整張表，只要感受到「查得快的，插入未必快；插得快的，查未必快」——魚與熊掌難以兼得，正是我們需要這麼多結構的原因。
第一個對照實驗#
下面的程式比較「串列線性搜尋」與「集合查詢」在大量資料下的速度差異，直觀感受資料結構帶來的影響：
import random, time
n = 200_000
data = [random.randint(0, n * 10) for _ in range(n)]
targets = [random.choice(data) for _ in range(2000)]
# 結構一：未排序串列，線性搜尋
t = time.perf_counter()
hit = sum(1 for x in targets if x in data) # 每次查詢 O(n)
t_list = time.perf_counter() - t
# 結構二：集合（雜湊表），常數時間查詢
s = set(data)
t = time.perf_counter()
hit2 = sum(1 for x in targets if x in s) # 每次查詢 O(1) 平均
t_set = time.perf_counter() - t
print(f"串列查詢 2000 次：{t_list:.4f} 秒")
print(f"集合查詢 2000 次：{t_set:.6f} 秒")
print(f"速度比：約 {t_list / t_set:.0f} 倍")
同一批資料、同樣的查詢，僅僅換了存放方式，速度就相差幾個數量級。這就是學資料結構的理由。
複雜度分析#
本節沒有新演算法，但請帶走兩個判斷準則：
- 查詢導向的問題優先考慮雜湊表或平衡樹。
- 順序、位置導向的問題優先考慮陣列或串列。
練習#
- 你要寫一個「手機通訊錄」，最常見操作是輸入姓名找電話。你會選串列、雜湊表還是有序陣列？為什麼？
- 承上，若還常需要「按姓名排序印出全部」，你會如何調整或補充儲存方式？
- 執行本節的對照實驗，把 n 改成 20 萬與 200 萬，觀察兩種結構耗時的成長趨勢是否符合 O(n) 與 O(1) 的預測。