Geek Answers Handbook

Why adding in a particular index is slower in LinkedLists than in ArrayLists

I checked this diagram containing performance comparisons between lists:

enter image description here

And it is very strange to me that adding and deleting elements in a certain index is faster in ArrayList than in LinkedList . Is this chart wrong? The whole idea of LinkedList is to improve such operations while paying with reduced iteration performance. But this diagram seems to indicate that the implementation of Java LinkedLists very poorly executed.

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

+5
source share
2 answers

The whole idea of ​​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 already have a reference to a node object, adding around or deleting it is very cheap too. (I don't think the Java API provides nodes, but some other platforms, such as .NET, do.)

To add to the index in a linked list, the first implementation must go to node in that index ... which is an O (n) operation. Once he got there, the addition is cheap. Thus, adding an index near the beginning (or ending with a smart implementation) is cheap, but adding an index near the middle is expensive.

With an ArrayList flow comes from:

  • Copy existing items outside of the index you are adding
  • Copying all that buffer is not big enough
+13
source

General information:

The micro benchmark is influenced by many factors, therefore it is not so easy to determine the micro test, which is reliable for small rooms.

Insertion can be considered as a two-step process:

  • Find position
  • Insert item

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

Using an ArrayList find the position is O (1), instead the insertion is done in O (n). Moving records of one position (to create space for a new element) is performed using their own libraries, so this is a fairly quick operation.

+2
source

More articles:


All Articles