Meh*_*dad 6 java language-agnostic arraylist deque arraydeque
为什么通常不ArrayList实施双端,这将支持前面和后面的快速摊销？
使用后者而不是前者有不利之处吗？
(我不只是谈论Java - 我没有看到双端数组列表是任何其他语言的默认值,但Java只是一个很好的例子.)
*编辑:我最初称它们为"阵列deques",但这对我来说是一种误解; 我不是在谈论队列,而是双端阵列表.
ArrayList很简单; 条目从0开始,你可以在最后添加东西(这可能会延长数组),但列表中的条目#X总是如此backing_array[X].
ArrayDeque会更复杂; 除了具有跟踪序列开始的(因为它会不再能保证在0开始,除非你想O(N)班/ unshifts),你还不得不担心的另一端是"空".额外的复杂性需要付出代价; 在更常见的情况(列表)中,RTL仍然必须在双端队列中进行所有必要的检查和索引数学运算,从而减慢应用程序的速度.条目#X变为backing_array[start+X],并且边界检查也有额外的数学.
因此,除非你真的需要deque功能,否则坚持使用列表会更简单,更有效,至少在你搞乱阵列的时候.