Python中collections.deque删除元素的时间复杂度是多少？

嘿，这个问题问到点子上了——毕竟我们用deque大多是冲它两端操作的高效性去的，但中间元素的操作确实容易让人迷糊。

直接给结论：执行del deq[1]这种删除中间元素的操作，时间复杂度是O(n)，这里的n是deque的总长度。

为什么是O(n)？ #

CPython里的deque是基于块链表实现的双端队列，它的设计初衷是让两端的添加/删除操作（比如popleft()、pop()）达到O(1)的时间复杂度。但当你要删除中间位置的元素时：

1. 首先需要定位到目标索引的位置：deque会选择从离目标更近的一端开始遍历（比如索引1离左端更近，就从左数），这一步是O(min(k, n-k))的复杂度，k是目标索引。
2. 找到元素后，为了维护队列的结构，需要将该位置一侧的所有元素整体移动一位来填补空缺——这一步的时间复杂度是O(n)，最坏情况下（比如删除正中间的元素）需要移动近一半的元素，整体复杂度就落到了线性级别。

用你给出的例子验证 #

import collections
deq = collections.deque([1, 2, 3])
del deq[1]
# 此时deque变为 deque([1, 3])

这个小例子里移动的元素很少，但如果是一个包含上万个元素的deque，删除中间位置的元素时，需要移动大量元素，耗时会随队列长度线性增长。

额外小贴士 #

如果你的业务场景需要频繁进行中间元素的删除或随机访问，那deque可能不是最优选择——普通的Python列表（list）在随机访问上是O(1)，但中间删除同样是O(n)；如果需要更高效的中间操作，可以考虑使用平衡树类的数据结构（不过Python标准库没有自带，需要第三方库支持）。而如果只是频繁操作两端，deque依然是你的不二之选。

内容的提问来源于stack exchange，提问作者Max Mikhaylov