为什么典型的数组列表实现不双头？ [英] 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）班/ unshifts），你也不得不担心的另一端是空。这额外的复杂性是有代价的;在更常见的情况（列表）时，RTL仍然会做所有必要的检查和指数的数学在一个deque，减慢应用程序没有真正的理由。进入#X成为 backing_array [开始+ 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屋！