LinkedList<E>与ArrayList<E>成本

Question

我在这里读到了很多问题，这些问题讨论了在Java中使用ArrayLists与LinkedLists的成本。到目前为止，我看到的最有用的一个是在这里：When to use LinkedList over ArrayList?。

我想确定我的理解是正确的。

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

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

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

如果这是一个错误的选择，请帮助我理解为什么。

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

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

一如既往，我非常感谢每一个人的投入！

Answer 1

对LinkedList和ArrayList的迭代应该花费大致相同的时间来完成，因为在每种情况下，从一个元素到另一个元素的成本是一个常数。但是，由于引用的局部性，ArrayList可能会更好一些，因此可能值得对其进行分析，以了解发生了什么。

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

尽管如此，您对为什么使用LinkedList的分析似乎是正确的。同样，对程序进行概要分析并查看ArrayList对于您的用例是否会更快并不会有什么害处。

希望这能有所帮助！