为什么典型的数组列表实现不是双端的? [英] Why typical Array List implementations aren't double-ended?

问题描述

为什么ArrayList一般不实现为双端的，这样既支持前后快速分摊插入?

Why aren't ArrayLists generally implemented to be double-ended, which would support fast amortized insertion in the front as well as the back?

使用后者比使用前者有什么缺点吗?

Is there ever a disadvantage to using the latter over the former?

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

(I'm not talking just about Java -- I haven't seen double-ended array lists being the default in any other language, but Java was just a good example here.)

*我最初称它们为数组双端队列"，但这是我的误解；我说的不是队列，而是双端数组列表.

* I originally called them "array deques" but that was a misunderstanding on my part; I wasn't talking about queues, but double-ended array lists.

推荐答案

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

An ArrayList is simple; entries start at 0, and you can add stuff at the end (which might lengthen the array), but entry #X in the list is always backing_array[X].

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

An ArrayDeque would be more complex; besides having to keep track of the start of the sequence (because it'd no longer be guaranteed to start at 0, unless you want O(N) shifts/unshifts), you'd also have to worry about the other end being "empty". That extra complexity comes at a cost; in the more common case (lists), the RTL would still have to do all the checks and index math necessary in a deque, slowing down the app for no real reason. Entry #X becomes backing_array[start+X], and bounds checks have extra math to them as well.

因此，除非您确实需要双端队列功能，否则坚持使用列表更简单、更高效，至少在您使用数组时是如此.

So unless you have a real need for deque functionality, it's simpler and more efficient to stick with a list, at least when you're messing with arrays.

这篇关于为什么典型的数组列表实现不是双端的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！