Python列表底层是动态指针数组，含引用计数与过量分配机制；append()平摊O(1)因扩容按new_allocated = (size >> 3) + (size < 9 ? 3 : 6)增长，单次可能触发O(n)重分配。
Python 列表不是“可变数组”的简单翻译，它的底层是动态指针数组 + 引用计数 + 过量分配（over-allocation）机制。直接操作 list 时，你其实一直在和这套内存管理策略打交道。
为什么 append() 平摊时间复杂度是 O(1)，但单次可能触发 O(n) 重分配？
CPython 的 list 在扩容时，并非每次只加 1 个槽位，而是按公式 new_allocated = (size >> 3) + (size 增长（见 <a href="https://www.php.cn/link/4b7dc121caf2baf0963a047346fc8df6">listobject.c</a>）。这意味着：
- 小列表（如长度
- 大列表（如长度 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) 移。
立即学习“Python免费学习笔记（深入）”；
用 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 压力。
