Sorted array list in Java

Question

I'm baffled that I can't find a quick answer to this. I'm essentially looking for a datastructure in Java which implements the java.util.List interface, but which stores its members in a sorted order. I know that you can use a normal ArrayList and use Collections.sort() on it, but I have a scenario where I am occasionally adding and often retrieving members from my list and I don't want to have to sort it every time I retrieve a member in case a new one has been added. Can anyone point me towards such a thing which exists in the JDK or even 3rd party libraries?

EDIT: The datastructure will need to preserve duplicates.

ANSWER's SUMMARY: I found all of this very interesting and learned a lot. Aioobe in particular deserves mention for his perseverance in trying to achieve my requirements above (mainly a sorted java.util.List implementation which supports duplicates). I have accepted his/her answer as the most accurate for what I asked and most thought provoking on the implications of what I was looking for even if what I asked wasn't exactly what I needed.

The problem with what I asked for lies in the List interface itself and the concept of optional methods in an interface. To quote the javadoc:

The user of this interface has precise control over where in the list 
each element is inserted.

Inserting into a sorted list doesn't have precise control over insertion point. Then, you have to think how you will handle some of the methods. Take add for example:

public boolean add(Object o)
   Appends the specified element to the end of this list (optional operation).

You are now left in the uncomfortable situation of either 1) Breaking the contract and implementing a sorted version of add 2) Letting add add an element to the end of the list, breaking your sorted order 3) Leaving add out (as its optional) by throwing an UnsupportedOperationException and implementing another method which adds items in a sorted order.

Option 3 is probably the best, but I find it unsavory having an add method you can't use and another sortedAdd method which isn't in the interface.

Other related solutions (in no particular order):

• java.util.PriorityQueue which is probably closest to what I needed than what I asked for. A queue isn't the most precise definition of a collection of objects in my case, but functionally it does everything I need it to.
• net.sourceforge.nite.util.SortedList. However, this implementation breaks the contract of the List interface by implementing the sorting in the add(Object obj) method and bizarrely has a no effect method for add(int index, Object obj). General consensus suggests throw new UnsupportedOperationException() might be a better choice in this scenario.
• Guava's TreeMultiSet A set implementation which supports duplicates
• ca.odell.glazedlists.SortedList This class comes with the caveat in its javadoc: Warning: This class breaks the contract required by List

Answer 1

Lists typically preserve the order in which items are added. Do you definitely need a list, or would a sorted set (e.g. TreeSet<E>) be okay for you? Basically, do you need to need to preserve duplicates?

Answer 2

Have a look at SortedList

This class implements a sorted list. It is constructed with a comparator that can compare two objects and sort objects accordingly. When you add an object to the list, it is inserted in the correct place. Object that are equal according to the comparator, will be in the list in the order that they were added to this list. Add only objects that the comparator can compare.

---

When the list already contains objects that are equal according to the comparator, the new object will be inserted immediately after these other objects.

Answer 3

Please refer to this question: http://stackoverflow.com/questions/416266/sorted-collection-in-java

Answer 4

Use java.util.PriorityQueue.

Answer 5

I think the choice between SortedSets/Lists and 'normal' sortable collections depends, whether you need sorting only for presentation purposes or at almost every point during runtime. Using a sorted collection may be much more expensive because the sorting is done everytime you insert an element.

If you can't opt for a collection in the JDK, you can take a look at the Apache Commons Collections

Answer 6

You could subclass ArrayList, and call Collections.sort(this) after any element is added - you would need to override two versions of add, and two of addAll, to do this.

Performance would not be as good as a smarter implementation which inserted elements in the right place, but it would do the job. If addition to the list is rare, the cost amortised over all operations on the list should be low.

Answer 7

Minimalistic Solution

Here is a "minimal" solution.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) {
            T tmp = get(i);
            set(i, get(i-1));
            set(i-1, tmp);
        }
    }
}

The insert runs in linear time, but that would be what you would get using an ArrayList anyway (all elements to the right of the inserted element would have to be shifted one way or another).

Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueue as well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

Overriding List.add

Note that overriding List.add (or List.addAll for that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification. What you could do, is to override this method to throw an UnsupportedOperationException.

From the docs of List.add:

boolean add(E e)
    Appends the specified element to the end of this list (optional operation).

Same reasoning applies for both versions of add, both versions of addAll and set. (All of which are optional operations according to the list interface.)

Some tests

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

....prints:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Answer 8

It might be a bit too heavyweight for you, but GlazedLists has a SortedList that is perfect to use as the model of a table or JList

Answer 9

If you don't need random access, don't use a List, use a SortedSet, or possibly a SortedMap.

Answer 10

You can try Guava's TreeMultiSet.

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);