CODEWITHSUNDEEP
javaperformancearraylistlinked-list
Woot4Moo
Woot4Moo

Reputation: 24316

JDK8 performance of ArrayList compared to LinkedList

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?

Upvotes: 1

Views: 116

Answers (3)

Peter Lawrey
Peter Lawrey

Reputation: 533442

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.

Upvotes: 1

Puce
Puce

Reputation: 38122

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

Upvotes: 0

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298818

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.

Upvotes: 0

Related Questions