Why is there no SortedList in Java

Question

In Java there are the SortedSet and SortedMap interfaces  Both belong to the Java 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

User · Answer

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.
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.

User · Answer

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

User · Answer

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

User · Answer

Another point is the time complexity of insert operations. For a list insert, one expects a complexity of O(1). But this could not be guaranteed with a sorted list.

And the most important point is that lists assume nothing about their elements. For example, you can make lists of things that do not implement equals or compare.

User · Answer

Since all lists are already  sorted  by the order the items were added  FIFO ordering   you can  resort  them with another order  including the natural ordering of elements  using java util Collections sort     EDIT   Lists as data structures are based in what is interesting is the ordering in which the items where inserted   Sets do not have that information   If you want to order by adding time  use List  If you want to order by other criteria  use SortedSet

User · Answer

I think all the above do not answer this question due to following reasons,

Since same functionality can be achieved by using other collections such as TreeSet, Collections, PriorityQueue..etc (but this is an alternative which will also impose their constraints i.e. Set will remove duplicate elements. Simply saying even if it does not impose any constraint, it does not answer the question why SortedList was not created by java community)
Since List elements do not implements compare/equals methods (This holds true for Set & Map also where in general items do not implement Comparable interface but when we need these items to be in sorted order & want to use TreeSet/TreeMap,items should implement Comparable interface)
Since List uses indexing & due to sorting it won't work (This can be easily handled introducing intermediate interface/abstract class)

but none has told the exact reason behind it & as I believe these kind of questions can be best answered by java community itself as it will have only one & specific answer but let me try my best to answer this as following,

As we know sorting is an expensive operation and there is a basic difference between List & Set/Map that List can have duplicates but Set/Map can not. This is the core reason why we have got a default implementation for Set/Map in form of TreeSet/TreeMap. Internally this is a Red Black Tree with every operation (insert/delete/search) having the complexity of O(log N) where due to duplicates List could not fit in this data storage structure.

Now the question arises we could also choose a default sorting method for List also like MergeSort which is used by Collections.sort(list) method with the complexity of O(N log N). Community did not do this deliberately since we do have multiple choices for sorting algorithms for non distinct elements like QuickSort, ShellSort, RadixSort...etc. In future there can be more. Also sometimes same sorting algorithm performs differently depending on the data to be sorted. Therefore they wanted to keep this option open and left this on us to choose. This was not the case with Set/Map since O(log N) is the best sorting complexity.

User · Answer

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

User · Answer

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

User · Answer

For any newcomers  as of April 2015  Android now has a SortedList class in the support library  designed specifically to work with RecyclerView  Here s the blog post about it

User · Answer

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 lt T gt  instead  It implements SortedSet and NavigableSet interfaces and works as you d probably expect from a list   TreeSet lt String gt  set   new TreeSet lt String gt     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 lt T gt    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 lt String gt  strings   new ArrayList lt String gt    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 lt string gt  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 lt E gt  and Collection lt E gt  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 lt String gt  strings   new ArrayList lt String gt    strings add  lol    strings add  cat     PriorityQueue lt String gt  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 lt E gt  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 lt E gt  extends AbstractList lt E gt         private ArrayList lt E gt  internalList   new ArrayList lt E gt             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

User · Answer

In case you are looking for a way to sort elements, but also be able to access them by index in an efficient way, you can do the following:

Use a random access list for storage (e.g. ArrayList)
Make sure it is always sorted

Then to add or remove an element you can use Collections.binarySearch to get the insertion / removal index. Since your list implements random access, you can efficiently modify the list with the determined index.

Example:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}

User · Answer

Set and Map are non-linear data structure. List is linear data structure.

The tree data structure SortedSet and SortedMap interfaces implements TreeSet and TreeMap respectively using used Red-Black tree implementation algorithm. So it ensure that there are no duplicated items (or keys in case of Map).

List is already maintains an ordered collection and index-based data structure, trees are no index-based data structures.
Tree by definition cannot contain duplicates.
In List we can have duplicates, so there is no TreeList(i.e. no SortedList).
List maintains elements in insertion order. So if we want to sort the list we have to use java.util.Collections.sort(). It sorts the specified list into ascending order, according to the natural ordering of its elements.

[java] Why is there no SortedList in Java?

The answer is

JavaFX `SortedList`

Examples related to java

Examples related to sorting

Examples related to collections

Tags