Java List Sorting: Is there a way to keep a list permantly sorted automatically like TreeMap?

Question

In Java you can build up an ArrayList with items and then call:

Collections.sort(list, comparator);

Is there anyway to pass in the Comparator at the time of list, creation like you can do with TreeMap?

The goal is to be able add an element to the list and instead of having it automatically appended to the end of the list, the list would keep itself sorted based on the Comparator and insert the new element at the index determined by the Comparator. So basically the list might have to re-sort upon every new element added.

Is there anyway to achieve this in this way with the Comparator or by some other similar means?

Solution 1

You can change the behaviour of ArrayList

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
         super.add(mt);
         Collections.sort(list, comparator);
         return true;
    }
}; 

Note: a PriorityQueue is NOT a List, if you didn't care what type of collection it was, the simplest would be to use a TreeSet, which is just like a TreeMap but is a collection. The only advantage PriorityQueue has is to allow duplicates.

Note: resorting is not very efficient for large collections, Using a binary search and inserting an entry would be faster. (but more complicated)

EDIT: A lot depends on what you need the "list" to do. I suggest you write a List wrapper for an ArrayList, LinkedList, PriorityQueue, TreeSet, or one of the other sorted collections and implement the methods which will actually be used. That way you have a good understanding of the requirements for the collection and you can make sure it works correctly for you.

EDIT(2): Since there was so much interest in using binarySearch instead. ;)

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
        int index = Collections.binarySearch(this, mt);
        if (index < 0) index = ~index;
        super.add(index, mt);
        return true;
    }
};

Solution 2

Everyone is suggesting PriorityQueue. However, it is important to realize that if you iterate over the contents of a PriorityQueue, the elements will not be in sorted order. You are only guaranteed to get the "minimum" element from the methods peek(), poll(), etc.

A TreeSet seems to be a better fit. The caveats would be that, as a Set, it can't contain duplicate elements, and it doesn't support random access with an index.

Solution 3

Something like TreeSet (or TreeMultiset in case you need duplicates) with more efficient random access is possible, but I doubt it was implemented in Java. Making each node of the tree remembers the size of its left subtree allows accessing an element by index in time O(log(size)) which is not bad.

In order to implement it, you'd need to rewrite a good portion of the underlying TreeMap.

Solution 4

The main difference between SortedSet and List is:

• SortedSet keeps it's element in the right order, but you can't really access a specific element by index.
• List allows indexed access, and arbitrary ordering of the elements. It also allows changing any element (by index or Iterator) to another element, without that the location changes.

You seem to want kind of a fusion of both: automatic sorting, and allowing (reasonable fast) index access. Depending on the size of data and how often indexed reading or adding new elements occur, these are my ideas:

• a wrapped ArrayList, where the add method used a ListIterator to find the insertion spot, then inserting the element there. This is O(n) for insertions, O(1) for indexed access.
• a wrapped LinkedList, where the add method used a ListIterator to find the insertion spot, then inserting the element there. (This still is O(n) for insertions (with sometimes quite smaller factor as ArrayList, sometimes even more), as well as indexed access.)
• a modified binary tree keeping track of the sizes of both halves on each level, thus enabling indexed access. (This would be O(log n) for each access, but needs some extra programming, as it is not yet included in the Java SE. Or you find some library that can this.)

In any case, the interfaces and contracts of SortedSet and List are not really compatible, so you'll want the List part be read-only (or read-and-delete-only), not allowing setting and adding, and having an extra object (maybe implementing the Collection interface) for adding Objects.

Solution 5

I would use a Guava TreeMultiset assuming you want a List because you may have duplicate elements. It'll do everything you want. The one thing it won't have is index-based access, which doesn't make much sense given that you aren't putting elements at indices of your choosing anyway. The other thing to be aware of is that it won't actually store duplicates of equal objects... just a count of the total number of them.

View more solutions