在O（1）中合并两个双端队列

Question

是否有一种方法可以在deques中合并两个Python O(1)？

Double linked lists可以合并到O(1)中，并且deque是双链表的实现。但是，从文档中我看不到一种有效地合并两个双端队列的方法。实际上，a.extend(b)中提到的a += b和this question遍历了b的所有元素，因此时间复杂度是O(len(b))而不是O(1)。

Answer 1

不。 deque不是简单的双向链表。它们是多个值的块的链接列表（在CPython参考解释器上，每个块最多可以包含64个值），其中只有开始和结束块可能不完整；这些块都不是稀疏的。因此，它必须填充左侧的结束块，这意味着下一个块将从两个块的混合中填充，等等。

除此之外，由于Python中没有诸如破坏性迭代之类的东西（反正不支持任何语言），即使左侧的结束块和右侧的开始块已满，它也无法实际传输这些块。必须进行复制，不能转让块所有权。

Answer 2

我将其作为单独的答案发布，而不是继续在ShadowRanger's good answer下发表评论。 ：）

ShadowRanger正确指出，deque的不变式之一是列表中间的块始终100％充满。因此，如果您有两个双端队列，如

X = (. . . 1) (2 3 4 5) (6 7 . .)  [3 blocks, 7 elements]
Y = (8 9 A B) (C D E .)            [2 blocks, 7 elements]

实际上，在保留顺序的同时，无法在O（1）时间内连接它们，因为deque的不变式不允许您将结果表示为：

X+Y = (. . . 1) (2 3 4 5) (6 7 . .) (8 9 A B) (C D E .)  [invalid]

您将have调整一个双端队列中所有元素的位置，就像这样：

X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .)  [adjusted elements 8 thru E]

或类似这样：

X+Y = (. 1 2 3) (4 5 6 7) (8 9 A B) (C D E .)  [adjusted elements 1 thru 7]

那些是简单的指针交换，因此它们很快；但仍然有O（n）。

---

但是，假设您传入两个双端队列，它们的排列恰巧重合？

X = (. . . 1) (2 3 4 5) (6 7 . .)  [3 blocks, 7 elements]
Y = (. . 8 9) (A B C D) (E . . .)  [3 blocks, 7 elements]

X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .)  [can be done in O(1)]

这里，在我们手动添加项8和9之后，实际上在物理上[[可能窃取O（1）中右双端队列的整个尾部。并且deque可以在O（1）中检测到这种可能性；并手动附加前几项需要O(block size) = O（1）。所以是的，在特殊情况下（不一定总是成立），在物理上可能可以在O（1）时间内连接两个双端队列。

但是，您必须将该操作称为x += y或x.extend(y)以外的名称。

这两个操作已指定不修改其右手操作数。 deque中的标准collections不提供任何类似的“破坏性”操作。 （顺便说一句，如果存在，我希望它被命名为splice。）您可以看到deque的+=运算符的实现（在CPython中实现）here.