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

Question

I was checking this chart containing performances comparisons among lists:

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?

Answer 1

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

Answer 2

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.