title: Difference between ArrayList and LinkedList in Java - the whys for performance
body: <p>I thought I understood the difference between ArrayList and LinkedList theoretically pretty well. However, its the first time, I put it to a little test, and the tests came out, well different to my expectations. </p>
  
  <p>Expectations : </p>
  
  <ol>
  <li><p>Arraylist will be slower than LinkedList when inserting at the
  beginning, since it has to "shift" the elements, for linkedlist, its
  just updating 2 references.</p>
  
  <p>Reality : came out to be same on most iterations. For a select few
  iterations, it was slower. </p></li>
  <li><p>Arraylist will be slower than LinkedList when deleting at the beginning, since it has to "shift" the elements, for Linkedlist, its just nullifying one element.</p>
  
  <p>Reality : Performance was same when deleting from beg.</p></li>
  </ol>
  
  <p>Test Case : 1,000,000 elements</p>
  
  <pre><code>public static void main(String[] args) {
      int n = 1000000;
  
      List arrayList = new ArrayList(n+10);
      long milis = System.currentTimeMillis();
      for(int i= 0 ;i&lt;n;i++){
          arrayList.add(i);
      }
      System.out.println("insert arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      List linkedList = new LinkedList();
      milis = System.currentTimeMillis();
      for(int i= 0 ;i&lt;n;i++){
          linkedList.add(i);
      }
      System.out.println("insert linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      //System.out.println("Adding at end");
      milis = System.currentTimeMillis();
      arrayList.add(n-5,n+1);
      System.out.println("APPEND arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.add(n-5,n+1);
      System.out.println("APPEND linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      //add at front
      milis = System.currentTimeMillis();
      arrayList.add(0,0);
      System.out.println("INSERT BEG arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.add(0,0);
      System.out.println("INSERT BEG linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      //add at middle
      milis = System.currentTimeMillis();
      arrayList.add(n/2,n/2);
      System.out.println("INSERT MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.add(n/2,n/2);
      System.out.println("INSERT MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      //get from front, mid, end
      milis = System.currentTimeMillis();
      arrayList.get(0);
      System.out.println("get front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.get(0);
      System.out.println("get front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      arrayList.get(n/2);
      System.out.println("get MIDDLE arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.get(n/2);
      System.out.println("get MIDDLE linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      arrayList.get(n-4);
      System.out.println("get last arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.get(n-4);
      System.out.println("get last linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      //delete from front, mid, end.
      milis = System.currentTimeMillis();
      arrayList.remove(0);
      System.out.println("del front arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.remove(0);
      System.out.println("del front linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      arrayList.remove(n/2);
      System.out.println("del mid arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.remove(n/2);
      System.out.println("del mid linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      arrayList.remove(n-4);
      System.out.println("del end arraylist takes "+(System.currentTimeMillis()-milis)+" ms");
  
      milis = System.currentTimeMillis();
      linkedList.remove(n-4);
      System.out.println("del end linkedlist takes "+(System.currentTimeMillis()-milis)+" ms");
  
  }
  </code></pre>
  
  <p><strong>Output Log</strong></p>
  
  <pre><code>insert arraylist takes 141 ms
  insert linkedlist takes 312 ms
  APPEND arraylist takes 0 ms
  APPEND linkedlist takes 0 ms
  INSERT BEG arraylist takes 0 ms
  INSERT BEG linkedlist takes 0 ms
  INSERT MIDDLE arraylist takes 0 ms
  INSERT MIDDLE linkedlist takes 0 ms
  get front arraylist takes 0 ms
  get front linkedlist takes 0 ms
  get MIDDLE arraylist takes 0 ms
  get MIDDLE linkedlist takes 16 ms
  get last arraylist takes 0 ms
  get last linkedlist takes 0 ms
  del front arraylist takes 0 ms
  del front linkedlist takes 0 ms
  del mid arraylist takes 0 ms
  del mid linkedlist takes 15 ms
  del end arraylist takes 0 ms
  del end linkedlist takes 0 ms
  </code></pre>
  
  <p>So what's the reason? JDK 1.6 used.</p>
  
  <p>EDIT : After using System.nanotime(), it did give me answers as I expected. Agreed, its only a single trial, and should be averaged.</p>
  
  <pre><code>insert arraylist takes 137076082 ns
  insert linkdlist takes 318985917 ns
  APPEND arraylist takes 69751 ns
  APPEND linkdlist takes 98126 ns
  **INSERT BEG arraylist takes 2027764 ns
  INSERT BEG linkdlist takes 53522 ns**
  INSERT MIDDLE arraylist takes 1008253 ns
  INSERT MIDDLE linkdlist takes 10395846 ns
  get front arraylist takes 42364 ns
  get front linkdlist takes 77473 ns
  get MIDDLE arraylist takes 39499 ns
  get MIDDLE linkdlist takes 9645996 ns
  get last arraylist takes 46165 ns
  get last linkdlist takes 43446 ns
  **del front arraylist takes 1720329 ns
  del front linkdlist takes 108063 ns**
  del mid arraylist takes 1157398 ns
  del mid linkdlist takes 11845077 ns
  del end arraylist takes 54149 ns
  del end linkdlist takes 49744 ns
  </code></pre>