Java: Sorted List

Sometimes you might have the need for a Java list, that is sorted with every element insertion. If you use a sorted TreeSet, you are stuck with iterators, no random access for elements. If you use an ArrayList, you could call Collections.sort() after every add, but that's not necessarily efficient. Collection.sort() will have to check the order for every element. If your list is long, this might take time.

But here's the trick: if you know your list was already sorted before your insertion, there's no need to re-sort everything again. You can find the proper insertion point with a quick binary search, and insert the new element at the proper position. Voilà, your list is always sorted.

Surprisingly simple to do this in Java:

/** A LinkedList that efficiently sorts itself with every add.
 * 
 * @author apodehl
 *
 */
public class SortedList< T extends Comparable> extends LinkedList
{
  /** Adds this element to the list at the proper sorting position.
   * If the element already exists, don't do anything.
   */
  @Override
  public boolean add(T e)
  {
    if( size()==0 ) {
      
      return super.add(e);
    }
    else {
      
      // find insertion index
      int idx = -Collections.binarySearch(this, e)-1;
      
      if( idx < 0 ) {
        return true; // already added
      }
      
      // add at this position
      super.add(idx, e);
      return true;
    }
  }
}