ArrayDeque是作为数组实现的，为什么不是Random Access？

Question

我知道 ArrayDeque 在添加和删除简单列表时速度很快。 我测试了一下，增删改查比LinkedList快。 因为我知道它是作为一个数组来实现的，那为什么不用随机访问呢？

我阅读了 Java src 中的 ArrayDeque.java 文件。但是以我的英语水平，我不太理解。看了很多谷歌和Stack Overflow的文章，都没有得到想要的答案

总而言之，我要找的是：

1. 为什么ArrayDeque不是Random Access？（我最好奇）
2. ArrayDeque在什么情况下使用？
3. ArrayDeque 不是作为数组实现的吗？ （我是不是误会了？）

非常感谢您的回复！

Answer 1

答案是没有充分的理由。将常数时间

get(int)

和

set(int,E)

添加到

ArrayDeque

会很容易。我不止一次不得不在

ArrayDeque

中实现

ArrayList

的算法来弥补这种不足。

Answer 2

如 here 中所述，ArrayDeque 是 Deque 接口的可调整大小的数组实现。下划线数据结构是数组。但是，它不支持随机访问，因为它公开了双端队列接口。如果要访问 Deque 的随机元素，可以调用

toArray()

，然后通过索引访问元素。

Answer 3

我认为对“为什么没有随机访问”的简短回答是，创建类时似乎没有必要，而且有点没有意义：

ArrayDeque

首先是一种

Deque

，这是主要允许两端访问的东西，仅此而已。所以我有点同意随机访问函数不应该在

Deque

中（尽管按照同样的逻辑，它也不应该在

List

中）。正如其他人指出的那样，您也可以让

ArrayDeque

实施

List

，但是很难改造，也许还有其他问题。我个人认为 Java 中的集合接口一团糟，但我就此打住。

现在，如果你想解决

ArrayDeque

没有随机访问的缺点，有一些选择：

• 首先，你真的需要随机访问吗？也许

  iterator()

  或

  descendingIterator()

  就足够了。
• 对于真正的随机访问，这可能不是很快，但应该是 O(1)：

  deque.stream().skip(index).findFirst().get()