title: How is LinkedList's add(int, E) of O(1) complexity?
body: <p>From the <a href="/questions/tagged/linked-list" class="post-tag" title="show questions tagged 'linked-list'" rel="tag">linked-list</a> tag wiki excerpt:</p>
  
  <blockquote>
    <p>A linked list is a data structure in which the elements contain
    references to the next (and optionally the previous) element. Linked
    lists offer <strong>O(1) insert and removal at any position</strong>, O(1) list
    concatenation, and O(1) access at the front (and optionally back)
    positions as well as O(1) next element access. Random access has O(N)
    complexity and is usually unimplemented.</p>
  </blockquote>
  
  <p><sup>(emphasis mine)</sup></p>
  
  <p>I was surprised to read this &ndash; how can the list <em>insert</em> at a random index with a lower complexity than simply <em>reading</em> that index?</p>
  
  <p>So I looked at <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java">the source code for <code>java.util.LinkedList</code></a>. The <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.add%28int%2Cjava.lang.Object%29"><code>add(int, E)</code> method</a> is:</p>
  
  <pre><code>public void add(int index, E element) {
      addBefore(element, (index==size ? header : entry(index)));
  }
  </code></pre>
  
  <p>The <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.addBefore%28java.lang.Object%2Cjava.util.LinkedList.Entry%29"><code>addBefore(E, Entry&lt;E&gt;</code> method</a> is simply pointer reassignment, but there's also the <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29"><code>entry(int)</code> method</a>:</p>
  
  <pre><code>if (index &lt; 0 || index &gt;= size)
          throw new IndexOutOfBoundsException("Index: "+index+
                                              ", Size: "+size);
      Entry&lt;E&gt; e = header;
      if (index &lt; (size &gt;&gt; 1)) {
          for (int i = 0; i &lt;= index; i++)
              e = e.next;
      } else {
          for (int i = size; i &gt; index; i--)
              e = e.previous;
      }
      return e;
  }
  </code></pre>
  
  <p>Even with the half-size optimization, the <code>for</code> loop in here (one or the other) seems to me a dead giveaway that this method (and thus <code>add(int, E)</code>) operates in a minimum worst-case scenario of O(n) time, and certainly not constant time.</p>
  
  <p>What am I missing? Am I misunderstanding the big-O notation?</p>