Sorted collection in Java
Solution 1:
This comes very late, but there is a class in the JDK just for the purpose of having a sorted list. It is named (somewhat out of order with the other Sorted*
interfaces) "java.util.PriorityQueue
". It can sort either Comparable<?>
s or using a Comparator
.
The difference with a List
sorted using Collections.sort(...)
is that this will maintain a partial order at all times, with O(log(n)) insertion performance, by using a heap data structure, whereas inserting in a sorted ArrayList
will be O(n) (i.e., using binary search and move).
However, unlike a List
, PriorityQueue
does not support indexed access (get(5)
), the only way to access items in a heap is to take them out, one at a time (thus the name PriorityQueue
).
Solution 2:
TreeMap and TreeSet will give you an iteration over the contents in sorted order. Or you could use an ArrayList and use Collections.sort() to sort it. All those classes are in java.util