Why Is There No Sortedlist in Java

Why is there no SortedList in Java?

List iterators guarantee first and foremost that you get the list's elements in the internal order of the list (aka. insertion order). More specifically it is in the order you've inserted the elements or on how you've manipulated the list. Sorting can be seen as a manipulation of the data structure, and there are several ways to sort the list.

I'll order the ways in the order of usefulness as I personally see it:

1. Consider using `Set` or `Bag` collections instead

NOTE: I put this option at the top because this is what you normally want to do anyway.

A sorted set automatically sorts the collection at insertion, meaning that it does the sorting while you add elements into the collection. It also means you don't need to manually sort it.

Furthermore if you are sure that you don't need to worry about (or have) duplicate elements then you can use the TreeSet<T> instead. It implements SortedSet and NavigableSet interfaces and works as you'd probably expect from a list:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

If you don't want the natural ordering you can use the constructor parameter that takes a Comparator<T>.

Alternatively, you can use Multisets (also known as Bags), that is a Set that allows duplicate elements, instead and there are third-party implementations of them. Most notably from the Guava libraries there is a TreeMultiset, that works a lot like the TreeSet.

2. Sort your list with `Collections.sort()`

As mentioned above, sorting of Lists is a manipulation of the data structure. So for situations where you need "one source of truth" that will be sorted in a variety of ways then sorting it manually is the way to go.

You can sort your list with the java.util.Collections.sort() method. Here is a code sample on how:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Using comparators

One clear benefit is that you may use Comparator in the sort method. Java also provides some implementations for the Comparator such as the Collator which is useful for locale sensitive sorting strings. Here is one example:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Sorting in concurrent environments

Do note though that using the sort method is not friendly in concurrent environments, since the collection instance will be manipulated, and you should consider using immutable collections instead. This is something Guava provides in the Ordering class and is a simple one-liner:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Wrap your list with `java.util.PriorityQueue`

Though there is no sorted list in Java there is however a sorted queue which would probably work just as well for you. It is the java.util.PriorityQueue class.

Nico Haase linked in the comments to a related question that also answers this.

In a sorted collection you most likely don't want to manipulate the internal data structure which is why PriorityQueue doesn't implement the List interface (because that would give you direct access to its elements).

Caveat on the `PriorityQueue` iterator

The PriorityQueue class implements the Iterable<E> and Collection<E> interfaces so it can be iterated as usual. However, the iterator is not guaranteed to return elements in the sorted order. Instead (as Alderath points out in the comments) you need to poll() the queue until empty.

Note that you can convert a list to a priority queue via the constructor that takes any collection:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Write your own `SortedList` class

NOTE: You shouldn't have to do this.

You can write your own List class that sorts each time you add a new element. This can get rather computation heavy depending on your implementation and is pointless, unless you want to do it as an exercise, because of two main reasons:

It breaks the contract that List<E> interface has because the add methods should ensure that the element will reside in the index that the user specifies.
Why reinvent the wheel? You should be using the TreeSet or Multisets instead as pointed out in the first point above.

However, if you want to do it as an exercise here is a code sample to get you started, it uses the AbstractList abstract class:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Note that if you haven't overridden the methods you need, then the default implementations from AbstractList will throw UnsupportedOperationExceptions.

Why there is no SortedList

First line in the List API says it is an ordered collection (also known as a sequence). If you sort the list you can't maintain the order, so there is no TreeList in Java. Probably that is the case you need to externally sort it as you have mentioned.

As API says Java List got inspired from Sequence and see the sequence properties http://en.wikipedia.org/wiki/Sequence_(mathematics)

It doesn't mean that you can't sort the list, but Java strict to his definition and doesn't provide sorted versions of lists by default.

Sorted List in java like TreeMap or SortedSet

The purpose of having a list is that they should maintain the order of the elements in which they were added. So, I believe there is no such List implementation in which the elements are sorted as they are added.

You can use Collections.sort() method to sort the list any time.

A good Sorted List for Java

It seems that you want a list structure with very fast removal and random access by index (not by key) times. An ArrayList gives you the latter and a HashMap or TreeMap give you the former.

There is one structure in Apache Commons Collections that may be what you are looking for, the TreeList. The JavaDoc specifies that it is optimized for quick insertion and removal at any index in the list. If you also need generics though, this will not help you.