title: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?
body: <p>Taken from the <a href="http://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html" rel="noreferrer">Apache <code>TreeList</code> doc</a>:</p>
  
  <blockquote>
    <p>The following relative performance statistics are indicative of this
    class:</p>
  
  <pre><code>             get  add  insert  iterate  remove
   TreeList       3    5       1       2       1
   ArrayList      1    1      40       1      40
   LinkedList  5800    1     350       2     325
  </code></pre>
  </blockquote>
  
  <p>It goes on to say:</p>
  
  <blockquote>
    <p><code>LinkedList</code> is rarely a good choice of implementation. <code>TreeList</code> is almost always a good replacement for it, although it does use sligtly more memory.</p>
  </blockquote>
  
  <p>My questions are:</p>
  
  <ul>
  <li><p>What is with the <code>ArrayList</code> <code>add</code>,
  <code>insert</code>, and <code>remove</code> times crushing
  <code>LinkedList</code>? Should we expect, for
  one, that real-world insertion and removal cases
  greatly favor <code>ArrayList</code>?</p></li>
  <li><p>Does this <code>TreeList</code> simply put the nail in the coffin of the venerable <code>LinkedList</code>?</p></li>
  </ul>
  
  <p>I am tempted to conclude they have amortized or ignored <code>ArrayList</code>'s growing pains, and have not taken into consideration the insertion and removal times for an item in a <code>LinkedList</code> that has already been located.</p>