1

I am starting to see more and more benchmarks that demonstrate ArrayList crushing LinkedList in terms of performance for 'large' inserts example below: Gluelist

Adding(1M) Elements (5 Tests Avg.)

LinkedList: 174.8 milliseconds
ArrayList:  76.4 milliseconds
GlueList:   39.2 milliseconds

Adding(10M) Elements (5 Tests Avg.)

LinkedList: 8975.6 milliseconds
ArrayList:  4118.2 milliseconds
GlueList:   3320.1 milliseconds

I ran similar tests on a RHEL 7.2 with JDK8.latest and saw similar results. I am under the impression that a LinkedList insert is O(1) even in the worst case and an ArrayList takes > O(1) because of the copy operation (I realize that we can discuss amortized costs, but that is out of scope). My question is this: How is LinkedList performing worse than ArrayList given that ArrayList forces a copy operation when capacity is nearly reached?

Woot4Moo
  • 23,987
  • 16
  • 94
  • 151
  • Guess: `System.arraycopy` is an efficient, packed `memcpy`, while the `LinkedList` inserts require lots of allocations and break cache locality. – chrylis -cautiouslyoptimistic- Aug 12 '16 at 16:03
  • Possible duplicate of [When to use LinkedList over ArrayList?](http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist)? – Janez Kuhar Aug 12 '16 at 16:24
  • "I realize that we can discuss amortized costs, but that is out of scope)" - you're *measuring* amortized costs right there. Why exclude it from the discussion? – the8472 Aug 13 '16 at 23:58

3 Answers3

1

They have the same big O but that doesn't tell you about the constant relationship. It tells you how they behave on an idealised machine, not a real machine.

LinkedList allocates and uses more memory. It creates a 24 byte object per node where as an ArrayList uses 4 bytes (usually) per reference and creates far less objects.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
0

Big O doesn't really help you there. It tells you in what direction growth goes, but it doesn't give you absolute numbers.

ArrayList uses arrays, with highly optimized native System.arrayCopy() calls.

LinkedLists have to create a wrapper object for every single node and store pointers to the next and previous nodes in it. That takes time.

ArrayList does not create a single object when inserting, unless it resizes the array, which doesn't happen that often.

Sean Patrick Floyd
  • 292,901
  • 67
  • 465
  • 588
0

The question is also: how did they test the performance?

Writing good microbenchmarks is not easy.

Here are some good articles:

http://www.ibm.com/developerworks/java/library/j-benchmark1/index.html

http://www.ibm.com/developerworks/java/library/j-benchmark2/index.html

http://ellipticgroup.com/html/benchmarkingArticle.html

Puce
  • 37,247
  • 13
  • 80
  • 152