Why is there no SortedList in Java?

Question

In Java there are the SortedSet and SortedMap interfaces. Both belong to Java's standard Collections framework and provide a sorted way to access the elements.

However, in my understanding there is no SortedList in Java. You can use java.util.Collections.sort() to sort a list.

Any idea why it is designed like that?

Answer 1

Think of it like this: the List interface has methods like add(int index, E element), set(int index, E element). The contract is that once you added an element at position X you will find it there unless you add or remove elements before it.

If any list implementation would store elements in some order other than based on the index, the above list methods would make no sense.

Answer 2

Because the concept of a List is incompatible with the concept of an automatically sorted collection. The point of a List is that after calling list.add(7, elem), a call to list.get(7) will return elem. With an auto-sorted list, the element could end up in an arbitrary position.

Answer 3

JavaFX SortedList

Though it took a while, Java 8 does have a sorted List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

As you can see in the javadocs, it is part of the JavaFX collections, intended to provide a sorted view on an ObservableList.

Update: Note that with Java 11, the JavaFX toolkit has moved outside the JDK and is now a separate library. JavaFX 11 is available as a downloadable SDK or from MavenCentral. See https://openjfx.io

Answer 4

Consider using indexed-tree-map . It's an enhanced JDK's TreeSet that provides access to element by index and finding the index of an element without iteration or hidden underlying lists that back up the tree. The algorithm is based on updating weights of changing nodes every time there is a change.