14-列表操作的时间复杂度真相-pop-insert-remove为什么有的慢有的快

列表操作的时间复杂度真相：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 ~> 列表操作复杂度速查表——贴在最前面

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 数组结构决定：

1. 尾部操作（append、pop）→ O(1)—— 不需要移动现有元素，改指针就行。
2. 随机访问lst[i]→ O(1)—— 直接算地址：基地址 + i × 指针宽度。
3. 头部/中间操作（insert(0)、pop(0)、remove）→ O(n)—— 需要移动大量元素。
4. 需要频繁头部/中间操作的场景 → 用collections.deque，或考虑非顺序容器（set/dict）。

结尾

列表复杂度分析到此结束。感谢阅读！

源码骑士 — 源码级拆解，从底层看透技术

👀关注：跟博主一起从源码视角深耕底层原理

❤️点赞：让优质内容被更多人看见

⭐收藏：核心知识点存好，随用随查

💬评论：分享你的经验或疑问，一起交流

🔄一键四连：别忘了给博主一键四连！

🗡️寄语：知道复杂度在手，容器选择有方向。

结语：列表是 C 数组——头部慢、尾部快、随机访问快。下篇进入 copy 模块——浅拷贝和深拷贝在 C 层面究竟差在哪。一键四连！