sorted collection in java

Question

I'm a beginner in Java. Please suggest which collection(s) can/should be used for maintaining a sorted list in Java. I have tried Map and Set but they weren't what I was looking for.

Answer 1

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

Answer 2

You want the SortedSet implementations, namely TreeSet.

Answer 3

There are a few options. I'd suggest TreeSet if you don't want duplicates and the objects you're inserting are comparable.

You can also use the static methods of the Collections class to do this.

See http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#sort(java.util.List) and http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html for more info.

Answer 4

If you just want to sort a list, use any kind of List and use Collections.sort(). If you want to make sure elements in the list are unique and always sorted, use a SortedSet.

Answer 5

If you want to maintain a sorted list which you will frequently modify (i.e. a structure which, in addition to being sorted, allows duplicates and whose elements can be efficiently referenced by index), then use an ArrayList but when you need to insert an element, always use Collections.binarySearch() to determine the index at which you add a given element. The latter method tells you the index you need to insert at to keep your list in sorted order.

Answer 6

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 order at all times, and have good insertion performance by using a heap data structure, where inserting in a sorted ArrayList will be O(n) (i.e., using binary search and move).