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 List
s 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 theadd
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 UnsupportedOperationException
s.
Sort Java Collection
Use a Comparator:
List<CustomObject> list = new ArrayList<CustomObject>();
Comparator<CustomObject> comparator = new Comparator<CustomObject>() {
@Override
public int compare(CustomObject left, CustomObject right) {
return left.getId() - right.getId(); // use your logic
}
};
Collections.sort(list, comparator); // use the comparator as much as u want
System.out.println(list);
Additionally, if CustomObject
implements Comparable
, then just use Collections.sort(list)
With JDK 8 the syntax is much simpler.
List<CustomObject> list = getCustomObjectList();
Collections.sort(list, (left, right) -> left.getId() - right.getId());
System.out.println(list);
Much simplier
List<CustomObject> list = getCustomObjectList();
list.sort((left, right) -> left.getId() - right.getId());
System.out.println(list);
Simplest
List<CustomObject> list = getCustomObjectList();
list.sort(Comparator.comparing(CustomObject::getId));
System.out.println(list);
Obviously the initial code can be used for JDK 8 too.
How to sort a Collection T ?
Collections by themselves do not have a predefined order, therefore you must convert them to
a java.util.List
. Then you can use one form of java.util.Collections.sort
Collection< T > collection = ...;
List< T > list = new ArrayList< T >( collection );
Collections.sort( list );
// or
Collections.sort( list, new Comparator< T >( ){...} );
// list now is sorted
Maintain sorted collection in java, with index access
None of the standard collections that come with Java supports this, but you can implement your own.
One way to implement such a collection would be to use a sorted array. Index lookups are easy. Value lookups could use Arrays.binarySearch()
. Inserting a new value would also use binarySearch()
to find the insertion point, then shift the remainder of the values to make room for the new value, auto-extending the array as needed.
Sorting a collection of objects
Implement the Comparator interface (once for each different sort order) and use the Collections.sort() method that takes a Comparator as additional parameter.
Is it faster to add to a collection then sort it, or add to a sorted collection?
TreeSet has a log(n)
time complexity guarantuee for add()/remove()/contains()
methods.
Sorting an ArrayList
takes n*log(n)
operations, but add()/get()
takes only 1
operation.
So if you're mainly retrieving, and don't sort often, ArrayList
is the better choice. If you sort often but dont retrieve that much TreeSet
would be a better choice.
How to use Collections.sort() in Java?
Use this method Collections.sort(List,Comparator) . Implement a Comparator and pass it to Collections.sort().
class RecipeCompare implements Comparator<Recipe> {
@Override
public int compare(Recipe o1, Recipe o2) {
// write comparison logic here like below , it's just a sample
return o1.getID().compareTo(o2.getID());
}
}
Then use the Comparator
as
Collections.sort(recipes,new RecipeCompare());
Related Topics
Detect Touch Press VS Long Press VS Movement
How to Use Interface to Communicate Between Two Activities
Unexpected Top-Level Exception: Com.Android.Dex.Dexexception: Multiple Dex Files Define
Volley - Sending a Post Request Using JSONarrayrequest
Firestore Query - Checking If Username Already Exists
Library to Read/Write Pbxproj/Xcodeproj Files
Compute Hex Color Code for an Arbitrary String
Aes Java Encoding, Ruby Decoding
Spring JSON Request Getting 406 (Not Acceptable)
Does Python Have an Equivalent to Java Class.Forname()
Javafx Freeze on Desktop.Open(File), Desktop.Browse(Uri)
How to View/Change Socket Connection Timeout on Linux
Can't Make Jdbc Connection to MySQL (Using Java, Intellij, and Linux)
Inputstream.Available() Is 0 Always
How to Achieve Javafx Mouse Event "Push and Hold"