我遇到了这个问题，第一个（被接受的）答案是：
arraydeque没有linkedlist那样的节点分配开销，也没有arraylist在删除时留下的数组内容移动开销。
我同意节点开销，但不同意关于元素移位的部分。我知道stackoverflow也可能有错误的信息，但这个答案有很多票，所以一定是我的无知。有人能告诉我：
怎么了 ArrayDeque 没有移动元件的开销？ ArrayDeque （顾名思义）仍然使用数组。这意味着它的工作原理与任何其他数组相同。如果我有10个元素，我去掉了头，那9个元素必须向左移动1个位置。就在头顶上 LinkedList 没有-它只是更改对上一个和下一个的引用。我说的对吗？
总而言之，不要 ArrayList 以及 ArrayDeque 同样的工作方式？如果结构发生变化，它们都会移动元素。唯一的区别是 ArrayList 可以访问任意位置，而 ArrayDeque 作为先进先出/后进先出。如果我错了，有人能纠正我吗？我不想在这里学到错误。
1条答案
按热度按时间4nkexdtk1#
有这样一种直觉是很好的，即从数组的前面移除所有内容都需要向后移动。然而，在
ArrayDeque，实现的设计方式不需要这样做。基于数组的deque通常使用称为循环缓冲区的数据结构来实现。我们的想法是维持一个元素数组，但假设数组的两端粘在一起形成一个环。
这个
ArrayDeque内部维护一个由16个元素组成的数组，我们可以这样查看：我们维护两个不同的指针，一个头指针和一个尾指针，跟踪deque的第一个元素的位置和deque的最后一个元素的位置。最初，它们将指向数组的开头：
无论我们什么时候
addFirst，我们将头指针备份一步，然后将元素写入找到的位置。因为我们假设数组的两端是连接在一起的，所以在这里后退一步会将头指针移动到最后一个位置：做一个
addLast，我们写到尾部位置，然后向前推进：如果我们再做两次的话会是这样的
addFirst学生：如果我们再做两次，情况会是这样
addLast学生：我们通过从头部指针开始，然后继续前进，直到到达尾部指针来读取deque的元素。在这种情况下，我们从
head，而不是数组中的第一个位置。以这种方式安排事情可以非常快地（o（1））除去deque的第一个元素。我们只是清理出
head然后移动head向前走一步，像这样：请注意，不需要进行任何移动，因为我们只是假装从数组中稍后的位置开始。
但是，你是不是要从中间离开
ArrayDeque，然后，就像从大多数其他基于数组的结构中间移除一样，是的，您必须移动元素。但是，话说回来，ArrayDeque没有针对该用例进行优化；顾名思义，它是专门设计成一个双端队列的。