ArrayDeque 是否有在 remove/add 上移动元素的开销？

Question

我遇到了 this 个问题，其中第一个（已接受的）答案说了这部分：

ArrayDeque doesn't have the overhead of node allocations that LinkedList does nor the overhead of shifting the array contents left on remove that ArrayList has.

我同意节点开销，但不同意关于移动元素的部分。我知道Whosebug也会有错误的信息，但是这个答案有很多票，所以一定是我的无知。那么有人可以告诉我这个吗：

怎么 ArrayDeque 没有 移动元素 的开销？ ArrayDeque（顾名思义）仍然使用 ARRAY。这意味着它的工作方式与任何其他 array 相同。如果我有 10 个元素并且我删除了 head，那 9 个元素必须向左移动 1 个位置。这是 LinkedList 没有的开销 - 它只是更改对 prev 和 next 的引用。我说得对吗？

总而言之，ArrayList 和 ArrayDeque 的工作方式不一样吗？如果结构发生变化，它们都会移动元素。唯一的区别是ArrayList可以访问任何任意位置，而ArrayDeque作为FIFO/LIFO。如果我错了，有人可以纠正我吗？我不想在这里学错东西。

Answer 1

有这样一种直觉，即从数组的前面移除需要将所有内容移回原处，这真是太棒了。但是，在 ArrayDeque 的特定情况下，实现的设计方式不需要这样做。

基于数组的双端队列通常使用称为循环缓冲区的数据结构来实现。这个想法是我们维护一个元素数组，但假装数组的末端粘在一起形成一个环。

ArrayDeque内部维护了一个16个元素的数组，我们可以这样查看：

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

我们维护两个不同的指针，一个头指针和一个尾指针，跟踪第一个元素的位置双端队列和双端队列最后一个元素的位置。最初，它们将指向数组的开头：

 head
  |
  v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  ^
  |
 tail

每当我们做addFirst时，我们将头指针后退一步，然后将元素写入我们找到的位置。由于我们假装数组的两端链接在一起，所以在这里后退一步将头指针移动到最后一个位置：

                                                             head
                                                              |
                                                              v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  ^
  |
 tail

做一个addLast，我们写到尾部位置，然后向前推进：

                                                             head
                                                              |
                                                              v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      ^
      |
     tail

这是如果我们再做两个 addFirsts 的样子：

                                                     head
                                                      |
                                                      v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X |   |   |   |   |   |   |   |   |   |   |   |   | X | X | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      ^
      |
     tail

这是如果我们再做两个 addLasts 的样子：

                                                     head
                                                      |
                                                      v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X | X | X |   |   |   |   |   |   |   |   |   |   | X | X | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
              ^
              |
             tail

我们从头指针开始读取双端队列的元素，然后继续前进直到到达尾指针。所以在这种情况下，我们从 head 指向的位置开始读取，而不是数组中的第一个位置。

以这种方式安排事物可以非常快地 (O(1)) 删除双端队列的第一个元素。我们只是清除 head 指向的条目并向前移动 head 一步，就像这样：

                                                         head
                                                          |
                                                          v
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| X | X | X |   |   |   |   |   |   |   |   |   |   |   | X | X |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
              ^
              |
             tail

请注意，不需要移动任何东西，因为我们只是假装我们从数组中较晚的位置开始。

但是，如果您要从 ArrayDeque 的中间移除，那么，就像从大多数其他基于数组的结构的中间移除一样，是的，您必须移动元素。但是，话又说回来，ArrayDeque 并未针对该用例进行优化；顾名思义，它专门设计为双端队列。

ArrayDeque 是否有在 remove/add 上移动元素的开销？

Does ArrayDeque have overhead of shifting elements on remove/add?

java

arrays

queue

arraylist

arraydeque