Python列表系统学习路线第242讲_核心原理与实战案例详解【技巧】

Python列表底层是动态指针数组，含引用计数与过量分配机制；append()平摊O(1)因扩容按new_allocated = (size >> 3) + (size

Python 列表不是“可变数组”的简单翻译，它的底层是动态指针数组 + 引用计数 + 过量分配（over-allocation）机制。直接操作 list 时，你其实一直在和这套内存管理策略打交道。

为什么 append() 平摊时间复杂度是 O(1)，但单次可能触发 O(n) 重分配？

CPython 的 list 在扩容时，并非每次只加 1 个槽位，而是按公式 new_allocated = (size >> 3) + (size 增长（见 listobject.c）。这意味着：

小列表（如长度

大列表（如长度 1000）再 append()，可能新增约 125 个空位

真正耗时的是 memcpy 整块复制旧数据到新地址——这步不可省略，且发生在扩容瞬间

所以连续调用 1000 次 append()，实际只重分配约 10–15 次，平摊下来接近常数

del lst[i] 和 lst.pop() 的性能差异远不止“删尾 vs 删中”

删除末尾元素（pop()）只需将 ob_size 减 1；而删除中间或开头元素（del lst[i]）必须把 i+1 到末尾的所有指针向前挪一位——这是纯 C 级别的内存移动：
import timeit
lst = list(range(100000))
timeit.timeit(lambda: lst.pop(), number=100000)        # ≈ 0.012s
timeit.timeit(lambda: del lst[0], number=100000)       # SyntaxError —— 正确写法是：
timeit.timeit(lambda: lst.__delitem__(0), number=100000)  # ≈ 2.8s（慢 200 倍以上）
更隐蔽的坑：lst.remove(x) 先遍历找索引，再执行 __delitem__，等价于 O(n) 查 + O(n) 移。

用 list.extend() 替代循环 append() 不只是为了“写得短”

假设你要合并两个列表：

for x in other: target.append(x) → 每次 append 都可能触发检查、扩容、复制

target.extend(other) → C 层直接预估总长度，一次分配到位，再批量 memcpy

若 other 是生成器（如 range(10**6)），extend 仍能高效处理；而循环 append 会因反复扩容严重拖慢

实测：向空列表添加 100 万个整数，extend(range(10**6)) 比循环 append 快 3–5 倍。

别依赖 id(lst) 不变来判断“列表没重建”，它掩盖了真实风险

看似安全的操作，比如：
lst = [1, 2, 3]
original_id = id(lst)
lst += [4, 5]  # 原地修改，id 不变
lst *= 2       # 原地修改，id 不变
lst = lst + [6]  # 创建新对象！id 已变
问题在于：+= 和 *= 对 list 是就地操作（调用 list_inplace_concat），但 + 和 * 总是新建对象。如果你在函数外持有原列表引用，又误用 + 赋值，就可能引发静默的引用失效。

真正需要关注的不是 id，而是是否触发了底层 realloc 或指针复制——这些对上层透明，但影响缓存局部性和 GC 压力。