list 底层扩容：为什么 append 通常是 O(1)

做的事：一边append，一边追踪list的内存占用

list底层是一个的连续内存数组，理论上每次真的要扩容都要重新分配+搬数据。

代码lst = [] prev_size = sys.getsizeof(lst) for i in range(70): lst.append(i) size = sys.getsizeof(lst) if size != prev_size: print(f"append第{i+1}个元素时: {prev_size} -> {size} 字节") prev_size = size

验证：扩容不是每次append都发生，而且间隔越来越大

记录到的扩容点。

结果append第1个元素时: 56 -> 88 字节 append第5个元素时: 88 -> 120 字节 append第9个元素时: 120 -> 184 字节 append第17个元素时: 184 -> 248 字节 append第25个元素时: 248 -> 312 字节 append第33个元素时: 312 -> 376 字节 append第41个元素时: 376 -> 472 字节 append第53个元素时: 472 -> 568 字节 append第65个元素时: 568 -> 664 字节

的扩容点是1、5、9、17、25、33、41、53、65——间隔是8、8、8、8、8、8、12、12这样越来越大的节奏，不是"每加满就扩容1个位置"。这就是list的"超额分配"策略：每次真的要扩容时，不是刚好分配够当前元素数的空间，而是多分配一截"预留空间"，后面接着append时，只要还在这截预留空间内，就不需要再申请新内存、搬数据。

验证：append比insert(0,x)快了608倍

append在尾部操作，insert(0,x)在头部操作，同样10万次。

结果append 100000次(尾部): 耗时 0.0039s insert(0,x) 100000次(头部): 耗时 2.3716s

append之所以"通常是O(1)"，原因就是上面的超额分配——大多数时候append不需要扩容，直接把新元素放进预留空间就行，均摊下来代价很小。insert(0,x) 则完全不同：在数组头部插入，要把后面所有元素都往后挪一位，元素越多，每次insert(0,x)要搬的数据就越多——这是的O(n)操作，10万次insert(0,x)累积成了O(n²)的总代价，比append慢了608倍。

分步演示：append为什么快，insert(0,x)为什么慢

每一步都是本文上面用Python 3.14跑出来的原始结果。