• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList v LinkedList speed comparison

 
Ranch Hand
Posts: 209
13
VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
On account of the different ways in which they implement the List interface, I understand that in theory:
ArrayList should be faster doing get() operations
LinkedList should be faster doing add() & remove() operations.
So, I thought I'd write a test to see if that really does happen.



The program prints how long it takes for a large number of add() operations on an ArrayList and a LinkedList, allowing comparison of the two.
Similarly get() and remove().



Interestingly, as expected, for add() & remove(), LinkedList is much faster.
However, contrary to my expectation, and despite repeating the test several times, there is almost no difference as far as get() is concerned, and often ArrayList.get() seems slightly slower.

Is there something wrong with the way I'm testing get() performance, or in reality is there not much difference between the two?


 
author & internet detective
Posts: 41878
909
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Richard Hayward wrote:Is something wrong with the way I'm testing get() performance, or in reality is there not much difference between the two?


Actually yes.

This doesn't do what you think it does. It always gets the 0th index in the list.


If you change the line to this, you get an actual random index:


With the newly added parens, the output is:


Where ArrayList get is MUCH faster. LinkedList is really good at getting the first element. Since your test was inadvertently asking for the first element on each time through the loop, you never hit the cost of LinkedList gets.

ps - I gave you a cow for the excellent question including all the relevant information.
 
Richard Hayward
Ranch Hand
Posts: 209
13
VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeanne Boyarsky wrote:
If you change the line to this, you get an actual random index:



Ah, yes! Thank you Jeanne.

I'd made that same error at 3 points in my code, which I've now corrected. I also made a minor adjustment to exclude time spent finding out the list sizes, in case that is an expensive operation.


Running this amended code, as you say, ArrayList.get is much faster than LinkedList.get, irrespective of the List size.

As previously, I was expecting LinkedList.add to be fastest, since all it has to do is adjust a pointer, pointing to the next element,  at the point where the insertion is made. Similarly with LinkedList.remove. The mental picture I have of these same operations on an ArrayList involves shifting the whole lot in memory.

However, that's not the case.







For larger List sizes, LinkedList adds & removes seem to be slower than those of ArrayList.


 
Jeanne Boyarsky
author & internet detective
Posts: 41878
909
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Richard Hayward wrote:For larger List sizes, LinkedList adds & removes seem to be slower than those of ArrayList.


Right. Because you are trying to add to a random position in the LinkedList. Which means the LinkedList has to use the slow "get" to find the right spot and then do a quick insert. If you were trying to always add to the end, you'd see a faster time.

Compare the add with these two and see how much faster it is for linked list
list.add(new Integer(i));
list.add(index, new Integer(i));

I used the below harness and got:
Time taken for 100000 ArrayList: random index  insertions =    355068666
Time taken for 100000 LinkedList: random index  insertions =  16926676282
Time taken for 100000 ArrayList: insert at end insertions =     10364420
Time taken for 100000 LinkedList: insert at end  insertions =      6117165

AddArrayListLinkedList
At random index35506866616926676282
At end103644206117165


As you can see, both benefit from always adding at the end. LinkedList way more so than ArrayList.

 
Richard Hayward
Ranch Hand
Posts: 209
13
VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jeanne Boyarsky wrote:you are trying to add to a random position in the LinkedList. Which means the LinkedList has to use the slow "get" to find the right spot and then do a quick insert.


ok, I was overlooking that fact.

Those timings make sense to me now.

Thanks for your help Jeanne.
Most instructive.
 
Ranch Hand
Posts: 199
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am coming back to Java Ranch after almost a decade.
Very good and useful discussion on the performance of ArrayList versus LinkedList. So, as I  understand, LinkedList is good for adding/removing to/from the end or beginning of a list, and "get" from the end and beginning. For any other indexed get, add or remove operation, ArrayList is still better, since LinkedList has to do the indexed get first for any operation, which is expensive.
 
Ranch Hand
Posts: 59
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A problem with these benchmarks is that the effect of JIT compilation and GC collection can affect the results. Here, it's the one that runs first that's slower.

With:



I get:



and with:



I get:



I tried this JMH benchmark:



With results (higher is better):



So adding to the end of an ArrayList is faster.

ArrayLists do need to be resized as elements are added, but the time between each resize increases exponentially as the size increases. This gives a constant time per element added.

Also, the elements in an ArrayList are stored in an array which keeps all the elements together in RAM. A resize is just copying a contiguous block of memory from one location to another, which computers do all the time.

With a LinkedList, you need to update the previous pointer, and the current pointer, and allocate a new object for the new node. Which is more of an overhead per item.
 
Don't MAKE me come back there with this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic