Why getting the different output regarding the time when inserting to LinkedList and ArrayList

Question

I was working with LinkedList and ArrayList and I know the concept of adding the elements into the ArrayList and LinkedList, but I when run code of checking the time of insertion then I got different insertion time again and again, for both LinkedList and ArrayList.

Sometimes the insertion time of LinkedList comes better and vice versa, how is it happening exactly, can any one please tell me.

import java.util.ArrayList;

public class Time
   {

   public static void main(String args[])

    {

       int n=100000;
       long milis = System.currentTimeMillis();
       ArrayList obj=new ArrayList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert arraylist takes "
            +(System.currentTimeMillis()-milis)+" ms");
}

  }

Output of this program is

1)insert arraylist takes 13 ms 2)insert arraylist takes 9 ms

The second code is

 import java.util.LinkedList;

  public class Time1 
  {

        public static void main(String args[])
{
      int n=100000;
      long milis = System.currentTimeMillis();
      LinkedList obj=new LinkedList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert linklist takes "
           +(System.currentTimeMillis()-milis)+" ms");
}

 }

The output of this

1)insert linklist takes 8 ms

2)insert linklist takes 17 ms

Please paste the output of both the programs for convenience. — Ankur Shanbhag, May 31 '13 at 11:38
Micro-benchmarks are almost impossible to write correctly. You can read answers to [this question](http://stackoverflow.com/q/504103/1343161) for some answers why. — Keppil, May 31 '13 at 11:38
That is a very small test, you should at least run the same test N times with the error becoming smaller as N increases. Also take out the object allocation out of the test. — arynaq, May 31 '13 at 11:40

score 1 · Accepted Answer · answered May 31 '13 at 12:08

Generally speaking, a linked list will be more efficient at adding and removing elements anywhere but the end of the list, but will be much slower at looking up an arbitrary index in the list. To add or remove an element in any location a LinkedList just has to change a couple of references, but in an ArrayList everything after that point needs shifting. In terms of looking up an arbitrary index, an ArrayList simply jumps to that location in memory, a LinkedList must traverse through each item up to that point.

That's the trivial example. There's two main reasons why you're not seeing this above:

Firstly, microbenchmarks suck at the best of times, but especially in a language like Java where you have a JIT that will "warm up" and alter performance in the process. Either benchmark it in a real world scenario, or you can pretty much wave goodbye to any real performance metric.
Secondly, ArrayList has seen lots of optimisation over the years, to the point that I've even noticed it performing faster in certain cases where you'd classically expect LinkedList to win out.

Personally, I'd stick ArrayList in the real world application I'm using, not a micro benchmark, and measure the performance. If the performance was unacceptable, I'd switch the implementation to LinkedList (which should be a one line change) and then run a benchmark again to check. Without those checks, it's nigh on impossible to say what will perform better in your scenario.

Good answer, but LinkedLists can traverse backwards too meaning that the worst insertion/removal point is the middle of the list rather than the end. — Numeron, Jul 31 '13 at 01:35

score 0 · Answer 2 · answered May 31 '13 at 14:28

0

You'll need to use obj in some way to avoid the hotspot optimizing away your whole for-loop.

answered May 31 '13 at 14:28

jontejj

2,800
1
25
27

score -1 · Answer 3 · answered May 31 '13 at 12:21

Everytime you start benchmarking java you have to be very sceptical about your results. Most of times your results will show different results which you could expect. There are too many factors which can affect performance in your programm. To make a correct benchmark you need deep understanding of JVM. The simpliest points I can name to you:

JIT warm up (your first benchmarking results usually will be much worse than later)
DCE aka Dead Code Elemination. This is not your case, but it's useful to know about it too

To make good benchmark with results which could be correctly interpreted, I recommend to look at Java Harness and carefully check and run all examples.

obj is never read so hotspot could potentially see that writing into obj could be optimized away. — jontejj, May 31 '13 at 14:29

Why getting the different output regarding the time when inserting to LinkedList and ArrayList

3 Answers3