北京
用Python写代码的人，几乎每天都在和列表打交道。但你可能没意识到，这个看似简单的数据结构，藏着一套精密的"自适应容量"机制——它让尾部操作快到飞起，却让头部操作慢如蜗牛。
这背后的秘密，藏在CPython源码的Objects/listobject.c文件里。
Python列表本质上是一个动态数组。当你调用append()、pop()或insert()时，列表长度发生变化。一旦长度超过底层数组的容量，就必须扩容；反之，当长度远低于容量时，则会缩容。所有这些长度变更操作，都要经过同一个核心函数：list_resize()。
这个函数的扩容策略很有意思。它不会精确分配刚好够用的空间，而是故意"多给一点"——新容量等于新长度加上新长度的1/8，再根据大小额外加3或6个槽位。公式写出来是：
new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)
为什么要加这个固定冗余？因为当列表长度小于8时，右移3位的1/8冗余会直接变成0。如果没有额外的3或6个槽位，一个从0开始增长的列表，几乎每次append()都要触发重新分配内存，性能将惨不忍睹。
这套机制产生的实际容量序列是：0、4、4、4、4、8、8、8、8、16、25、35、46……前期跳得快，后期增长放缓，整体呈线性摊还特性。
更关键的是触发条件。list_resize()会在两种情况下真正调用realloc()：一是新长度超过当前容量（必须扩容），二是新长度不到当前容量的一半（考虑缩容）。如果新长度落在"容量的一半到容量之间"这个区间，无论怎么操作，都不动底层数组——这正是尾部操作极快的根本原因。
append()和pop()都发生在列表末尾，绝大多数情况下不会触发内存重分配，时间复杂度是O(1)。但insert(0, x)或pop(0)就惨了：它们需要把现有元素整体搬家，本身已经是O(n)操作，如果还碰巧触发扩容或缩容，代价更高。
源码里还藏着一个细节：当新长度为0时，容量会被强制设为0，彻底释放内存。这是Python列表唯一会完全"归零"的时刻。
这套设计在2001年左右就基本定型，至今仍是CPython的核心机制。它解释了为什么Python教程总劝你"尽量在尾部操作"——这不是风格问题，是实打实的性能鸿沟。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
