在将列表一次创建一个元素，然后一次读取一个元素的情况下，最快的列表实现(在Java中)是什么？读取将使用迭代器完成，然后列表将被销毁。
我知道get的Big O表示法是O(1)，ArrayList的add是O(1)，而LinkedList的get是O(n)，而O(1)是加法。迭代器的行为是否具有相同的Big O表示法？

解决方案

循环访问链表是每个元素O(1)。

每个选项的Big O运行时相同。由于更好的内存位置，ArrayList可能会更快，但是我们必须对其进行测量才能确定。选择使代码最清晰的内容。

首先的想法：

• 将代码重构为不需要列表。
• 将数据简化为标量数据类型，然后使用：int []
• 甚至只使用我们拥有的任何对象组成的数组：Object []-John Gardner
• 将列表初始化为完整大小：new ArrayList(123);

当然，正如其他人所提到的，进行性能测试，证明新解决方案是一种改进。

我建议对其进行基准测试。读取API是一回事，但是直到我们自己尝试使用它为止，它都是学术性的。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。##############

应该很容易测试，只要确保我们进行有意义的操作，否则热点将使我们变得更聪明，并将其全部优化为NO-OP :)

请注意，如果天真地完成对LinkedList实例的迭代，则可以为O(n ^ 2)。具体来说：

List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

就效率而言，这是绝对可怕的，因为对于每次迭代，该列表必须遍历两次至" i"。如果我们确实使用了LinkedList，请确保使用Iterator或者Java 5增强的for循环：

for (Object o : list) {
    // ...
}

上面的代码是O(n)，因为列表是有状态地遍历原位的。

为了避免上述所有麻烦，只需使用ArrayList。并非总是最佳选择(尤其是为了提高空间效率)，但这通常是一个安全的选择。

在很大程度上取决于我们是否预先知道每个列表的最大大小。

如果这样做，使用ArrayList;它肯定会更快。

否则，我们可能必须进行概要分析。虽然对" ArrayList"的访问为O(1)，但由于动态调整大小，创建它并不那么简单。

要考虑的另一点是，时空权衡尚不明确。每个Java对象都有相当多的开销。虽然" ArrayList"可能会在多余的插槽上浪费一些空间，但每个插槽只有4个字节(在64位JVM上为8个字节)。 " LinkedList"的每个元素可能约为50个字节(在64位JVM中可能为100个字节)。因此，在LinkedList实际上获得其假定的空间优势之前，必须在ArrayList中浪费大量插槽。引用的局部性也是一个因素，在那里最好使用" ArrayList"。

实际上，我几乎总是使用" ArrayList"。

我们几乎可以肯定需要ArrayList。按照文档中的指定，添加和读取都是"摊销固定时间"(即O(1))(请注意，即使列表必须增加其大小，这也是正确的，其设计方式请参见http：//java.sun。 com / j2se / 1.5.0 / docs / api / java / util / ArrayList.html)。如果我们大致知道将要存储的对象数量，那么甚至可以消除ArrayList大小的增加。

将O(1)加到链表的末尾，但常数乘数大于ArrayList(因为通常每次都创建一个节点对象)。如果我们使用的是迭代器，则读取操作实际上与ArrayList相同。

始终使用最简单的结构是一个好规则，除非有充分的理由不这样做。这里没有这样的原因。

ArrayList文档中的确切引述是："加法运算以摊销的恒定时间运行，也就是说，加n个元素需要O(n)时间。所有其他运算都以线性时间运行(大致来说)。常数因子相较于LinkedList实施方案，它要低。"