1.3 Python中的資料結構總覽#

概念說明#

在動手造輪子之前，先盤點 Python 內建的工具箱。了解每個內建結構「底層是什麼、擅長什麼」，日後設計程式時才能選對工具，也才明白本書自製結構與內建結構的對應關係。

內建結構速覽#

結構	語法	底層	特色
list	`[1, 2, 3]`	動態陣列	支援索引、append 攤攤 O(1)
tuple	`(1, 2, 3)`	不可變陣列	可雜湊、能當 dict 鍵
dict	`{'a': 1}`	雜湊表	鍵值查詢平均 O(1)
set	`{1, 2}`	雜湊表	去重、成員測試平均 O(1)
str	`'abc'`	不可變序列	豐富的字串方法
frozenset	`frozenset(...)`	不可變集合	可雜湊

標準函式庫裡還有幾個重要成員：

collections.deque：雙向佇列，兩端增刪 O(1)，底層是區塊串列。
queue.PriorityQueue / heapq：優先權佇列，底層是二元堆積（第7章）。
collections.Counter、defaultdict、OrderedDict：dict 的變形，各針對特殊需求。

各結構的操作成本#

from collections import deque

a = list(range(100_000))
d = deque(a)

# list 開頭插入：O(n)，要搬動所有元素
# deque 開頭插入：O(1)

常用操作的成本（n 為元素數）：

操作	list	deque	dict/set
索引 `a[i]`	O(1)	O(n)	—
尾端增刪	O(1)	O(1)	—
頭端增刪	O(n)	O(1)	—
成員測試 `x in s`	O(n)	O(n)	O(1) 平均
插入/刪除任意鍵	—	—	O(1) 平均

記住兩個易踩的坑：x in list 是線性掃描，大量成員測試應改用 set；list.insert(0, x) 與 list.pop(0) 都是 O(n)，需要雙端操作時應改用 deque。

實測驗證#

import time

n = 100_000

# 實驗一：頭端插入
t = time.perf_counter()
lst = []
for i in range(20_000):
    lst.insert(0, i)
t_list = time.perf_counter() - t

t = time.perf_counter()
dq = deque()
for i in range(20_000):
    dq.appendleft(i)
t_deque = time.perf_counter() - t
print(f"頭端插入 2 萬次：list {t_list:.4f} 秒 / deque {t_deque:.6f} 秒")

# 實驗二：成員測試
lst = list(range(n))
st = set(lst)
t = time.perf_counter()
sum(1 for _ in range(1000) if 99_999 in lst)
t_list = time.perf_counter() - t
t = time.perf_counter()
sum(1 for _ in range(1000) if 99_999 in st)
t_set = time.perf_counter() - t
print(f"成員測試 1000 次：list {t_list:.4f} 秒 / set {t_set:.6f} 秒")

本書結構與 Python 的對應#

本書自製結構與內建工具的關係：

第2章動態陣列、鏈結串列 → 理解 list 與 deque 的原理。
第3章堆疊、佇列 → 其實 list 當堆疊、deque 當佇列即可，但要知道為什麼。
第4章雜湊表 → 揭開 dict 的面紗。
第5、6章樹與平衡樹 → 標準庫沒有內建樹，這正是需要自製的場景。
第7章堆積 → 對應 heapq 模組。

複雜度分析#

本節重點是建立「操作成本表」的直覺。往後章節介紹任何新結構，都會附上一張類似的表格，請練習自己填、自己驗證。

練習#

用 10 萬筆資料實測 x in list 與 x in set，並解釋結果與理論複雜度的關係。
你需要一個「先進先出」的工作佇列，該用 list 還是 deque？說明 list.pop(0) 為何慢。
tuple 為什麼可以當 dict 的鍵而 list 不行？（提示：可雜湊性）