CODEWITHSUNDEEP
javaperformancearraylistlinked-list
FinnTheHuman
FinnTheHuman

Reputation: 1155

Why is add at specific index slower in LinkedLists than in ArrayLists

I was checking this chart containing performances comparisons among lists:

enter image description here

And I find it very odd that adding and removing elements at a specific index performs faster in an ArrayList than it does in a LinkedList. Is this chart wrong? The whole idea of a LinkedList is to improve such operations, while paying with reduced iteration performance. But this chart seems to indicate that Java's implementation of LinkedLists is very poorly done.

Should I trust the chart? And if so, why Java LinkedLists perform so bad?

Upvotes: 5

Views: 558

Answers (2)

Davide Lorenzo MARINO
Davide Lorenzo MARINO

Reputation: 26926

A general information:

Making micro benchmark is influenced by many factors, so it is not so easy to define a micro benchmark that is reliable for little numbers.

The insertion can be seen as a two step process:

  • Find position
  • Insert element

The first step, find position, is done in O(n), the second step in O(1) for a LinkedList.

Using an ArrayList finding the position is O(1), instead the insertion is done in O(n). Moving records one position (to create space for a new element) is done using native libraries so it is a quite fast operation.

Upvotes: 2

Jon Skeet
Jon Skeet

Reputation: 1500595

The whole idea of a LinkedList is to improve such operations, while paying with reduced iteration performance.

No, the idea of a linked list is to make adding or removing at the end or beginning very cheap... or if you have a reference to a node object already, adding around that or removing it is very cheap too. (I don't think the Java API exposes the nodes, but some other platforms like .NET do.)

To add at an index within a linked list, the implementation first has to navigate to the node at that index... which is an O(n) operation. Once it's got there, the add is cheap. So adding by index near the start (or end with a smart implementation) is cheap, but adding by index near the middle is expensive.

With an ArrayList, the expense comes from:

  • Copying the existing elements beyond the index you're adding
  • Copying the whole thing is the buffer isn't big enough

Upvotes: 13

Related Questions