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?
This question is related to
java
sorting
collections
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.
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.
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
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
.
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
.
I think all the above do not answer this question due to following reasons,
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.
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.
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.
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.
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:
ArrayList
)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);
}
}
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.List
we can have duplicates, so there is no TreeList
(i.e. no SortedList
).java.util.Collections.sort()
. It sorts the specified list into ascending order, according to the natural ordering of its elements.Source: Stackoverflow.com