python 列表底层是动态数组，支持 o(1) 的随机访问与元素修改，但任意位置的插入/删除为 o(n)；仅在末尾增删时可达 o(1)，因其无需移动其他元素。
python 列表底层是动态数组，支持 o(1) 的随机访问与元素修改，但任意位置的插入/删除为 o(n)；仅在末尾增删时可达 o(1)，因其无需移动其他元素。
Python 中的 list 类型虽常被称作“列表”，但其底层实现并非链表，而是动态数组（dynamic array）——即一段连续分配的内存空间，元素按索引顺序紧邻存储。这一物理结构直接决定了各类操作的时间复杂度特性。
✅ 为什么访问（access）和修改（modify）是 O(1)？
因为数组支持基于偏移量的直接寻址：给定索引 i，内存地址可由公式 base_address + i * element_size 瞬间计算得出，无需遍历。无论 i 是 0、中间值还是 len(lst)-1，耗时恒定。
lst = [10, 20, 30, 40, 50] print(lst[2]) # → 30，O(1) lst[2] = 35 # 修改索引2处元素，O(1)
❌ 为什么任意位置插入/删除是 O(n)？
关键在于内存连续性约束。例如在索引 0 处插入新元素：
- 若底层数组仍有空闲容量，需将原索引
0至n-1的全部n个元素向右平移一位； - 若容量不足，还需重新分配更大内存块，并整体复制所有元素。
同理，删除索引 0 的元素后，需将后续 n-1 个元素全部左移一位以填补空缺。
lst = [10, 20, 30, 40, 50] lst.insert(0, 5) # O(n)：所有元素右移 → [5, 10, 20, 30, 40, 50] lst.pop(0) # O(n)：所有元素左移 → [10, 20, 30, 40, 50]
⚠️ 注意：Big O 描述的是最坏情况下的渐进上界。虽然
insert(i)在i == len(lst)（即末尾）时实际为 O(1)，但通用分析取最差情形i == 0，故标为 O(n)。
✅ 末尾操作为何是 O(1)？
-
append()：若剩余容量足够，直接写入末尾空位；即使触发扩容（如从 64→128），摊还分析（amortized analysis）仍为 O(1)。 -
pop()（无参数）：直接移除并返回最后一个元素，不涉及任何移动。
lst.append(60) # 摊还 O(1) lst.pop() # O(1)
? 总结建议
- 频繁随机读写？✅ 用
list（O(1) 访问/修改）； - 频繁首/中插删？❌ 避免
list.insert(i, x)/list.pop(i)（O(n)）；可考虑collections.deque（双端队列，首尾 O(1)）或重构算法避免中间修改； - 关注实际场景：若只操作末尾，
list是高效且简洁的选择。
理解底层内存模型，是写出高性能 Python 代码的关键一步。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
