I was always wondering if it is a good idea to use LinkedList if the number of elements in the list is unknown. So I decided to test it. Program is pretty short here:
https://github.com/artgo/TestLists/blob/master/src/TestLists.java
I run this test on Ubuntu 12 64bit, Oracle Java 7 64bit, 12Gb RAM, i7 920 processor.
It won’t run, of course without Java option set to -Xmx10000m, with which I’ve got:
ArrayList : 17_781_152_915
LinkedList: 85_340_498_650
It was slow and definitely it is not your server configuration, isn’t it?
So going further I updated Java 7, 64bit options to:
-Xmx10000m -Xms10000m -Xmn9000m -d64 -Xnoclassgc -XX:+AggressiveOpts
(Max memory 10Gm min memory 10G, newly allocated memory 9G, 64 bit operations, no garbage collection for classes, aggressive optimization is on)
And got:
ArrayList : 1_442_938_558
LinkedList: 2_105_144_104
So, basically, results are pretty obvious and expected: ArrayList requests memory in chunks, while LinkedIn element by element. Frankly speaking if you know number of elements in advance you better end up with arrays whenever possible if list-performance is critical.
When would you use LinkedList then? I think there could be use-cases where you can have pretty advanced algorithms where you would insert/remove elements somewhere in the middle of List. Queues might work pretty well. But those are pretty rare, aren’t they?
Addition: Testing insertion into the middle of the list showed that ArrayList is still faster!
I updated these lines:
linkedList.add(i>>1, ints[i]);
arrayList.add(i>>1, ints[i]);
And got the following results:
ArrayList : 76_381_256_439
LinkedList: 1075_967_955_689
Artem's Blog 