哪个列表<对象>实现对于一次通过写入，读取然后销毁的最快？

list collections java big-o

2022-09-01 15:14:12

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

答案 1

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

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

否则，您可能必须进行分析。虽然访问是 O（1），但由于动态调整大小，创建它并不那么简单。ArrayList

需要考虑的另一点是，时空权衡并不明确。每个 Java 对象都有相当多的开销。虽然可能会在多余的插槽上浪费一些空间，但每个插槽只有 4 个字节（在 64 位 JVM 上为 8 个字节）。的每个元素可能大约为 50 个字节（在 64 位 JVM 中可能是 100 个字节）。因此，在实际赢得其假定的空间优势之前，您必须在一个位置上浪费相当多的插槽。参考的局部性也是一个因素，在这方面也是可取的。ArrayListLinkedListArrayListLinkedListArrayList

在实践中，我几乎总是使用.ArrayList

答案 2

第一个想法：

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

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