title: ArrayList Vs LinkedList
body: <p>I was following a <a href="https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/322742#322742">previous post</a> on this that says:</p>
  <blockquote>
  <p>For LinkedList</p>
  <ul>
  <li>get is O(n)</li>
  <li>add is O(1)</li>
  <li>remove is O(n)</li>
  <li>Iterator.remove is O(1)</li>
  </ul>
  <p>For ArrayList</p>
  <ul>
  <li>get is O(1)</li>
  <li>add is O(1) amortized, but O(n) worst-case since the array must be resized and copied</li>
  <li>remove is O(n)</li>
  </ul>
  </blockquote>
  <p>So by looking at this, I concluded that if I've to do just sequential insert in my collection for say 5000000 elements, <code>LinkedList</code> will outclass <code>ArrayList</code>.</p>
  <p>And if I've to just fetch the elements from collection by iterating i.e. not grabbing the element in middle, still <code>LinkedList</code> will outclass <code>ArrayList</code>.</p>
  <p>Now to verify my above two statements, I wrote below sample program… But I'm surprised that my above statements were proven wrong.</p>
  <p><code>ArrayList</code> outclassed <code>Linkedlist</code> in both the cases. It took less time than <code>LinkedList</code> for adding as well as fetching them from Collection. Is there anything I'm doing wrong, or the initial statements about <code>LinkedList</code> and <code>ArrayList</code> does not hold true for collections of size 5000000?</p>
  <p>I mentioned size, because if I reduce the number of elements to 50000, <code>LinkedList</code> performs better and initial statements hold true.</p>
  <pre class="lang-java prettyprint-override"><code>long nano1 = System.nanoTime();
  
  List&lt;Integer&gt; arr = new ArrayList();
  for (int i = 0; i &lt; 5000000; i++) {
      arr.add(i);
  }
  System.out.println(System.nanoTime() - nano1);
  
  for (int j : arr) {
      // Do nothing
  }
  System.out.println(System.nanoTime() - nano1);
  
  long nano2 = System.nanoTime();
  
  List&lt;Integer&gt; arrL = new LinkedList();
  for (int i = 0; i &lt; 5000000; i++) {
      arrL.add(i);
  }
  System.out.println(System.nanoTime() - nano2);
  
  for (int j : arrL) {
      // Do nothing
  }
  System.out.println(System.nanoTime() - nano2);
  </code></pre>