is
Jon Skeet
Why is add at specific index slower in LinkedLists than in ArrayLists
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?
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
See more on this question at Stackoverflow