list.append()与insert()时间复杂度对比详解

从现在开始，我们要努力学习啦！今天我给大家带来《list.append() 和 insert() 时间复杂度对比分析》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

list.append() 是 O(1) 均摊时间复杂度，因在末尾添加且底层动态数组预留空间；list.insert(i, x) 是 O(n)，因需移动索引 i 后所有元素，越靠前插入越慢。

Python 中 list.append() 是 O(1) 均摊时间复杂度，而 list.insert(i, x) 是 O(n) 时间复杂度——关键区别在于操作位置和底层内存行为。

append() 为什么快：在末尾追加，通常无需移动元素

append() 总是在列表末尾添加元素。CPython 的 list 实现背后是动态数组，内部预留了额外空间（over-allocation）。只要还有空位，就直接写入，不需要搬动已有数据。即使偶尔触发扩容（如从容量 128 扩到 256），也是复制一次全部元素，但这种开销被分摊到多次 append 上，所以均摊仍是 O(1)。

• 典型场景：循环收集结果、构建列表、栈式 push
• 注意：不是严格 O(1)，但实践中极稳定，可视为常数级

insert() 为什么慢：可能需要整体平移元素

insert(i, x) 把元素插入索引 i 处。这意味着从位置 i 开始的所有后续元素都得往后挪一位。最坏情况（i = 0）要移动全部 n 个元素；平均下来也要移动约 n/2 个元素，因此时间复杂度为 O(n)。

• 越靠前插入越慢（insert(0, x) 最差）
• 插入末尾（insert(len(lst), x)）等价于 append()，但不推荐这么写——语义不清且无优化

实际影响：大数据量下性能差距明显

当列表有 10 万以上元素时，频繁用 insert(0, x) 构建列表，可能比用 append() 再 reverse() 慢上百倍。例如：

result = []
for item in data:
  result.insert(0, item)  # 每次 O(n)，总耗时 O(n²)

result = []
for item in data:
  result.append(item)     # 每次 O(1)，总耗时 O(n)
result.reverse()          # 一次 O(n)

替代方案：按需选择更合适的数据结构

如果真需要频繁在开头插入或删除，list 不是最佳选择：

• 用 collections.deque：两端插入/删除都是 O(1)
• 用链表逻辑？Python 标准库无内置单链表，但 deque 足够覆盖多数队列/栈/双端场景
• 若必须用 list 且插入位置固定（如始终末尾），坚持用 append() 和 pop()

本篇关于《list.append()与insert()时间复杂度对比详解》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！