关于Java中

Question

的文件执行ArrayDeque的说：

大小可变数组实现双端队列接口。 Array deques 没有容量限制;他们根据需要增长以支持使用

但是我仍然想了解ArrayDeque的结构究竟是什么，调整大小如何工作。如果有人能够提供可靠的信息来源，我可以找到答案，这也是非常好的。根据我发现的一些Google结果，它可能被实现为圆形阵列。这是真的吗？什么是增长政策？它与ArrayList相似吗？如果是这样，ArrayDeque在类似于ArrayList的操作中是否像在末尾添加或删除元素一样操作？

谢谢。

Answer 1

ArrayList和ArrayDeque的增长策略没有记录，并且可能因JDK实现甚至JDK版本而异。例如，在Open JDK 6中是(n*3/2+1)，但在Open JDK 8中是(n*3/2)。在JDK 6 ArrayList中，默认的构造函数最初是用10个元素数组创建的，而在JDK 8中，只有在添加了至少一个元素时才分配数组。

ArrayDeque执行更改的次数少于ArrayList。它始终在内部使用默认情况下从16开始的内置两倍大小的阵列，并在必要时将其加倍，因此对于ArrayList和ArrayDeque（对于ArrayDeque，平均具有较少的重新分配但浪费较多的内存），内存占用可能不同。

对于ArrayList和ArrayDeque来说，尾部的添加几乎同样快，除非需要重新分配。重新分配事件可能发生在不同的点。例如，默认情况下，在添加元素＃11时将首先为ArrayList重新分配，但对于ArrayDeque，将在元素＃16上发生。

ArrayDeque的优势是能够将元素添加到头部的速度与尾部一样快。相反，ArrayList将在O(n)时间内完成，因为它必须移动所有现有元素。因此，在需要添加/删除头部和尾部时，请使用ArrayDeque。如果您只需要修改尾部，通常首选ArrayList。