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?

Because your benchmark is flawed. http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — assylias, Oct 16 '14 at 12:20
Did you try to swap them? First the arraylist and than the linkedlist? — Vincent Beltman, Oct 16 '14 at 12:21
if you do vice versa i.e. ArrayList first and then LL? Also pass on the length to ArrayList constructor and see what happens? — SMA, Oct 16 '14 at 12:22
Nothing changes. You could run them separately in two different programms. — Tony, Oct 16 '14 at 12:23

score 2 · Accepted Answer · edited May 23 '17 at 12:11

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.

All in one link by [Oracle Wiki](https://wikis.oracle.com/display/HotSpotInternals/MicroBenchmarks). See Relevant links too.. — dasrohith, Oct 16 '14 at 12:38

Filling ArrayList vs LinkedList

1 Answers1