英文:
LinkedList can lead to unnecessary performance overhead if the List is randomly accessed
问题
我有这段代码：
@Nullable
@Value.Default
default List<String> write() {
return new LinkedList<>();
}
而DeepCode的IntelliJ插件指出，如果随机访问列表，则LinkedList可能会导致不必要的性能开销。应改用ArrayList。
LinkedList相比ArrayList有什么性能开销？这是否真的和DeepCode所建议的一样明显？
英文:
I have this my code:
@Nullable
@Value.Default
default List<String> write() {
return new LinkedList<>();
}
And DeepCode IntelliJ plugin indicates that LinkedList can lead to unnecessary performance overhead if the List is randomly accessed. And ArrayList should be used instead.
What is this performance overhead that LinkedList have over ArrayList? Is it really much of a difference as what DeepCode suggest?
答案1
得分: 4
LinkedList和ArrayList在性能特性上有所不同，如JavaDoc中所述。在LinkedList中插入是廉价的，特别是在前面和后面插入。按顺序遍历LinkedList，例如使用流或foreach，是相对廉价的。
另一方面，随机访问，例如使用get(n)，速度较慢，因为它需要O(n)的时间。
另一方面，ArrayList可以在O(1)的时间内进行随机访问。然而，插入操作以平摊常数时间运行：
add操作以平摊常数时间运行，也就是说，添加n个元素需要O(n)的时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常数因子较低。
LinkedList的主要优点在于允许快速插入和通过迭代器在前端/末尾进行删除。一个典型的使用场景是将LinkedList用作Queue或Deque（它实际上也实现了这两个接口）。
因此，这取决于您正在做什么。如果您经常需要随机访问，请使用ArrayList。如果您经常需要顺序访问（通过迭代器）并在前面/后面进行添加/删除，例如因为您将其用作Queue，请使用LinkedList。
如果在任意位置进行添加，例如通过add(int index, E element)，LinkedList必须首先遍历列表，使插入变为O(n)，与ArrayList没有任何优势（ArrayList必须将后续元素下移，并最终调整底层数组的大小，这也是平摊的O(n)）。。
实际上，我只会在确有需要时选择LinkedList，否则我会将ArrayList作为默认选择。请注意，如果您知道元素的数量，可以适当地调整ArrayList的大小，从而避免调整大小，减小ArrayList的缺点。
- https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
- https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
- 另请参阅https://stuartmarks.wordpress.com/2015/12/18/some-java-list-benchmarks/（感谢@Leprechaun提供此资源）
英文:
LinkedList and ArrayList have different performance characteristics as described in the JavaDoc. Inserting into a LinkedList is cheap, especially at the front and back. Traversing a LinkedList in sequence, e.g. with streams or foreach, is (relatively) cheap.
On the other hand, random access e.g. with get(n) is slow, as it takes O(n).
ArrayLists on the other hand do random access in O(1). Inserting on the other hand runs in amortized constant time:
> The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
The main advantage of LinkedList is that it allows for fast inserting and deletion at the front/end and via the iterator. A typical usage scenario is if you use the LinkedList as a Queue or Deque (it actually implements those two interfaces as well).
So, it depends on what you are doing. If you have frequent random access, use ArrayList. If you have frequent sequential access (via the iterator) and adding/removing from front/back, e.g. because you use it as a Queue, use LinkedList.
If you add at arbitrary positions, e.g. via add(int index, E element), a LinkedList has to traverse the list first, making insertion O(n), having no benefit over ArrayList (which has to shift the subsequent elements down and eventually resize the underlying array, which again, is amortized O(n) as well).
In practice, I'd only choose LinkedList if there is a clear need for it, otherwise I'd use ArrayList as the default choice. Note that if you know the number of elements, you can size an ArrayList properly and thus avoid resizing, making the disadvantages of ArrayList even smaller.
- https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
- https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
- See also https://stuartmarks.wordpress.com/2015/12/18/some-java-list-benchmarks/ (thanks to @Leprechaun for providing this resource)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论