0

我在这里阅读了很多问题，讨论了在 Java 中使用 ArrayLists 与 LinkedLists 的成本。到目前为止，我见过的最有用的一个是在这里：何时使用 LinkedList 而不是 ArrayList？.

我想确保我理解正确。

在我当前的用例中，我有多种情况将对象存储在 List 结构中。每次运行时列表中的对象数量都会发生变化，并且从不需要随机访问列表中的对象。基于这些信息，我选择使用 LinkedLists 和 ListIterators 来遍历列表的全部内容。

例如，我的代码可能如下所示：

for (Object thisObject : theLinkedList) {
    // do something
}

如果这是一个错误的选择，请帮助我理解原因。

我目前的理解是，使用迭代解决方案遍历 LinkedList 中的整个对象列表会产生 O(n) 成本。由于没有随机访问列表（例如，需要获取第 3 项），我目前的理解是，这与遍历 ArrayList 的内容并请求每个元素的索引基本相同。

假设我事先知道要存储在列表中的对象数量，我目前的想法是最好将 ArrayList 初始化为适当的大小并完全切换到该结构而不使用 ListIterator。这个逻辑合理吗？

一如既往，我非常感谢大家的意见！

4

1 回答 1

0

迭代 aLinkedList和ArrayList应该花费大致相同的时间来完成，因为在每种情况下，从一个元素步进到下一个元素的成本都是一个常数。但是，由于参考的局部性，这ArrayList可能会更好一些，因此可能值得分析一下会发生什么。

如果您保证总是有固定数量的元素，并且不会在随机位置插入和删除，那么原始数组可能是一个不错的选择，因为它非常快速并且针对这种情况进行了很好的优化。

也就是说，您对使用原因的分析LinkedList似乎是合理的。ArrayList同样，对程序进行概要分析并查看对于您的用例是否实际上会更快，这并没有什么坏处。

希望这可以帮助！

于 2013-09-10T19:27:26.280 回答