list.insert(0, x) 在大列表上极慢，因其底层为动态数组，需将所有元素后移一位，时间复杂度为 O(n)；实测 10 万元素插入 1000 次耗时约 1.8 秒，远慢于 append（0.0012 秒）和 deque.appendleft（0.0015 秒）。
为什么 list.insert(0, x) 在大列表上慢得离谱
因为 Python 的 list 底层是动态数组，insert(0, x) 必须把原有全部元素往后平移一位——10 万个元素就要移动 10 万次内存地址。这不是“有点慢”，而是 O(n) 时间复杂度的硬伤，实测插入 100 万次首元素可能比末尾追加慢 200 倍以上。
真实性能差距：10 万元素插入 1000 次的耗时对比
在典型机器上（Python 3.11，i5-8250U）：
-
list.insert(0, x)：约 1.8 秒 -
list.append(x)：约 0.0012 秒 -
collections.deque.appendleft(x)：约 0.0015 秒
差距不是数量级差异，而是「秒级 vs 毫秒级」。一旦涉及循环插入、日志前缀追加、解析器 token 前置等场景，很容易卡住主线程。
真正可用的替代方案与取舍
别只记「用 deque」，要按场景选：
- 需要频繁在开头/结尾增删 + 不需要随机索引 → 用
collections.deque，appendleft()和popleft()都是 O(1) - 必须保留 list 接口（比如下游代码强依赖
lst[5]或切片）→ 改用lst = [x] + lst（小数据可接受），或反向构建再reversed()（适合一次性前置多条） - 读多写少 + 偶尔前置 → 先
append()，最后统一lst.reverse()，避免每次插入都搬数组 - 需要保持顺序且写入密集 → 考虑临时用
deque积累，完成后再转list(deq)（仅一次拷贝）
容易被忽略的陷阱
deque 看似完美，但要注意：
- 不支持 slicing（
d[1:5]报TypeError），需转list(d)[1:5]（代价高） - 随机访问是 O(n)，
d[10000]会从头遍历，比 list 慢百倍 - 内存占用略高（每个节点含前后指针），小列表（
-
deque不是线程安全的，多线程写入仍需threading.Lock
真正的优化起点，不是换数据结构，而是先问一句：这个“插入开头”的逻辑，是不是可以变成“追加末尾 + 最后翻转”？很多 parser 和 builder 场景其实可以倒着写。
