CODEWITHSUNDEEP
java
Fireburn
Fireburn

Reputation: 1021

LinkedList can lead to unnecessary performance overhead if the List is randomly accessed

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?

Upvotes: 0

Views: 84

Answers (1)

Polygnome
Polygnome

Reputation: 7820

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.

Upvotes: 4

Related Questions