title: List implementation that maintains ordering
body: <p>Is there an existing <code>List</code> implementation in Java that maintains order based on provided <code>Comparator</code>?</p>
  
  <p>Something that can be used in the following way:</p>
  
  <pre><code>Comparator&lt;T&gt; cmp = new MyComparator&lt;T&gt;();
  List&lt;T&gt; l = new OrderedList&lt;T&gt;(cmp);
  l.add(someT);
  </code></pre>
  
  <p>so that <code>someT</code> gets inserted such that the order in the list is maintained according to <code>cmp</code></p>
  
  <p>(On @andersoj suggestion I am completing my question with one more request)</p>
  
  <p>Also I want to be able to traverse the list in sorted order without removing the elements, i.e:</p>
  
  <pre><code>T min = Const.SMALLEST_T;
  for (T e: l) {
    assertTrue(cmp.compare(min, e) &gt;= 0);
    min = e;
  }
  </code></pre>
  
  <p>should pass.</p>
  
  <p>All suggestions are welcome (except telling me to use <code>Collections.sort</code> on the unordered full list), though, I would prefer something in <code>java.*</code> or eventually <code>org.apache.*</code> since it would be hard to introduce new libraries at this moment.</p>
  
  <p><strong><em>Note: (UPDATE4)</em></strong> I realized that implementations of this kind of list would have inadequate performance. There two general approaches:</p>
  
  <ol>
  <li>Use Linked structure (sort of) B-tree or similar</li>
  <li>Use array and insertion (with binary search)</li>
  </ol>
  
  <p>No 1. has problem with CPU cache misses 
  No 2. has problem with shifting elements in array.</p>
  
  <p><strong><em>UPDATE2:</em></strong>
  <code>TreeSet</code> does not work because it uses the provided comparator (<code>MyComparator</code>) to check for equality and based on it assumes that the elements are equal and exclude them. I need that comparator only for ordering, not "uniqueness" filtering (since the elements by their natural ordering are not equal)</p>
  
  <p><strong><em>UPDATE3:</em></strong>
  <code>PriorityQueue</code> does not work as <code>List</code> (as I need) because there is no way to traverse it in the order it is "sorted", to get the elements in the sorted order you have to remove them from the collection.</p>
  
  <p>UPDATE:</p>
  
  <p>Similar question: <br/>
  <a href="https://stackoverflow.com/questions/2661065/a-good-sorted-list-for-java">A good Sorted List for Java</a> <br/>
  <a href="https://stackoverflow.com/questions/4031572/sorted-array-list-in-java">Sorted array list in Java</a></p>