title: Sorted array list in Java
body: <p>I'm baffled that I can't find a quick answer to this.  I'm essentially looking for a datastructure in Java which implements the <code>java.util.List</code> interface, but which stores its members in a sorted order.  I know that you can use a normal <code>ArrayList</code> and use <code>Collections.sort()</code> on it, but I have a scenario where I am occasionally adding and often retrieving members from my list and I don't want to have to sort it every time I retrieve a member in case a new one has been added.  Can anyone point me towards such a thing which exists in the JDK or even 3rd party libraries?</p>
  
  <p><strong>EDIT</strong>:  The datastructure will need to preserve duplicates.</p>
  
  <p><strong>ANSWER's SUMMARY</strong>:  I found all of this very interesting and learned a lot.  Aioobe in particular deserves mention for his perseverance in trying to achieve my requirements above (mainly a sorted java.util.List implementation which supports duplicates).  I have accepted his answer as the most accurate for what I asked and most thought provoking on the implications of what I was looking for even if what I asked wasn't exactly what I needed.  </p>
  
  <p>The problem with what I asked for lies in the List interface itself and the concept of optional methods in an interface.  To quote the javadoc:</p>
  
  <blockquote>
    <p>The user of this interface has precise control over where in the list each element is inserted.</p>
  </blockquote>
  
  <p>Inserting into a sorted list doesn't have precise control over insertion point.  Then, you have to think how you will handle some of the methods.  Take <code>add</code> for example:</p>
  
  <blockquote>
    <p>public boolean add(Object o)</p>
  
  <pre><code> Appends the specified element to the end of this list (optional operation).
  </code></pre>
  </blockquote>
  
  <p>You are now left in the uncomfortable situation of either
  1) Breaking the contract and implementing a sorted version of add
  2) Letting <code>add</code> add an element to the end of the list, breaking your sorted order
  3) Leaving <code>add</code> out (as its optional) by throwing an <code>UnsupportedOperationException</code> and implementing another method which adds items in a sorted order.</p>
  
  <p>Option 3 is probably the best, but I find it unsavory having an add method you can't use and another sortedAdd method which isn't in the interface.</p>
  
  <p>Other related solutions (in no particular order):</p>
  
  <ul>
  <li><a href="http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html" rel="noreferrer">java.util.PriorityQueue</a> which is probably closest to what I needed than what I asked for.  A queue isn't the most precise definition of a collection of objects in my case, but functionally it does everything I need it to. </li>
  <li><a href="http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html" rel="noreferrer">net.sourceforge.nite.util.SortedList</a>.  However, this implementation breaks the contract of the List interface by implementing the sorting in the <code>add(Object obj)</code> method and bizarrely has a no effect method for <code>add(int index, Object obj)</code>.  General consensus suggests <code>throw new UnsupportedOperationException()</code> might be a better choice in this scenario.</li>
  <li><a href="http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/TreeMultiset.html" rel="noreferrer">Guava's TreeMultiSet</a> A set implementation which supports duplicates</li>
  <li><a href="http://publicobject.com/glazedlists/glazedlists-1.7.0/api/ca/odell/glazedlists/SortedList.html" rel="noreferrer">ca.odell.glazedlists.SortedList</a>  This class comes with the caveat in its javadoc: <code>Warning: This class breaks the contract required by List</code></li>
  </ul>