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?

Answer 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;     } }; 

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