Python列表底层是动态数组而非链表，支持O(1)索引访问和len()查询，但头插/头删为O(n)；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 且<code>allocated > 50时触发，防止“抖动”
为什么append比insert快得多
list.append()只在数组末尾写入，只要容量够就纯O(1)；而list.insert(i, x)必须把索引i及之后所有元素整体后移一位，最坏情况（i=0）要搬动全部元素。
使用场景：高频追加用append；需要头插/中间插时，优先考虑collections.deque（双端队列，头插O(1)）。
立即学习“Python免费学习笔记（深入）”；
-
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 放在循环里，以为<code>len()有开销，其实完全没必要缓存——它就是一次整数读取。
-
len()对应CPython里的list_len函数，一行returnPy_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；而“数组”意味着连续性——这点一旦被忽略，比如当成链表来设计算法，性能问题就很难靠后期优化补救。
