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

Use Google Guava's TreeMultiset class. Guava has a spectacular collections API.

One problem with providing an implementation of List that maintains sorted order is the promise made in the JavaDocs of the add() method.

Answer 2

The problem with PriorityQueue is that it's backed up by an simple array, and the logic that gets the elements in order is done by the "queue[2*n+1] and queue[2*(n+1)]" thingie. It works great if you just pull from head, but makes it useless if you are trying to call the .toArray on it at some point.

I go around this problem by using com.google.common.collect.TreeMultimap, but I supply a custom Comparator for the values, wrapped in an Ordering, that never returns 0.

ex. for Double:

private static final Ordering<Double> NoEqualOrder = Ordering.from(new Comparator<Double>() {

    @Override
    public int compare(Double d1, Double d2)
    {
        if (d1 < d2) {
            return -1;
        }
        else {
            return 1;
        }
    }
});

This way I get the values in order when I call .toArray(), and also have duplicates.

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 Collections#sort(java.util.List) and TreeSet for more info.

Answer 4

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).

Answer 5

You want the SortedSet implementations, namely TreeSet.

Answer 6

TreeSet would not work because they do not allow duplicates plus they do not provide method to fetch element at specific position. PriorityQueue would not work because it does not allow fetching elements at specific position which is a basic requirement for a list. I think you need to implement your own algorithm to maintain a sorted list in Java with O(logn) insert time, unless you do not need duplicates. Maybe a solution could be using a TreeMap where the key is a subclass of the item overriding the equals method so that duplicates are allowed.