在一次创建列表一个元素然后在稍后一次读取一个元素的情况下，最快的列表实现(在 java 中)是什么？读取将使用迭代器完成，然后列表将被销毁。
我知道 get 的 Big O 表示法是 O(1)，而 ArrayList 的 add 是 O(1)，而 LinkedList 的 get 是 O(n)，add 是 O(1)。迭代器是否使用相同的大 O 表示法？
最佳答案
这很大程度上取决于您是否预先知道每个列表的最大大小。
如果这样做，请使用 ArrayList;它肯定会更快。
否则，您可能需要进行概要分析。虽然访问 ArrayList 是 O(1)，但创建它并不简单，因为动态调整大小。
要考虑的另一点是时空权衡并不明确。每个 Java 对象都有相当多的开销。虽然 ArrayList 可能会在多余的插槽上浪费一些空间，但每个插槽只有 4 个字节(或在 64 位 JVM 上为 8 个字节)。 LinkedList 的每个元素大约有 50 个字节(在 64 位 JVM 中可能是 100 个字节)。因此，在 LinkedList 真正赢得其假定的空间优势之前，您必须在 ArrayList 中有相当多的浪费插槽。引用的局部性也是一个因素，ArrayList 也更可取。
在实践中，我几乎总是使用 ArrayList。
关于java - 哪个 list<Object> 实现对于一次写入、读取和销毁来说是最快的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/135314/