java - 为什么典型的 Array List 实现不是双端的？

Question

为什么 ArrayList 通常不实现为双端的，这将支持在前面和后面的快速分摊插入？

使用后者比使用前者有缺点吗？

(我不只是在谈论 Java——我还没有看到双端数组列表是任何其他语言的默认设置，但 Java 在这里只是一个很好的例子。)

---

*编辑:我最初称它们为“array deques”，但这是我的误解；我不是在谈论队列，而是双端数组列表。

Answer 1

ArrayList 很简单；条目从 0 开始，您可以在末尾添加内容(这可能会延长数组)，但列表中的条目 #X 始终是 backing_array[X]。

ArrayDeque 会更复杂；除了必须跟踪序列的开始(因为它不再保证从 0 开始，除非你想要 O(N) 移位/取消移位)，你还必须担心另一端是“空的”。这种额外的复杂性是有代价的；在更常见的情况下(列表)，RTL 仍然必须在双端队列中执行所有必要的检查和索引数学运算，无缘无故地减慢应用程序。条目 #X 变为 backing_array[start+X]，边界检查也有额外的数学运算。

因此，除非您确实需要双端队列功能，否则坚持使用列表会更简单、更有效，至少在您处理数组时是这样。