为什么ArrayLists 通常不实现为双端，这将支持在前面和后面的快速分期插入？
使用后者比使用前者有什么缺点吗？
（我不只是在谈论 Java——我还没有看到双端数组列表是任何其他语言的默认设置，但 Java 只是一个很好的例子。）
*编辑：我最初称它们为“数组双端队列”，但这是我的误解；我说的不是队列，而是双端数组列表。
问问题
1838 次
4 回答
5
ArrayList 很简单；条目从 0 开始，您可以在末尾添加内容（这可能会延长数组），但列表中的条目 #X 始终为backing_array[X].
ArrayDeque 会更复杂；除了必须跟踪序列的开始（因为它不再保证从 0 开始，除非你想要 O(N) 班次/取消班次），你还必须担心另一端是“空的”。这种额外的复杂性是有代价的。在更常见的情况下（列表），RTL 仍然需要在双端队列中进行所有必要的检查和索引数学运算，从而无缘无故地减慢应用程序的速度。条目 #X 变为backing_array[start+X]，并且边界检查对它们也有额外的数学运算。
因此，除非您真正需要双端队列功能，否则坚持使用列表会更简单、更有效，至少在您处理数组时是这样。
于 2011-05-27T04:04:57.017 回答
1
仅当您想以 FIFO 或 LIFO 方式访问数据时才使用双端队列，它们的通用接口既不提供获取第 n 个元素的方法，您应该手动完成，实际上如果您查看 Java Deque在这里，您了解没有提供第 n 个方法。当您需要索引任何数据组时，这应该足以避免使用它。
好的，您可以将其实现为数组双端队列而不是普通数组，但这会添加仅在需要时才应考虑的功能，而不是默认情况下。否则，您可以证明对简单问题使用更复杂的数据结构是合理的，因为您可以。
恕我直言，这也是当今数组之间的协同作用以及当您在机器附近编写代码时它们是如何实现/管理的。
于 2011-05-27T03:50:48.253 回答
0
在 Java ArrayDeque 中没有实现 List。我不确定为什么没有。
于 2011-05-27T04:00:11.660 回答
0
正常的ArrayList实现是代码的正常首选集合类型，它只需要一些可以重复添加项目然后从中读取项目的东西。该类型提供了比这更多的功能，并且省略其中一些可能会增强该类型在主要用例中的功能，但是如果ArrayList操作速度甚至慢 1%，那么在整个宇宙中必须花费的额外 CPU 时间总量会很重要。
此外，还不清楚对双端数组列表的索引访问应该如何表现，因为有两种合理的行为模型：它可以指定从低编号端添加或删除项目应该改变所有现有项目的编号，或者它可以指定在项目 0 之前插入的项目的索引将为 -1（所有现有索引将保持不变）。在 item 0 之前添加超过 2^32 个 item（同时从另一端删除足够的 item 以避免内存不足）将添加 item MIN_INT，然后是 item MAX_INT，然后是 MAX_INT-1，等等。这样的界面在在某些方面，但在其他方面可能非常好（例如，实现可以允许在相反端操作的写入线程和读取线程同时进行索引访问，
肯定有各种双端集合类型的用途，但这并不意味着添加双端功能会为常见用例增加任何价值。
于 2013-12-24T18:35:23.943 回答