Python 与数据结构
数据结构课讲抽象数据类型；Python 把它们做成了内置对象。会用
list、dict只是第一步，知道它们背后分别是动态数组、紧凑哈希表、块状链表和二叉堆，才能解释「为什么尾部追加快、头部插入慢」「为什么 dict 有序」「为什么 set 去重快」。
1. 一张总表
| 抽象数据结构 | Python 载体 | 底层实现 | 关键复杂度 | 典型场景 |
|---|---|---|---|---|
| 动态数组 | list | PyListObject + 连续的 PyObject* 数组 | 索引 O(1)，尾部追加均摊 O(1)，中间插入/删除 O(n) | 结果集、栈、DP 数组 |
| 定长序列 | tuple、namedtuple | PyTupleObject，创建后长度固定 | 索引 O(1)，不可变 | 坐标、返回值、字典键 |
| 哈希表 | dict | 紧凑哈希表：稀疏 indices + 密集 entries | 查找/插入/删除平均 O(1) | 配置、缓存、计数 |
| 哈希集合 | set、frozenset | 开放寻址哈希表，只存键 | 成员判断平均 O(1) | 去重、集合运算 |
| 双端队列 | collections.deque | 固定大小块组成的双向链表 | 两端增删 O(1)，中间索引 O(n) | BFS、滑动窗口 |
| 优先队列 | heapq + list | 0-based 二叉堆（数组存储） | 堆顶 O(1)，push/pop O(log n)，heapify O(n) | Top K、Dijkstra |
| 链表 | 自定义 Node | 对象 + next 引用 | 已知位置插入 O(1)，查找 O(n) | LRU、链表类题目 |
| 树 / 图 | 自定义 Node、dict[list] | 对象引用 / 邻接表 | 取决于遍历方式 | 文件树、依赖图 |
| 并查集 | list / dict 存 parent | 数组 + 路径压缩 + 按秩合并 | 近似 O(1) | 连通性、账户合并 |
两个常被忽略的事实：
- Python 没有内置链表和树，因为「对象 + 引用」就能拼出来；但
deque内部确实是链式结构，只是它按块组织，不是教科书里的单节点链表。 dict、set的 O(1) 是平均复杂度，遇到严重哈希冲突会退化；list的 O(1) 索引则依赖「连续存放引用」这个前提。
2. list：动态数组
2.1 内存布局
CPython 的 list 不是「一串元素」，而是「一个对象头 + 一个指向指针数组的入口」：
PyListObject
ob_refcnt 引用计数
ob_type 类型指针
ob_size = 3 实际元素个数
allocated = 4 已分配的槽位数
ob_item ────────► [ PyObject* ][ PyObject* ][ PyObject* ][ 空闲 ]
│ │ │
▼ ▼ ▼
int 1 int 2 int 3
每个槽位放的是 PyObject*，不是元素本身。所以 [1, "a", [2]] 合法：三个槽位指向三个类型完全不同的对象。连续的是引用，不是对象。
import sys
a = [1, 2, 3]
print(sys.getsizeof(a)) # 本机 3.13：88 = 40 字节 PyListObject + 16 字节 GC 头 + 4 槽 × 8 字节
print(id(a)) # 140...，就是 PyListObject 的地址
a.append(4)
print(id(a)) # 不变：原地扩容，对象没有搬家
2.2 为什么尾部快、头部慢
append() 发现容量够，就直接写下一个槽位；容量不够，才按比例申请更大的数组，把旧引用搬过去。按比例扩容让 n 次追加的总搬移量保持在 O(n)，所以均摊 O(1)，但单次触发扩容仍可能是 O(n)。
pop(0)、insert(0, x) 则不同：它们要把后面所有引用依次左移或右移，n 个元素就是 O(n)。这就是「用 list 当队列」会慢的原因。
# 栈：尾部进、尾部出，都是 O(1)
stack = []
stack.append(1)
stack.pop()
# 队列：不要这样写，pop(0) 是 O(n)
queue = []
queue.append(1)
queue.pop(0) # 后面所有元素都要往前挪
2.3 切片与浅拷贝
切片 a[:] 会创建一个新的外层 list，但只复制引用，不复制引用指向的对象：
a = [[1], [2]]
b = a[:]
b.append([3]) # 只影响 b
b[0].append(99) # a[0] 也变了：b[0] 和 a[0] 是同一个列表
二维列表初始化是同一个坑：
# 错误：三行指向同一个内层列表
matrix = [[0] * 3] * 3
matrix[0][0] = 1
print(matrix) # [[1,0,0], [1,0,0], [1,0,0]]
# 正确：每一行独立创建
matrix = [[0] * 3 for _ in range(3)]
3. dict 与 set：哈希表
3.1 dict 的紧凑布局
Python 3.6 起，dict 把「索引」和「真正的键值条目」分开存：
dk_indices（稀疏）: [ 1, -1, 0, -1, 2, -1, -1, -1 ]
│ │
▼ ▼
dk_entries（密集）: [ (hash, key, value), (hash, key, value), ... ]
indices只存「槽位 → entries 下标」，空槽是-1。entries按插入顺序追加，所以遍历dict得到的就是插入顺序。- 删除只把
indices标记为DUMMY、把 entry 的 key/value 置空；entry 槽位不会立刻复用，删除也不会自动收缩。只有扩容或显式重建dict时才压缩。
这解释了三个常见现象：
dict在 3.7+ 保证插入顺序，但它不是排序，只是记住你插入的先后。dict的内存比「每个键值对单独一个节点」的链表实现更紧凑。- 频繁删除大量键后，表可能变得稀疏，重新构建一个
dict有时反而更省内存。
set的布局和dict不同。set不是「去掉 value 的紧凑 dict」；CPython 的PySetObject用一张setentry表，每项存key + hash，配合used/fill/mask做开放寻址，没有dict的indices + entries分离。它只存键，迭代顺序由哈希决定，不保证顺序；frozenset不可变、可哈希，可以做dict的键。
3.2 哈希与相等
dict/set 的键必须满足：
- 可哈希：
hash(obj)在生命周期内稳定； - 可比较：
__eq__能判断两个键是否相等； - 二者一致：
a == b时必须有hash(a) == hash(b)。
print(hash(1) == hash(1.0) == hash(True)) # True
d = {1: "a", 1.0: "b", True: "c"}
print(d) # {1: 'c'}，三个键被当成同一个
list、dict、set 本身不可哈希，不能做 dict 的键；tuple 只有在所有元素都可哈希时才可哈希。自定义对象默认按 id() 哈希，一旦重写 __eq__ 而没有重写 __hash__，就会变成不可哈希。
3.3 冲突与退化
哈希冲突用开放寻址处理：算出一个槽位，被占了就按扰动序列继续找。装载因子过高时扩容并重新散列。平均 O(1) 的前提是哈希函数把键分散得足够均匀；如果所有键都落到同一个槽，查找就退化成 O(n)。
3.4 遍历时不要改容器
d = {"a": 1, "b": 2}
for k in d:
del d[k] # RuntimeError: dictionary changed size during iteration
需要删除时先复制一份键：
for k in list(d):
if k == "a":
del d[k]
3.5 应用开发中的高频用法
from collections import Counter, defaultdict
# 计数
cnt = Counter("abracadabra")
print(cnt.most_common(2)) # [('a', 5), ('b', 2)]
# 分组
groups = defaultdict(list)
for word in ["apple", "avocado", "banana"]:
groups[word[0]].append(word)
# 去重且保序
seen = set()
unique = [x for x in [3, 1, 3, 2, 1] if not (x in seen or seen.add(x))]
# LRU：OrderedDict 的 move_to_end + popitem(last=False)
from collections import OrderedDict
cache = OrderedDict()
cache["a"] = 1
cache.move_to_end("a")
cache.popitem(last=False) # 淘汰最久未使用
4. deque：块状双向链表
deque 不是「每个元素一个节点」的纯链表，而是「固定大小的块 + 块之间双向链接」：
block <──> block <──> block
[64 个槽] [64 个槽] [64 个槽]
- 两端
append/appendleft/pop/popleft都是 O(1)； - 中间插入、按下标访问是 O(n)，因为要先走到对应块；
maxlen让它在满时自动从另一端淘汰；底层仍是块状双向链表，不是环形缓冲区。
from collections import deque
q = deque([1, 2, 3], maxlen=3)
q.append(4) # 1 被自动挤掉
print(q) # deque([2, 3, 4], maxlen=3)
q.popleft() # O(1)
应用：
- BFS 的待访问队列；
- 滑动窗口最大值（单调递减
deque）； - 单机生产者-消费者（多线程用
queue.Queue，它内部就是deque+ 条件变量）。
注意：deque 不支持切片；d[500] 这种中间索引是 O(n)；转成 list 会复制一份。
5. heapq：数组里的二叉堆
heapq 不提供独立的堆对象，而是直接操作一个 list，把它维护成 0-based 的完全二叉树：
索引: 0
/ \
1 2
/ \ / \
3 4 5 6
父 → 子：left = 2*i + 1, right = 2*i + 2
子 → 父：parent = (i - 1) // 2
heapify(a)：原地建堆，O(n)；heappush/heappop：O(log n)；heappushpop(h, x)：先 push 再 pop，返回最小值；空堆也可用；heapreplace(h, x)：先 pop 再 push，返回最小值；堆不能为空，否则IndexError；nlargest(k, it)/nsmallest(k, it)：O(n log k)。
import heapq
# Top K：比 sorted 全排序更省
nums = [5, 1, 9, 3, 7]
print(heapq.nlargest(2, nums)) # [9, 7]
# 大顶堆：Python 只有小顶堆，取负模拟
max_heap = []
for x in [5, 1, 9]:
heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap)) # 9
# 多键排序：元组按元素依次比较
heap = []
heapq.heappush(heap, (2, "b"))
heapq.heappush(heap, (1, "a"))
print(heapq.heappop(heap)) # (1, 'a')
两个坑：
- 堆只保证堆顶最小，不保证整个列表有序。需要完整顺序时用
sorted。 - 元组里如果有不可比较的对象，会抛
TypeError；常用「计数器」做第二键，避免比较业务对象。
6. 选型决策
需要按 key 快速查找？ → dict
需要去重 / 交并差？ → set / frozenset
需要两端增删？ → deque
需要每次取最小 / 最大？ → heapq
需要按下标随机访问、尾部追加？ → list
需要不可变记录 / 字典键？ → tuple / namedtuple
需要紧凑的数值数组？ → array.array / numpy.ndarray
需要已知节点间的前后关系？ → 自定义 Node
需要连通性合并与查询？ → 并查集（list/dict + 路径压缩）
7. 应用开发中的组合
| 场景 | 组合 | 原因 |
|---|---|---|
| API 请求去重 | set + dict | set 判重 O(1)，dict 存结果 |
| LRU 缓存 | OrderedDict 或 dict + 双向链表 | 命中后移到尾部，淘汰头部 |
| 任务队列（单机） | deque | 两端 O(1)，不需要线程安全 |
| 任务队列（多线程） | queue.Queue | deque + 锁 + 条件变量 |
| Top K / 排行榜 | heapq.nlargest | 只维护 k 个元素，O(n log k) |
| 邻接表 | defaultdict(list) | 稀疏图比二维矩阵省内存 |
| 账户合并 / 连通分量 | 并查集 | 近似 O(1) 合并与查询 |
| 时间序列 | array.array / numpy.ndarray | 连续数值存储，避免每个元素一个对象 |
8. 常见坑
- 可变默认参数：
def f(x, acc=[])的acc只创建一次，多次调用共享同一个列表。 [[0] * n] * m：m 行指向同一个内层列表。- 遍历时修改
dict/set：会抛RuntimeError，先复制键。 - 用
list做dict的键：不可哈希，直接TypeError。 - 在
list里做成员判断：x in list是 O(n)；频繁判断先转set。 - 浅拷贝当深拷贝：
copy()、[:]、list()都只复制第一层。 deque当随机访问数组：中间索引 O(n)，需要下标访问就用list。- 大顶堆忘记取负：
heapq只有小顶堆。
9. 动手实验
import sys
import timeit
import heapq
# 1. list 的内存与扩容
a = []
for i in range(5):
a.append(i)
print(len(a), sys.getsizeof(a))
# 2. 尾部追加 vs 头部插入
print(timeit.timeit("a.append(0)", setup="a=list(range(10000))", number=10000))
print(timeit.timeit("a.insert(0, 0)", setup="a=list(range(10000))", number=10000))
# 3. list 查找 vs set 查找
setup = "a=list(range(10000)); s=set(a)"
print(timeit.timeit("9999 in a", setup=setup, number=10000))
print(timeit.timeit("9999 in s", setup=setup, number=10000))
# 4. heapify 是 O(n)，逐个 push 是 O(n log n)
nums = list(range(10000))
print(timeit.timeit("heapq.heapify(nums)", setup="import heapq; nums=list(range(10000))", number=100))
print(timeit.timeit(
"h=[]\nfor x in nums: heapq.heappush(h, x)",
setup="import heapq; nums=list(range(10000))",
number=100,
))
本机 3.13 的参考结论：
list的append比insert(0, ...)快两三个数量级；set的成员判断比list快几个数量级；heapify比逐个heappush建堆快，因为前者是 O(n)。
10. 小结
list是动态数组：连续的是引用，不是对象；尾部快、头部慢。dict/set是哈希表：平均 O(1) 的前提是哈希均匀；dict记住插入顺序，但不是排序。deque是块状双向链表：两端 O(1)，中间 O(n)。heapq是数组里的二叉堆：只保证堆顶最小，不保证整体有序。- 选型的本质不是背复杂度，而是先问「数据怎么访问、怎么修改」，再找匹配的底层布局。