数据结构：Python标准库速查

本篇把前五篇收成一张柜台：我要做 X → 用哪个类型。默认解释器 CPython 3.11+。先开标准库，再谈手写节点或第三方。

段末注释：速查对象是 CPython 标准库容器与算法模块，不是「所有曾发明的结构」。红黑树、B+、布隆过滤器不在表内。

---

1. 我要做 X → 用哪个

我要做的事	用这个	不要误用
按下标、追加、扫描	list	头插当队列
固定一组、当键、返回多值	tuple	可变记录用 list
同质 C 标量紧凑存	array.array / NumPy	海量 int 还用 list
字节缓冲	bytearray / bytes / memoryview	用 str 拼二进制
后进先出	list.append / pop	insert(0, …)
先进先出 / 两头进	collections.deque	list.pop(0)
滑动窗口定长	deque(maxlen=k)	每次 list 切片
按键查找、分组、稀疏表	dict	线性扫 list 找键
缺键自动建桶	defaultdict(list/int/set)	满篇 if k not in
计数、Top-K 词频	Counter	手写 dict 再 sorted（(k) 小应用 most_common）
去重、成员测试	set	用 list 做 in
保插入序去重	dict.fromkeys(xs)	依赖 set 顺序
多层覆盖查找	ChainMap	浅拷贝合并大 dict
LRU 缓存函数	functools.lru_cache	手写节点
LRU 缓存键值	OrderedDict	普通 dict 没有 move_to_end
反复取最值	heapq	每次 min(list)
有序数组里折半	bisect	手写 BST 当默认
有序映射且插入勤	sortedcontainers（第三方）	手写红黑树
图（稀疏）	dict → list/dict	(n) 很大还上矩阵
无权最短路	deque BFS	Dijkstra
非负权最短路	heapq	无权也上堆
连通合并	并查集（自写 20 行）	每次 BFS 全图
前缀集合	嵌套 dict Trie	对每个前缀扫全部词
线程间传递	queue.Queue / LifoQueue / PriorityQueue	多线程裸 list/dict

---

2. 复杂度总表（期望 / 均摊）

类型	按下标	头插删	尾插删	按值/in	按键
list	(O(1))	(O(n))	(O(1))	(O(n))	—
deque	(O(n))	(O(1))	(O(1))	(O(n))	—
dict / set	—	—	—	—	(O(1))
heapq（list）	堆顶 (O(1))	—	入/出 (O(\log n))	(O(n))	—
有序 list+bisect	(O(1))	insort (O(n))	—	(O(\log n)) 查找	—

哈希最坏 (O(n))、堆没有按下标改优先级的现成 decrease-key。写题时按这张表估，不要背「链表插入总是更快」。

---

3. 模块入口

模块	拿走什么
内置	list tuple dict set frozenset bytes bytearray memoryview
collections	deque defaultdict Counter OrderedDict ChainMap namedtuple
collections.abc	Mapping Sequence 等接口，给类型检查与 isinstance
array	同质数值数组
heapq	最小堆 API
bisect	折半查找 / 插入
queue	线程安全 FIFO / LIFO / 优先队列
functools	lru_cache、cache
dataclasses	记录类型（不是容器，常与 list/dict 一起用）

namedtuple / dataclass 解决「一条记录有哪些字段」，不解决「一堆记录怎么索引」。索引回到 list/dict。

---

4. 一张最小对照（与总览篇对齐）

教科书名字	Python 落点
动态数组	list
静态数组	tuple；数值紧凑用 array
链表	教学手写；生产 deque 块状链
栈	list
队列 / 双端队列	deque
哈希表 / 映射	dict
哈希集合	set
堆 / 优先队列	heapq；带锁 queue.PriorityQueue
有序映射	无内置；bisect 或 sortedcontainers
图	dict 邻接表
Trie / 并查集 / BST	自写；不要为它们先找框架
LRU	lru_cache / OrderedDict
B+ / 红黑	数据库 / 第三方；进程内默认不碰

---

5. 第三方何时才值得

需求	社区方案	风险
大规模数值矩阵	NumPy	dtype=object 退回指针表
有序 list/dict/set	sortedcontainers	多依赖；不是红黑树常数
图算法电池	NetworkX	大图慢
稀疏矩阵 / 图 CSR	SciPy	接口偏科学计算
布隆过滤	各 pybloom*	假阳性；实现质量不一

原则：标准库常数不可接受，先量再换。不要预装一套「完整数据结构框架」。

---

6. 自检

不看表，回答：

1. 队列、栈、LRU、Top-K、前缀、连通，各一句点名类型。
2. 哪个操作让你立刻否定 list？哪个立刻否定 deque？
3. 为什么 3.7+ 有序的 dict 仍替不了 OrderedDict 做 LRU？

答不全就回到 §1 左列重走一遍。