5

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?

Improve this question

2 Answers 2

Reset to default
13

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
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Java doesn't expose the node, but the LinkedList's iterator allows adding an element at a given position. So adding an element every 3 positions for example is less complex in a linked list than in an arraylist, which would have to constantly shift all the remaining elements to the right).
Sorry @Jon, I have no idea what "that's a silver lining" means :-(
@JBNizet: It means that it doesn't make up for the lack of access to the node directly, but it's better than nothing.
@JBNizet here is an account of the phrase's origin. Uncultured swine as I am, I didn't realise it came from John Milton.
Part of the reason iterating a linked list is so expensive is that it will often trigger numerous cache misses, since linked lists have poorer memory locality than vectors. Copying a big, contiguous chunk of memory (with a vector) is often cheaper than navigating a bunch of non-contiguous chunks of memory.
|
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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.