Filling ArrayList vs LinkedList

Question

I have been thinking that LinkedList fills faster than ArrayList. As I know ArrayList is based on simple array with limited length(constant). So every time array is out of range, new array with higher range will be created. LinkedList is much simpler. It hasn't got any limit (except for memory), so it should be filled faster. But I run next code:

 public static void main(String[] args) {
 int length = 7000000;
 List<Integer> list = new LinkedList<Integer>();
 long oldTime = System.currentTimeMillis();
 for (int i = 0; i < length; i++) {
 list.add(i);
 }
 System.out.println("LinkedList fill: " + (System.currentTimeMillis() - oldTime));
 list = new ArrayList<Integer>();
 oldTime = System.currentTimeMillis();
 for (int i = 0; i < length; i++) {
 list.add(i);
 }
 System.out.println("ArrayList fill: " + (System.currentTimeMillis() - oldTime));
 }

The output is:

LinkedList fill: 3936
ArrayList fill: 628

Why so?

• assylias: Because your benchmark is flawed. stackoverflow.com/questions/504103/…
• Vincent Beltman: Did you try to swap them? First the arraylist and than the linkedlist?
• SMA: if you do vice versa i.e. ArrayList first and then LL? Also pass on the length to ArrayList constructor and see what happens?
• Tony: Nothing changes. You could run them separately in two different programms.

Answer 1

You can't really benchmark performance like that in Java. See How do I write a correct micro-benchmark in Java? for a more detailed explanations of the many things that can go wrong.

If I test your code with jmh I get the following results:

Benchmark Mode Samples Score Error Units
c.a.p.SO26404256.arrayList avgt 5 7.661 ± 0.672 ms/op
c.a.p.SO26404256.linkedList avgt 5 9.675 ± 1.213 ms/op

So filling a LinkedList seems to be slightly slower than filling an arrayList, but the difference is a lot less than your test indicated.

As for the reason for the difference, it is probably because each element of a LinkedList is wrapped in a Node: that means more object creations and more garbage collections. And the penalty due to array copies in ArrayList is probably less than you think because they are highly optimised.

• dasrohith: All in one link by Oracle Wiki. See Relevant links too..