时间戳

首页 > 解决方案 > ArrayDeque 在删除/添加时是否有移动元素的开销？

java - ArrayDeque 在删除/添加时是否有移动元素的开销？

问题描述

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

ArrayDeque 没有 LinkedList 没有的节点分配开销，也没有 ArrayList 具有的将数组内容移到 remove 时的开销。

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

HowcomeArrayDeque没有移动元素的开销？ArrayDeque（如其名称所述）仍然使用ARRAY。这意味着它与任何其他数组一样工作。如果我有 10 个元素并且我删除了head，那么这 9 个元素必须向左移动 1 个位置。这是LinkedList没有的开销——它只是改变了对prev和next的引用。我对么？

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

标签： javaarraysarraylistqueuearraydeque

解决方案

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

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

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

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

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

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

每当我们执行 anaddFirst时，我们都会将头指针备份一步，然后将元素写入我们找到的位置。由于我们假设数组的两端是链接在一起的，所以这里后退一步会将头指针移动到最后一个位置：

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

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

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

如果我们再做两个 s，它会是什么样子addFirst：

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

addLast这就是如果我们再做两个s 的样子：

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

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

以这种方式安排事情使得删除双端队列的第一个元素非常快（O（1））。我们只是清除了指向的入口head，向前head迈了一步，像这样：

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

请注意，没有什么需要移动，因为我们只是假装我们从数组中的较晚位置开始。

但是，如果您要从ArrayDeque. 但是，再一次，ArrayDeque没有针对该用例进行优化；顾名思义，它专门设计为双端队列。

推荐阅读