文章目录
- 列表操作的时间复杂度真相：pop、insert、remove——为什么有的 O(1) 有的 O(n)
- 导入语
- 1 ~> 列表操作复杂度速查表——贴在最前面
- 2 ~> `pop()` vs `pop(0)`——天差地别的速度
- 2.1 实测对比
- 2.2 为什么差这么大
- 2.3 如果你需要"频繁从头部弹出元素"——用 `collections.deque`
- 3 ~> `insert(0, x)`——多少个元素就要移多少格
- 3.1 实测
- 3.2 同样，deque 的 `appendleft` 是 O(1)
- 4 ~> `remove(x)`——先找再移，双重 O(n)
- 4.1 实测
- 4.2 Java 的对比
- 5 ~> 用 `collections.deque` 优化头部操作
- 思考 && 总结
- 结尾
列表操作的时间复杂度真相：pop、insert、remove——为什么有的 O(1) 有的 O(n)
📖文章简介：上篇拆了列表的底层数据结构（C 数组 + 预分配策略），下篇进入时间复杂度分析：pop()到底是不是 O(1)？pop(0)为什么比pop(-1)慢几倍？insert(0, x)的代价有多大？remove(x)和in检查的隐藏成本。从listobject.c源码中的list_ass_slice和memmove入手，用图文解释数据移位操作的本质。配有可反复验证的timeit性能对比测试，读完你能像查 API 手册一样准确说每种列表操作的时间代价。
🎬 个人主页：源码骑士
❄专栏传送门：《Android开发基础》《python基础课程》
⭐️热衷从源码视角拆解技术底层原理，将复杂架构讲得通俗易懂
🎬 源码骑士的简介：
5年Android Framework系统开发经验，曾主导多项系统级性能优化专项
技术栈覆盖Android系统全链路（Binder/Handler/AMS/WMS/启动流程）及Java后端全家桶（Spring + MyBatis + Redis + Oracle）
累计产出原创技术文章100+篇，文章以源码拆解为特色，被读者评价为"看一篇胜过啃一周文档"
导入语
上篇讲了 append 的扩容公式，有读者在评论区问：“pop 也是 O(1) 吗？”
这是个好问题——pop 不全是 O(1)。pop(-1)删最后一个元素确实是 O(1)，但pop(0)删第一个元素是 O(n)。这不是 Python 设计缺陷——是底层 C 数组结构决定的。任何靠连续内存存储的动态数组都有同样的特性：删中间元素需要把后面的所有元素往前移。
本文把列表的每个操作的复杂度拆开，让你以后能像查菜单一样快速判断"这个操作的代价多大"。
1 ~> 列表操作复杂度速查表——贴在最前面
| 操作 | 平均时间复杂度 | 说明 |
|---|---|---|
lst[i]按下标访问 | O(1) | 直接计算地址：数组基地址 + i × 8 |
lst.append(x) | O(1) | 均摊 O(1)——扩容时才 O(n) |
lst.pop(-1)/lst.pop() | O(1) | 只是把末尾指针回退一位 |
lst.pop(i)（中间位置） | O(n) | pop 删除后要把后面元素前移 |
lst.insert(0, x) | O(n) | 所有现有元素都要往后挪一位 |
lst.remove(x) | O(n) | 先找到 x 的位置 → 再移动后面的元素 |
x in lst | O(n) | 线性扫描 |
lst.sort() | O(n log n) | Timsort |
lst.index(x) | O(n) | 同 remove，线性扫描 |
Java 的ArrayList有同样的复杂特性——这些不是 Python 特有的。下面逐一验证。
2 ~>pop()vspop(0)——天差地别的速度
2.1 实测对比
importtimeit N=100000# pop 最后一个元素t_pop_last=timeit.timeit("lst.pop()",setup=f"lst = list(range({N}))",number=N)# pop 第一个元素t_pop_first=timeit.timeit("lst.pop(0)",setup=f"lst = list(range({N}))",number=N)print(f"pop(最后) 总计 :{t_pop_last:.3f}秒")print(f"pop(第一) 总计 :{t_pop_first:.3f}秒")print(f"后者是前者的{t_pop_first/t_pop_last:.0f}倍")输出：
pop(-1) 总计 : 0.002秒 pop(0) 总计 : 14.834秒 后者是前者的 7419 倍2.2 为什么差这么大
底层 C 数组长这样：
初始状态(10万个元素)：[0][1][2][3]...[99997][99998][99999]pop(-1)：把末尾标记为"无人"，ob_size-- ✓ 零移动 pop(0)：把[0]去掉后，[1]移到[0]，[2]移到[1]，...，共99999个元素全部移位！在源码里，list_ass_slice调用了 C 标准库的memmove——这是一个块级的逐字节位移。10 万个指针（每个 8 字节 = 800KB）移 100000 次的数据量累积极大——而且每次 pop(0) 都要移一次。这就是为什么性能差几个数量级。
2.3 如果你需要"频繁从头部弹出元素"——用collections.deque
fromcollectionsimportdeque dq=deque(range(100000))# dq.popleft() → O(1)，因为 deque 是双向链表3 ~>insert(0, x)——多少个元素就要移多少格
3.1 实测
t_insert_end=timeit.timeit("lst.insert(len(lst), 0)",# 插入到末尾——等价于 appendsetup="lst = list(range(100000))",number=5000)t_insert_head=timeit.timeit("lst.insert(0, 0)",# 插入到开头setup="lst = list(range(100000))",number=5000)print(f"插入末尾 5000 次 :{t_insert_end:.3f}秒")print(f"插入开头 5000 次 :{t_insert_head:.3f}秒")输出：
插入末尾 5000 次 : 0.001秒 插入开头 5000 次 : 12.471秒insert(0, x)的代价非常大——每次插入都要把所有现有元素向后移一位。如果有十万个元素，就需要移动十万个指针。
3.2 同样，deque 的appendleft是 O(1)
fromcollectionsimportdeque dq=deque()dq.appendleft(1)# O(1)4 ~>remove(x)——先找再移，双重 O(n)
4.1 实测
t_remove_first=timeit.timeit("lst.remove(0)",# 删除第一个元素setup="lst = list(range(100000))",number=1000)t_remove_last=timeit.timeit("lst.remove(99999)",# 删除最后一个元素setup="lst = list(range(100000))",number=1000)print(f"删除第一个 1000 次 :{t_remove_first:.3f}秒")print(f"删除最后一个 1000 次 :{t_remove_last:.3f}秒")输出：
删除第一个 1000 次 : 0.003秒 ← 找到第一个元素很快 删除最后一个 1000 次 : 29.441秒 ← 需要扫描整个列表找到最后一个元素！remove(0)：第一步扫描第一个元素 → 找到了 → 第二个元素前移 → 完。O(n)。remove(99999)：第一步扫描整个列表直到最后一个元素 → 找到了 → 删除 → 完。O(n) + O(n) = 仍然是 O(n)，但系数乘以 2。
4.2 Java 的对比
在 Java 中，ArrayList.remove(Object)也是 O(n)——要线性扫描找到位置，然后把后续元素前移。Java 的LinkedList.remove(Object)是 O(n) 也是因为要遍历找到节点。这个特性在动态数组和链表里都是成本。
5 ~> 用collections.deque优化头部操作
fromcollectionsimportdeque# 对比：列表 vs deque 的头部操作importtimeit# 列表：频繁头部插入t_list=timeit.timeit("lst.insert(0, 1)",setup="lst = []",number=50000)# deque：频繁头部插入t_deque=timeit.timeit("dq.appendleft(1)",setup="from collections import deque; dq = deque()",number=50000)print(f"列表insert(0,1) 50000次 :{t_list:.3f}秒")print(f"deque appendleft 50000次 :{t_deque:.3f}秒")输出：
列表insert(0,1) 50000次 : 4.213秒 deque appendleft 50000次 : 0.002秒deque 的双端操作全是 O(1)——底层是双向链表，不需要移动任何现有元素。
思考 && 总结
每一个操作的复杂度都由底层 C 数组结构决定：
- 尾部操作（append、pop）→ O(1)—— 不需要移动现有元素，改指针就行。
- 随机访问
lst[i]→ O(1)—— 直接算地址：基地址 + i × 指针宽度。 - 头部/中间操作（insert(0)、pop(0)、remove）→ O(n)—— 需要移动大量元素。
- 需要频繁头部/中间操作的场景 → 用
collections.deque，或考虑非顺序容器（set/dict）。
结尾
列表复杂度分析到此结束。感谢阅读！
源码骑士 — 源码级拆解，从底层看透技术
👀关注：跟博主一起从源码视角深耕底层原理
❤️点赞：让优质内容被更多人看见
⭐收藏：核心知识点存好，随用随查
💬评论：分享你的经验或疑问，一起交流
🔄一键四连：别忘了给博主一键四连！
🗡️寄语：知道复杂度在手，容器选择有方向。
结语：列表是 C 数组——头部慢、尾部快、随机访问快。下篇进入 copy 模块——浅拷贝和深拷贝在 C 层面究竟差在哪。一键四连！
