Python列表底层是动态数组，CPython中通过PyListObject实现，使用数组结构存储元素，支持动态扩容和缩容。

Python列表看似简单，实则底层是精心设计的动态数组（CPython中由PyListObject实现），凭借连续内存布局实现O(1)索引访问和len()查询，但头插/头删等操作因需整体移动元素而退化为O(n)，大列表上性能断崖式下跌；其智能扩容（按1.125倍增长）与保守缩容（仅当使用量不足容量1/4且容量超50时触发）平衡了空间与时间开销，而append的摊还O(1)与insert(0,x)的纯O(n)形成鲜明对比——理解这一本质，才能避开高频头插等经典陷阱，必要时果断选用deque，真正让代码既简洁又高效。

Python列表底层是动态数组，不是链表

Python的list在CPython中用的是连续内存块实现的动态数组，不是节点指针串联的链表。这意味着list支持O(1)索引访问，但尾部以外的插入/删除是O(n)——因为要移动后续所有元素。

常见错误现象：list.insert(0, x)或list.pop(0)在大列表上明显卡顿；有人误以为list适合高频头插，结果性能崩了。

• 实际存储结构：一个PyListObject结构体，含指向PyObject **数组的指针、当前长度ob_size、已分配容量allocated
• 扩容策略：当ob_size == allocated时，新容量按(size + 1) * 1.125向上取整（有最小增幅兜底），避免频繁 realloc
• 缩容时机：仅在ob_size 且allocated > 50时触发，防止“抖动”

为什么append比insert快得多

list.append()只在数组末尾写入，只要容量够就纯O(1)；而list.insert(i, x)必须把索引i及之后所有元素整体后移一位，最坏情况（i=0）要搬动全部元素。

使用场景：高频追加用append；需要头插/中间插时，优先考虑collections.deque（双端队列，头插O(1)）。

• append平均摊还时间复杂度O(1)，因扩容成本被分摊
• insert(0, x)每次都是O(n)，n越大越慢，10万次头插可能比10万次尾插慢百倍
• CPython源码里list_insert函数会调用memmove搬内存，这是实打实的CPU和缓存开销

len()为什么是O(1)而不是遍历计数

因为list对象自己维护着ob_size字段，len()直接返回它，不扫描数组。

容易踩的坑：有人写while i 放在循环里，以为len()有开销，其实完全没必要缓存——它就是一次整数读取。

• len()对应CPython里的list_len函数，一行return Py_SIZE(self)
• 对比str、tuple、bytes等不可变序列，也都是O(1)，但自定义类若没实现__len__或实现得差，就可能退化
• 注意：len()不等于list.allocated，后者是总容量，前者是当前有效长度

查看实际内存布局：sys.getsizeof和list.__sizeof__

sys.getsizeof([])返回约56字节（空列表基础开销），每多一个元素，只增加8字节（64位系统下指针大小），但不包括元素自身占用的内存。

真实例子：sys.getsizeof([1, 2, 3]) ≈ 80字节，而[1]*1000比[1]*100只多约7200字节（900×8），不是10倍增长——这说明底层确实是紧凑数组，不是每个元素带额外头信息。

• 想看分配容量？CPython未暴露allocated，但可用list.__sizeof__()粗略估算，或用ctypes读内存（不推荐生产环境）
• 注意：小整数、短字符串等会被缓存或内联，sys.getsizeof不反映这部分共享内存
• 真正影响内存的关键是allocated而非len()——比如l = [1]*1000; l.extend([2]*100)后，allocated可能远大于1100

动态数组的“动态”二字藏在扩容缩容逻辑里，不是简单 realloc；而“数组”意味着连续性——这点一旦被忽略，比如当成链表来设计算法，性能问题就很难靠后期优化补救。

终于介绍完啦！小伙伴们，这篇关于《Python列表底层是动态数组，CPython中通过PyListObject实现，使用数组结构存储元素，支持动态扩容和缩容。》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！