Engineering
Python 資料結構深度解析：不只是背複雜度，而是知道什麼時候該用哪一個
2026-03-04 · — views
寫給已經會寫 Python、但想搞清楚「為什麼選這個」的工程師。
前言：Vibe Coding 時代，你更需要懂資料結構
現在是 Vibe Coding 的時代。Cursor、Copilot、Claude Code 幫你寫完大部分的程式碼，你一個下午就能 ship 一個 MVP。但問題來了——
當 AI 幫你選了 list 來做 queue、用 lru_cache 快取有時效性的行情資料、或者在 hot path 上用 pandas.DataFrame 做逐筆更新的時候，你看得出來這些是不好的選擇嗎？
Vibe Coding 讓你寫得更快，但不代表你可以不懂。恰恰相反，當產出速度變快，你需要更強的判斷力來 review AI 生成的程式碼——尤其是它選的資料結構到底合不合理。 AI 很擅長寫出「能跑」的程式碼，但它不一定會選「最適合你場景」的方案。
這篇文章不是要教你從零學資料結構，而是讓你在看到一段程式碼時，能快速判斷：「這裡的選擇合理嗎？有沒有更好的替代方案？瓶頸可能在哪？」
大部分教學會告訴你 dict 是 O(1) 查詢、list.append() 是 O(1)。但很少人會告訴你：list.pop(0) 是 O(n) 會害死你、deque[i] 其實不是真正的 O(1)、lru_cache 在有時效性的場景下是個地雷。
這篇文章把 Python 常用的資料結構攤開來講，包含底層實作原理、完整的時間與空間複雜度、實務應用場景，以及 LeetCode 上哪些題會用到。
1. list — 動態陣列
底層實作
Python 的 list 是一個指標陣列（array of pointers），每個元素存的是一個指向 PyObject 的指標，不是值本身。底層是一塊連續的記憶體，長度不夠時會自動擴容（大約 1.125 倍）。
這意味著：
list的元素在記憶體中不是連續儲存的（指標連續，但指向的物件散落各處）- 每個元素除了值本身，還有 PyObject header 的 overhead（約 28 bytes per int）
時間複雜度
| 操作 | 複雜度 | 說明 |
|---|---|---|
list[i] | O(1) | 直接用 index 算 offset，極快 |
list.append(x) | amortized O(1) | 偶爾觸發擴容時是 O(n)，但均攤下來是 O(1) |
list.pop() | O(1) | 從尾端移除 |
list.pop(0) | O(n) | 所有元素往前搬一位，這是最常見的效能陷阱 |
list.insert(0, x) | O(n) | 同上，所有元素往後搬 |
list.insert(i, x) | O(n - i) | 搬 i 之後的元素 |
x in list | O(n) | 線性掃描，沒有 hash |
list.sort() | O(n log n) | Timsort，穩定排序 |
list[i:j] | O(j - i) | slice 會建新 list |
list.extend(iterable) | O(k) | k 是 iterable 的長度 |
del list[i] | O(n - i) | 搬 i 之後的元素 |
list.remove(x) | O(n) | 先找到 x，再搬元素 |
len(list) | O(1) | 內部有維護 length 變數 |
空間複雜度
- 每個元素：8 bytes（指標）+ PyObject overhead（int 約 28 bytes）
- 預分配空間：list 會多分配約 12.5% 的空間做 buffer，避免頻繁 resize
sys.getsizeof([])= 56 bytes（空 list 的 overhead）- 實際佔用 ≈ 56 + 8n bytes（不含元素本身），元素本身另計
應用場景
- 適合：需要 random access（
list[i]）、大量尾端操作（append/pop） - 不適合：頻繁頭部操作（insert(0)/pop(0)）、大量
in查詢 - 實務用途：Stack（用 append + pop）、排序後的結果儲存、batch 資料收集
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #20 | Valid Parentheses | 當 Stack 用（append + pop） |
| #155 | Min Stack | 雙 list 模擬 min stack |
| #56 | Merge Intervals | sort 後遍歷合併 |
| #15 | 3Sum | sort + 雙指標 |
| #78 | Subsets | backtracking 收集結果 |
| #739 | Daily Temperatures | Monotonic Stack（list 當 stack） |
注意
# 這是 O(n)，千萬不要在迴圈裡用
for _ in range(n):
list.pop(0) # 每次都搬整個陣列
# 用 deque 取代
from collections import deque
dq = deque(list)
for _ in range(n):
dq.popleft() # O(1)
2. collections.deque — 雙端佇列
底層實作
deque 的底層是一個 doubly-linked list of fixed-size blocks，每個 block 存 64 個元素。不是教科書上的「每個節點一個元素」的 linked list，所以記憶體效率比純 linked list 好很多。
[block0: 64 items] <-> [block1: 64 items] <-> [block2: 64 items]
時間複雜度
| 操作 | 複雜度 | 說明 |
|---|---|---|
dq.append(x) | O(1) | 右端加入 |
dq.appendleft(x) | O(1) | 左端加入 |
dq.pop() | O(1) | 右端移除 |
dq.popleft() | O(1) | 左端移除 |
dq[i] | O(n) | 不是 O(1)！要走過 i//64 個 block |
dq.rotate(k) | O(k) | 旋轉 k 步 |
x in dq | O(n) | 線性掃描 |
len(dq) | O(1) | 內部維護 length |
dq.remove(x) | O(n) | 找到並移除 |
dq.extend(iterable) | O(k) | k 是 iterable 長度 |
空間複雜度
- 每個 block：64 個指標 + linked list 的 prev/next 指標
- 比 list 稍多一點 overhead（因為 block linking），但不需要 resize 時的整塊搬遷
deque(maxlen=N)會自動丟棄超出的元素，記憶體上限固定
應用場景
- 適合：Queue（FIFO）、雙端操作、固定窗口（
maxlen）、BFS - 不適合：頻繁 random access（
dq[i]）、需要 slice 操作 - 實務用途：BFS 的佇列、sliding window 的窗口容器、producer-consumer pattern
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #102 | Binary Tree Level Order Traversal | BFS 佇列 |
| #200 | Number of Islands | BFS 佇列 |
| #239 | Sliding Window Maximum | Monotonic deque（核心題） |
| #862 | Shortest Subarray with Sum at Least K | Monotonic deque |
| #346 | Moving Average from Data Stream | deque(maxlen=N) 完美匹配 |
| #641 | Design Circular Deque | 直接用 deque 實作 |
deque 的隱藏特性
# maxlen：自動維護固定窗口，超出就丟掉最舊的
dq = deque(maxlen=5)
for i in range(10):
dq.append(i)
print(dq) # deque([5, 6, 7, 8, 9], maxlen=5)
# rotate：O(k) 旋轉，某些題目很好用
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2) # 往右轉 2 步 → deque([4, 5, 1, 2, 3])
dq.rotate(-1) # 往左轉 1 步 → deque([5, 1, 2, 3, 4])
3. dict — 雜湊表
底層實作
Python 3.6+ 的 dict 使用 compact dict：
- 一個 indices 陣列（存 hash → entry index 的映射）
- 一個 entries 陣列（按插入順序存放 key-value pair）
這個設計讓 dict 既保持 O(1) 查詢，又保持插入順序（Python 3.7+ 正式保證）。Hash collision 用 open addressing（probing）處理，load factor 超過 2/3 時自動 resize。
時間複雜度
| 操作 | 平均 | 最差 | 說明 |
|---|---|---|---|
d[key] | O(1) | O(n) | 最差情況是所有 key hash 衝突 |
d[key] = val | O(1) | O(n) | 可能觸發 resize |
del d[key] | O(1) | O(n) | |
key in d | O(1) | O(n) | |
d.get(key, default) | O(1) | O(n) | |
d.keys() / d.values() | O(1) | 回傳 view，不是 copy | |
for k in d | O(n) | 遍歷所有 entry | |
len(d) | O(1) | ||
d.pop(key) | O(1) | O(n) | |
d1.update(d2) | O(len(d2)) | ||
{**d1, **d2} | O(len(d1) + len(d2)) | 建新 dict |
空間複雜度
- 空 dict：64 bytes
- 每個 entry：約 50~70 bytes（key hash + key pointer + value pointer）
- Load factor < 2/3，所以至少有 1/3 的空間是浪費的
- Resize 時容量翻倍，瞬間記憶體使用翻倍
int key vs str key 效能差異
hash(42) # → 42（直接回傳自己，幾乎 instant）
hash("AAPL") # → 需要遍歷字串計算 hash（Python 會 cache）
在 hot path 上，int key 的 dict 查詢比 str key 快 20~40%。實務上常見的做法是：建一個 symbol_to_id mapping，之後全程用 int。
應用場景
- 適合：幾乎所有需要快速查詢的場景、計數、分組、快取
- 不適合：需要排序遍歷、key 不是 hashable 的
- 實務用途：counter、lookup table、graph adjacency list、JSON-like 資料
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #1 | Two Sum | hash map 存 complement |
| #49 | Group Anagrams | sorted string 當 key 分組 |
| #128 | Longest Consecutive Sequence | set/dict 查 O(1) |
| #146 | LRU Cache | dict + doubly linked list |
| #560 | Subarray Sum Equals K | prefix sum + dict 計數 |
| #3 | Longest Substring Without Repeating | dict 記錄最後出現位置 |
| #138 | Copy List with Random Pointer | old node → new node mapping |
| #347 | Top K Frequent Elements | dict 計數 + heap |
4. collections.defaultdict — 帶預設值的 dict
底層實作
defaultdict 是 dict 的子類別，唯一的差異是：存取不存在的 key 時，不會丟 KeyError，而是自動呼叫 default_factory 建立預設值並插入。
from collections import defaultdict
dd = defaultdict(list)
dd["a"].append(1) # 不用先 if "a" not in dd: dd["a"] = []
時間 / 空間複雜度
跟 dict 完全相同。唯一的額外成本是：miss 時呼叫一次 default_factory（通常是 list()、int()、set() 等，都是 O(1)）。
常見 default_factory
| Factory | 預設值 | 用途 |
|---|---|---|
int | 0 | 計數器 |
list | [] | 分組收集 |
set | set() | 去重分組 |
lambda: float('inf') | inf | 最短距離初始化 |
應用場景
- 適合：需要頻繁對不存在的 key 做 append/add/increment 的場景
- 陷阱：查詢不存在的 key 會自動插入，可能造成 dict 意外膨脹
dd = defaultdict(int)
val = dd["not_exist"] # 現在 dd 裡多了一個 {"not_exist": 0}
# 如果只是要查，用 dd.get("key", 0) 更安全
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #49 | Group Anagrams | defaultdict(list) 分組 |
| #207 | Course Schedule | defaultdict(list) 建 adjacency list |
| #269 | Alien Dictionary | defaultdict(set) 建 graph |
| #323 | Number of Connected Components | defaultdict(list) 建無向圖 |
| #314 | Binary Tree Vertical Order | defaultdict(list) 按 column 分組 |
5. collections.OrderedDict — 有序字典
底層實作
OrderedDict 內部維護一個 doubly-linked list 來追蹤插入順序。Python 3.7+ 的普通 dict 也保證插入順序，所以 OrderedDict 的存在意義主要是它提供的額外方法：
move_to_end(key, last=True)— 把某個 key 移到頭或尾，O(1)popitem(last=True)— 從頭或尾 pop，O(1)
這兩個方法讓它成為實作 LRU Cache 的理想基礎。
時間複雜度
| 操作 | 複雜度 | 說明 |
|---|---|---|
od[key] | O(1) | 同 dict |
od[key] = val | O(1) | 同 dict |
od.move_to_end(key) | O(1) | OrderedDict 專屬，dict 沒有 |
od.popitem(last=False) | O(1) | 從頭 pop（FIFO），dict 只能 pop 尾 |
del od[key] | O(1) |
空間複雜度
比 dict 多一個 doubly-linked list 的開銷（每個 entry 多兩個指標，約 16 bytes）。
應用場景
- 適合：需要 LRU 淘汰策略、需要
move_to_end的場景 - 不需要用的場景：只需要插入順序遍歷（普通 dict 就夠了）
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #146 | LRU Cache | 經典題，OrderedDict 一步到位 |
| #460 | LFU Cache | 搭配 defaultdict(OrderedDict) |
LRU Cache 的兩種實作
# 方法一：用 OrderedDict（面試推薦，簡潔）
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.cap:
self.cache.popitem(last=False)
# 方法二：dict + doubly-linked list（面試考手刻能力時用）
# 省略，但邏輯是一樣的，只是要自己管 linked list
6. heapq — 堆積（優先佇列）
底層實作
Python 的 heapq 是用 list 實作的 min-heap（最小堆）。heap[0] 永遠是最小元素。底層就是一個普通的 list，透過 index 關係維護 heap property：heap[k] <= heap[2k+1] 且 heap[k] <= heap[2k+2]。
要用 max-heap？把值取負：heappush(h, -val)。
時間複雜度
| 操作 | 複雜度 | 說明 |
|---|---|---|
heapq.heappush(h, x) | O(log n) | 插入 |
heapq.heappop(h) | O(log n) | 彈出最小值 |
h[0] | O(1) | 查看最小值（不彈出） |
heapq.heappushpop(h, x) | O(log n) | push 再 pop，比分開做快 |
heapq.heapify(list) | O(n) | 把既有 list 轉成 heap |
heapq.nlargest(k, iterable) | O(n log k) | |
heapq.nsmallest(k, iterable) | O(n log k) |
空間複雜度
- 就是一個 list，O(n)
- 沒有額外的結構開銷
關鍵限制
- 不支援任意位置刪除 — 這是 heap 最大的弱點。你無法高效地刪除 heap 中間的某個元素。常見 workaround 是 lazy deletion（標記為已刪除，pop 時跳過），但會累積垃圾。
- 不支援 decrease-key — 無法高效更新已在 heap 中的元素的 priority。在 Dijkstra 演算法中，這意味著你只能用「重複 push + lazy deletion」來處理。
- 只有 min-heap — 要 max-heap 就取負值。
應用場景
- 適合：Top-K 問題、合併 K 個有序序列、排程（priority queue）
- 不適合：需要任意刪除的場景（如 order book）、需要遍歷所有元素的場景
- 實務用途：工作排程、Dijkstra、Huffman coding、streaming median
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #215 | Kth Largest Element | min-heap 維護大小 K |
| #23 | Merge k Sorted Lists | heap merge K 個序列 |
| #295 | Find Median from Data Stream | 雙 heap（max-heap + min-heap） |
| #347 | Top K Frequent Elements | dict 計數 + min-heap |
| #743 | Network Delay Time | Dijkstra 的 priority queue |
| #621 | Task Scheduler | max-heap 排程 |
| #973 | K Closest Points to Origin | min-heap / max-heap |
| #378 | Kth Smallest Element in Sorted Matrix | heap merge |
實務 pattern：用 tuple 排序 + sequence number 避免比較問題
import heapq
seq = 0
heap = []
def push(priority, item):
global seq
heapq.heappush(heap, (priority, seq, item))
seq += 1 # 確保相同 priority 時按插入順序排
# 為什麼要 seq？
# 如果兩個 tuple 的第一個元素相同，Python 會比較第二個
# 如果 item 沒有實作 __lt__，會直接報 TypeError
# seq 保證第二個元素永遠不同，避免比較到 item
7. set / frozenset — 集合
底層實作
set 的底層就是一個只有 key 沒有 value 的 hash table，實作方式跟 dict 幾乎一樣（open addressing + probing）。frozenset 是 immutable 版本，可以被 hash，所以可以當 dict 的 key 或放進另一個 set。
時間複雜度
| 操作 | 平均 | 最差 | 說明 |
|---|---|---|---|
x in s | O(1) | O(n) | hash lookup |
s.add(x) | O(1) | O(n) | |
s.remove(x) | O(1) | O(n) | 不存在會丟 KeyError |
s.discard(x) | O(1) | O(n) | 不存在不報錯 |
| `s1 | s2` (union) | O(len(s1) + len(s2)) | |
s1 & s2 (intersection) | O(min(len(s1), len(s2))) | 掃短的那個 | |
s1 - s2 (difference) | O(len(s1)) | ||
s1 ^ s2 (symmetric diff) | O(len(s1) + len(s2)) | ||
s1 <= s2 (subset) | O(len(s1)) |
空間複雜度
- 類似 dict，load factor < 2/3
- 每個元素約 50 bytes（hash + pointer + overhead）
應用場景
- 適合：去重、成員檢查（O(1) vs list 的 O(n)）、集合運算
- 不適合：需要排序、需要 index access
- 實務用途：URL visited 檢查、白名單/黑名單、graph 的 visited set
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #3 | Longest Substring Without Repeating | set 當 sliding window 的字元集 |
| #128 | Longest Consecutive Sequence | set 查 O(1)，避免排序 |
| #36 | Valid Sudoku | set 檢查行 / 列 / 格重複 |
| #139 | Word Break | set 存字典做 O(1) lookup |
| #200 | Number of Islands | visited set 搭配 BFS/DFS |
| #127 | Word Ladder | set 當 word bank + visited |
set vs list 的 in 查詢
# 你以為差不多，其實天差地別
my_list = list(range(100000))
my_set = set(range(100000))
99999 in my_list # O(n)，掃到最後才找到
99999 in my_set # O(1)，hash 一次就找到
# 經驗法則：只要你要做 `in` 查詢超過 10 次，就該用 set
8. namedtuple / dataclass — 結構化記錄
namedtuple
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)
p.x # 1（有名稱，比 tuple[0] 可讀）
底層：就是 tuple 的子類別，immutable。記憶體跟 tuple 一樣小。
| 特性 | 說明 |
|---|---|
| 記憶體 | 很小，跟 tuple 相同 |
| 存取速度 | O(1)，同 tuple |
| Immutable | 是，修改要用 _replace() 建新物件 |
| Hashable | 是，可以當 dict key |
| 型別提示 | 弱（可以用 typing.NamedTuple 改善） |
dataclass
from dataclasses import dataclass
@dataclass
class Position:
symbol: str
quantity: int = 0
pnl: float = 0.0
底層：普通的 class，自動生成 __init__、__repr__、__eq__ 等。加上 slots=True 可以大幅降低記憶體。
| 特性 | dataclass | dataclass(slots=True) |
|---|---|---|
| 記憶體 | 中等（有 __dict__） | 小（接近 C struct） |
| Mutable | 是 | 是 |
| 型別提示 | 完整支援 | 完整支援 |
| IDE 支援 | 好 | 好 |
| 動態加屬性 | 可以 | 不行（這是 trade-off） |
怎麼選？
| 場景 | 選擇 |
|---|---|
| 不需要修改、要放進 set 或當 dict key | namedtuple |
| 需要頻繁修改欄位 | dataclass |
| 需要最小記憶體 + 頻繁修改 | dataclass(slots=True) |
| 只需要打包幾個值回傳 | 普通 tuple 就好 |
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #253 | Meeting Rooms II | namedtuple 存 interval |
| #295 | Find Median from Data Stream | dataclass 封裝 heap 操作 |
| 通用 | Graph node, Trie node | dataclass 定義節點結構 |
9. queue.Queue / asyncio.Queue — 執行緒安全佇列
對比表
| 維度 | deque | queue.Queue | asyncio.Queue |
|---|---|---|---|
| Thread-safe | 否（單一操作 atomic，複合操作不安全） | 是 | 否（single event loop） |
| Blocking get | 不支援 | 支援（q.get(timeout=N)） | 支援（await q.get()） |
| 效能 | 最快 | 慢 5~10x（有 Lock） | 快（但限 async） |
| 適用架構 | 單執行緒 | 多執行緒 | asyncio |
時間複雜度
三者的 enqueue / dequeue 都是 O(1)，差別在常數（lock 的開銷）。
GIL 的 thread-safety 迷思
# deque.append() 和 deque.popleft() 單一操作在 CPython 下是 atomic
# 但複合操作不是：
if len(dq) > 0: # ← GIL 可能在這裡 release
item = dq.popleft() # ← 到這裡 dq 可能已經空了
# 多執行緒下永遠用 queue.Queue
LeetCode 常見用法
queue 模組在 LeetCode 中幾乎不用（因為都是單執行緒），但在系統設計面試中是重要概念。
10. functools.lru_cache — 記憶化快取
底層實作
lru_cache 在內部用一個 dict + circular doubly-linked list 實作 LRU 淘汰。有一個全域 Lock 保證 thread-safety。
@lru_cache(maxsize=128)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
時間複雜度
| 操作 | 複雜度 |
|---|---|
| Cache hit | O(1) |
| Cache miss | O(1)（dict 插入 + LRU 更新） + 原函數執行時間 |
cache_clear() | O(n) |
cache_info() | O(1) |
限制
- 參數必須 hashable — 不能傳 list、dict
- 沒有 TTL — cache 住了就不會過期
- 只能
cache_clear()全部清除 — 不能清單一 entry - 有全域 Lock — 高並發下可能成為瓶頸
maxsize=None— 無限制 cache，記憶體可能爆炸
Python 3.9+：@cache
from functools import cache
@cache # 等同於 @lru_cache(maxsize=None)，更簡潔
def factorial(n):
return n * factorial(n-1) if n else 1
應用場景
- 適合：遞迴 DP（避免重複計算）、純函數的 memoization
- 不適合：有時效性的資料、參數不是 hashable 的
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #70 | Climbing Stairs | 遞迴 + @lru_cache |
| #322 | Coin Change | Top-down DP |
| #1143 | Longest Common Subsequence | Top-down DP |
| #494 | Target Sum | 遞迴搜索 + memo |
| #329 | Longest Increasing Path in Matrix | DFS + @lru_cache |
| #1335 | Minimum Difficulty of a Job Schedule | Top-down DP |
面試技巧
# 面試時用 @lru_cache 把 top-down 遞迴直接變成 DP
# 省去手動建 dp table 的麻煩
@lru_cache(maxsize=None)
def solve(i, j):
if base_case:
return ...
return min(solve(i+1, j), solve(i, j+1)) + cost[i][j]
# 面試官可能會 follow-up：
# 「這個 cache 的空間複雜度是多少？」→ O(n*m)，跟 bottom-up DP table 一樣
# 「如果 n 很大，遞迴深度會不會爆？」→ 會，Python 預設 recursion limit 1000
# 可以 sys.setrecursionlimit()，但 bottom-up 更安全
11. sortedcontainers.SortedList / SortedDict — 排序容器（第三方）
底層實作
sortedcontainers 是純 Python 實作，底層是 list of sorted lists（分段排序）。每個 segment 約 1000 個元素，用 binary search 定位 segment，再在 segment 內做 bisect。
雖然是純 Python，但因為 cache locality 好（連續記憶體），實測經常比 C 擴展的紅黑樹（如 bintrees）還快。
時間複雜度
| 操作 | 複雜度 | 說明 |
|---|---|---|
sl.add(x) | O(log n) | bisect + insert |
sl.discard(x) | O(log n) | bisect + remove |
sl[i] | O(log n) | 需要定位 segment |
sl.bisect_left(x) | O(log n) | 找插入位置 |
x in sl | O(log n) | bisect 查找 |
sl[i:j] | O(log n + j - i) | |
sl.peekitem(0) (SortedDict) | O(log n) | 取最小/最大 key |
空間複雜度
- O(n)，跟普通 list 差不多
- segment 之間有少量 metadata overhead
應用場景
- 適合：需要排序 + 動態插入刪除（order book、即時排行榜）
- 不適合：Python 標準庫不包含，部署時要額外裝套件
LeetCode 常見用法
| 題號 | 題目 | 用法 |
|---|---|---|
| #220 | Contains Duplicate III | SortedList 維護 sliding window |
| #352 | Data Stream as Disjoint Intervals | SortedList 合併區間 |
| #327 | Count of Range Sum | SortedList + bisect 計數 |
| #480 | Sliding Window Median | SortedList 動態維護排序窗口 |
| #715 | Range Module | SortedList 管理區間 |
12. 總整理：速查表
按使用場景選擇
| 需求 | 首選 | 別用 |
|---|---|---|
| Stack (LIFO) | list（append + pop） | deque（overkill） |
| Queue (FIFO) | deque（append + popleft） | list（pop(0) 是 O(n)） |
| 快速查詢 key-value | dict | list（in 是 O(n)） |
| 去重 / 成員檢查 | set | list（in 是 O(n)） |
| 排序 + 動態增刪 | SortedList | list + 反覆 sort |
| Top-K / Priority | heapq | sort 全部再取前 K |
| 遞迴 DP memo | @lru_cache | 手動建 dict（可以但麻煩） |
| LRU Cache | OrderedDict | lru_cache（沒有 TTL） |
| 結構化資料（mutable） | dataclass | dict of dict（沒型別提示） |
| 結構化資料（immutable） | namedtuple | dataclass（如果不需要修改） |
完整複雜度速查
| 結構 | 查詢 | 插入 | 刪除 | 排序遍歷 | 記憶體 |
|---|---|---|---|---|---|
list | O(1) index / O(n) search | O(1) tail / O(n) head | O(1) tail / O(n) head | O(n log n) | 中 |
deque | O(n) | O(1) 兩端 | O(1) 兩端 | 不支援 | 中 |
dict | O(1) | O(1) | O(1) | 不支援 | 大 |
set | O(1) | O(1) | O(1) | 不支援 | 大 |
heapq | O(1) min | O(log n) | O(log n) pop min | 不直接支援 | 小 |
SortedList | O(log n) | O(log n) | O(log n) | O(n) | 中 |
OrderedDict | O(1) | O(1) | O(1) | O(n) 插入序 | 大 |
結語：資料結構的選擇不在於「哪個最快」，而在於你的場景裡哪個操作最頻繁。搞清楚讀寫比例、是否需要排序、是否需要 thread-safety，答案自然就出來了。