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?
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:
Set or Bag collections insteadNOTE: 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.
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"
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);
In Java 8+, more simply call List#sort.
strings.sort( usCollator ) ;
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);
java.util.PriorityQueueThough 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).
PriorityQueue iteratorThe 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"
SortedList classNOTE: 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:
List<E> interface has because the add methods should ensure that the element will reside in the index that the user specifies.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.
Integer maxVal = prioQueue.peek(prioQueue.size() - 1);. Secondly if you're intending to use the PriorityQueue simply as a sorted list, it will sound less intuitive to see PriorityQueue in the code than it would have been to see SortedList, if such a data structure existed. –
Calamander Collections.sort() even lets you define the compare function that is used to sort, by using a Comparator object. –
Kra put(). Am I confused? –
Dulosis Map is not the same thing as the index for a List. Using put() there is no way for sure that putting something in a lower number and something in a higher number will come in the order you want when you iterate on the entrySet of the map (i.e. unless you sort the entrySet by the key). –
Ohmmeter ArrayList) and you know that it is already sorted before adding a new item, you can use Collections.binarySearch to get the index where the new item should be inserted. –
Scala 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.
list.get(n) operation will be deterministic, meaning it will always return the same element at position n as long as the list is not modified. I don't agree that the "concept of a List" requires that to be the insertion order. Yes, the List interface does feature list.add(index, element) method which doesn't make sense for a sorted collection, but it's optional according to the docs. –
Transpacific 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.
lists are already sorted by its order is a bit misleading. Yes, Lists have a default FIFO ordering (the order the items were added), but reading that sentence I was thinking about the natural ordering of elements, which is kinda different thing. I will propose an edit –
Subhuman 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 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.SortedListThough 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
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.
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.
SortedSet of things that do not implement Comparable. See this TreeSet constructor. –
Calamander List interface doesn't guarantee any performance specifications on its methods. –
Rights ArrayList provides O(1) traversal time with O(1) access time once you're there. Linked lists provide O(n) traversal time with O(1) access time once you're there. Sorted structures typically provide O(log(n)) traversal time with O(1) access speed once you're there. Other operations may have different complexities, traversing aside. For example, insertion is O(n), O(1) and O(log(n)) for their respective implementations. –
Talca 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.
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);
}
}
(See a more complete implementation in this 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.
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.
https://github.com/geniot/indexed-tree-map
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 changed nodes every time there is a change.
We have Collections.sort(arr) method which can help to sort ArrayList arr. to get sorted in desc manner we can use Collections.sort(arr, Collections.reverseOrder())
Computational speaking, in simple lists, it is more expensive to insert ordered than insert without any order and then order after you are done inserting.
As discussed already, SortedList (aka SortedSequence) would break the expectations of users of a List that add(x) adds x to the list end, and add(i,x) adds x at position i, etc.
However these are optional operations of List according to the Java SE8 documentation, so there is no guarantee about them in any case: https://docs.oracle.com/javase/8/docs/api/java/util/List.html.
SortedList would be a useful collection if you wish to have a consistent sorted order imposed on a list throughout program processing, it also will enable faster search operations such as contains, indexOf, lastIndexOf, getCount, etc, although insertion will be slower. It can also be used to support the definition of a SortedOrderedSet (a unique-element sorted sequence, constructed using a HashSet and a SortedSequence).
Implementations of SortedSequence and SortedOrderedSet are provided as part of the AgileUML libraries: https://github.com/eclipse/agileuml/tree/master/libraries
© 2022 - 2024 — McMap. All rights reserved.
int diff = this.score - that.score;return (diff == 0) ? 1 : diff;As it's a smelly hack I would provide this as an anonymous constructor argument rather than having any implement Comparable. – Budworthset.add(X); Y = set.get(X);will surely return null. – TonjatonjesSetdoesn't implementget- note; I'd stated it's a smelly hack - the point I was trying to make is that my suggestion allows multiple identical values in aSetand does so onaddavoiding cost ofCollections.sort(List). This smelly hack fails for a number of scenarios, such ascontains- wasn't intended for use but conversion; strongly suspect it's quicker (WRT time-complexity for huge collections) to use this and then dump into a List with e.g.ArrayListconstructor oraddAll(unlikely better for big O memory) – Budworthget- but similar argument forcontains. Also, your comparator surely violates some contract, since compare(a,b) == 1 and compare(b,a) == 1, i.e., a > b and b > a. I'd at least go for consistency in the case of a.equals(b) by ordering on something else, maybe comparing System.identityHashCode values. – Tonjatonjes