title: Is LinkedList really faster than ArrayList in the case of insertion in the middle of list?
body: <p><em>- What is the difference between <code>LinkedList</code> and <code>ArrayList</code>? When is it preferable to use a <code>LinkedList</code>?</em></p>
  
  <p>I think every Java developer has heard this question at interview at least once.</p>
  
  <p><em>- Linked list is preferable if you want to be able to insert items in the middle of the list.</em></p>
  
  <p>It is a common answer to this question. Everybody knows it. Every time you ask a question about the difference between List implementations you get such answers as:</p>
  
  <blockquote>
    <p>When should I use LinkedList? When do you need efficient removal in between elements or at the start?</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/a/322730/1782379">From here</a></p>
  
  <blockquote>
    <p>Forgot to mention insertion costs. In a LinkedList, once you have the correct position, insertion costs <code>O(1)</code>, while in an ArrayList it goes up to <code>O(n)</code> - all elements past the insertion point must be moved.</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/a/322742/1782379">From here</a></p>
  
  <blockquote>
    <p>Linked lists are preferable over arrays when you want to be able to insert items in the middle of the list (such as a priority queue).</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/a/393578/1782379">From here</a></p>
  
  <blockquote>
    <p>ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. LinkedList just has to manipulate a couple of references.</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/a/10656509/1782379">From here</a></p>
  
  <p>And more...</p>
  
  <p>But have you ever tried to reproduce it by yourself? I tried yesterday and got these results:</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  
  public class Test {
      public static void main(String... args) {
          final int MAX_VAL = 10000;
          List&lt;Integer&gt; linkedList = new LinkedList&lt;Integer&gt;();
          List&lt;Integer&gt; arrayList = new ArrayList&lt;Integer&gt;();
          for(int i = 0; i &lt; MAX_VAL; i++) {
              linkedList.add(i);
              arrayList.add(i);
          }
          long time = System.nanoTime();
          for(int i = 0; i &lt; MAX_VAL; i++) {
              linkedList.add(MAX_VAL/2, i);
          }
          System.out.println("LL time: " + (System.nanoTime() - time));
          time = System.nanoTime();
          for(int i = 0; i &lt; MAX_VAL; i++) {
              arrayList.add(MAX_VAL/2, i);
          }
          System.out.println("AL time: " + (System.nanoTime() - time));
      }
  }
  </code></pre>
  
  <p><strong>Output:</strong></p>
  
  <blockquote>
    <p>LL time: 114098106</p>
    
    <p>AL time: 24121889</p>
  </blockquote>
  
  <p>So what is it? Why does LinkedList suck so much? Maybe we should try the remove operation instead of add? Ok, let's try:</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  
  public class Test {
      public static void main(String... args) {
          final int MAX_VAL = 10000;
          List&lt;Integer&gt; linkedList = new LinkedList&lt;Integer&gt;();
          List&lt;Integer&gt; arrayList = new ArrayList&lt;Integer&gt;();
          for(int i = 0; i &lt; MAX_VAL; i++) {
              linkedList.add(i);
              arrayList.add(i);
          }
          long time = System.nanoTime();
          for(int i = 0; i &lt; MAX_VAL/2; i++) {
              linkedList.remove(MAX_VAL/2);
          }
          System.out.println("LL time: " + (System.nanoTime() - time));
          time = System.nanoTime();
          for(int i = 0; i &lt; MAX_VAL/2; i++) {
              arrayList.remove(MAX_VAL/2);
          }
          System.out.println("AL time: " + (System.nanoTime() - time));
      }
  }
  </code></pre>
  
  <p><strong>Output:</strong></p>
  
  <blockquote>
    <p>LL time: 27581163</p>
    
    <p>AL time: 3103051</p>
  </blockquote>
  
  <p>Oh, ArrayList is still faster than LinkedList. What is the reason? Was this myth busted? Or maybe I'm wrong?</p>
  
  <p><img src="https://i.stack.imgur.com/7cBdM.jpg" alt="enter image description here"></p>