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

Melinite

If you insert occasionally and read frequently why not just sort it during insertion? – Fustigate

Answer 1

Minimalistic Solution

Here is a quick and dirty solution.

class SortedArrayList<T> extends ArrayList<T> {
    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        int i = Collections.binarySearch((List<Comparable<T>>) this, value);
        add(i < 0 ? -i - 1 : i, value);
    }
}

Note that despite the binarySearch, insertSorted will run in linear time since add(index, value) runs in linear time for an ArrayList.

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

A more complete implementation would, just like the PriorityQueue, also include a constructor that allows the user to pass in a Comparator.

Demo

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]

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.

From the docs of List.add:

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

Maintaining the sortedness invariant

Unless this is some throw-away code, you probably want to guarantee that all elements remain sorted. This would include throwing UnsupportedOperationException for methods like add, addAll and set, as well as overriding listIterator to return a ListIterator whose set method throws.

Applejack

A good start, but calling add, or addall would add members in an unsorted fashion. – Melinite

Yes. Anything but appending them to the list would be a direct violation of the List-interface. See my updated answer. – Applejack

@Applejack Good point. But isn't an Unsupported operation of a interface method a code smell? The proper way might be to not extend ArrayList but implement List but even then maybe List just wasn't meant for this purpose. From the Javadoc for List: The user of this interface has precise control over where in the list each element is inserted which isn't the best description for inserting elements in a sorted fashion and you still have to deal with the add(int index, Object obj) interface method. These issues probably explain why List hasn't been implemented in a sorted fashion. – Melinite

Well, the operation is optional for a reason. I wouldn't be surprised if I got an UnsupportedExceptionOperation when doing .add on a SortedArrayList. Yes, 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.) – Applejack

Ah, I didn't realize they were optional operations. The plot thickens... ;) – Melinite

Heheh, yeah. At first I was against the whole idea and upvoted the PriorityQueue-answer. However, if one simply adds an insertSorted (and possibly disallow add) I think one would be "correct" in all aspects, and still have a List that has sorted elements :-) – Applejack

As always with stackoverflow though, it is not always the formally "correct" answer that the OP wants :-) – Applejack

Of course, the problem with insertSorted() is that you can't pass around the data structure as a List and still add new members. But maybe that's the best of both worlds. Where you add elements you work with the concrete implementation, and then pass around a read-only List interface to the rest of the code. – Melinite

Well, that wouldn't be safe anyway... say you pass it to a function that does list.add("x"); if (!list.get(list.size()-1).equals("x")) formatHarddrive();. It's safe according to spec, so you can't really blame the method-writer for the crash :P – Applejack

Is there any reason you can't (or shouldn't) make it class SortedArrayList<T extends Comparable<T>> extends ArrayList<T>? That would explicitly enforce the fact that you can only put in things that are comparable to themselves, rather than implicitly through a cast. – Lattie

Not in my sample snippet, but in a more complete example you would want to include custom orderings through a Comparator. – Applejack

This is a great answer. I suggest to use composition over inheritance (en.wikipedia.org/wiki/Composition_over_inheritance). I my implementation I define a class SortedList<T> implements Iterable<T> that implements all methods I need by delegating to a List object (which isn't exposed). That way you don't run into any of the problems mentioned in other comments. – Vite

@EmanuelMoecklin, good suggestion, but not applicable to this question which specifically says "I'm essentially looking for a datastructure in Java which implements the java.util.List interface". – Applejack

You can use composition and still implement the List interface – Vite

@EmanuelMoecklin, right. That would be slightly "safer" I guess. One has to ask "Is a SortedList an ArrayList?" and formally I think the answer is "no". So unless it's some throwaway code, composition is probably the way to go here. – Applejack

@Applejack Maybe it shouldn't be called SortedList since it does violate the List contract. AFAIK there's no interface definition in Java that fits a sorted list data structure. Lists should give precise control over where each element is inserted while Maps don't allow duplicates. Maybe it should be called SortedCollection? As a consequence delegation/composition makes sense even if that means writing more code. – Vite

@EmanuelMoecklin formally speaking it does comply with the List interface since all add methods are optional. – Applejack

@Applejack you're right. When I use a list in my code (code against the interface) I do expect to be able to use the add methods though. If I have a List implementation that imposes restrictions on the add methods I would want to use the concrete class or another interface which doesn't have the add methods. I would therefore suggest to either use composition with a concrete class that delegates to a List or define a new interface SortedList and code against that list. I'm aware that the OP wanted a List but maybe that approach is flawed... – Vite

@EmanuelMoecklin, note that API methods such as Arrays.asList and Collections.unmodifiableList return lists that doesn't support add. So while it may seem unnatural to you to have a List that doesn't support add, it's not that uncommon. – Applejack

@Applejack Again that's correct. Nevertheless I wouldn't use that list all across my code but just locally where I know it's unmodifiable or whatever restrictions it has. I don't think it's good design to code against an interface that might or might not support certain methods (I know it's common but that doesn't make it good). Alternatively use the List as Iterable<T> or Collection<T>. – Vite

Answer 2

Use java.util.PriorityQueue.

Landlocked

that is not a List, i.e. no random access. – Route

It's a queue based priority heap a does not implement List. – Robinett

Of course, with a list that maintains sort order the indexes change all the time, so random access is probably not needed anyway. – Route

Hmm, this might work for what I require (as I don't need random access). Thanks! – Melinite

+1 Imho the best solution given, even if does not implement the List interface. – Cresol

-1 as it doesn't implement List, which was one of the OP's requirements. – Auberbach

@Qwerky, note that the exact answer is not always the best answer, or the answer the OP is actually after. – Applejack

priority queue doesn't grant sorted order on iteration. – Osullivan

marcorossi has the crux of it, PriorityQueue would be what the OP was looking for if its iterator returned the elements in the natural ordering of the queue, but the javadoc specifically says it doesn't. – Buchalter

Answer 3

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

Conspectus

+1. This is a great library. MultiSet is A collection that supports order-independent equality, like Set, but may have duplicate elements – Neotropical

Answer 4

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?

Scrapbook

Thanks Jon, but I need to preserve duplicates – Melinite

Answer 5

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.

Miss

That looks good, but it also looks buggy: there's no override of either version of addAll, so the list will be unsorted after calling those. – Honewort

And the add method "has no effect". It should rather throw an UnsupportedOperationException if it cannot be used. – Route

@Tom Anderson @Route , agree with both of you. – Miss

Interesting, but I'm rather wary of someone in the future using addAll() and thinking it would all all the elements in a sorted fashion. Agree with the UnsupportedOperationException as well. – Melinite

What's the time complexity of addition to this list? – Kamerun

Answer 6

Aioobe's approach is the way to go. I would like to suggest the following improvement over his solution though.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

aioobe's solution gets very slow when using large lists. Using the fact that the list is sorted allows us to find the insert point for new values using binary search.

I would also use composition over inheritance, something along the lines of

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vite

This solution probably outperforms the solution I propose, but only with a constant factor. The complexity is the same: insertSorted runs in O(n) in both our solutions. – Applejack

Actually got around to update my answer. Correct me if I'm wrong, but I think Collections.binarySearch does just what your insertPoint does? – Applejack

Answer 7

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

Dihydrostreptomycin

Answer 8

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.

Honewort

Answer 9

Just make a new class like this:

public class SortedList<T> extends ArrayList<T> {

private final Comparator<? super T> comparator;

public SortedList() {
    super();
    this.comparator = null;
}

public SortedList(Comparator<T> comparator) {
    super();
    this.comparator = comparator;
}

@Override
public boolean add(T item) {
    int index = comparator == null ? Collections.binarySearch((List<? extends Comparable<? super T>>)this, item) :
            Collections.binarySearch(this, item, comparator);
    if (index < 0) {
        index = index * -1 - 2;
    }
    super.add(index+1, item);
    return true;
}

@Override
public void add(int index, T item) {
    throw new UnsupportedOperationException("'add' with an index is not supported in SortedArrayList");
}

@Override
public boolean addAll(Collection<? extends T> items) {
    boolean allAdded = true;
    for (T item : items) {
        allAdded = allAdded && add(item);
    }
    return allAdded;
}

@Override
public boolean addAll(int index, Collection<? extends T> items) {
    throw new UnsupportedOperationException("'addAll' with an index is not supported in SortedArrayList");
}

}

You can test it like this:

    List<Integer> list = new SortedArrayList<>((Integer i1, Integer i2) -> i1.compareTo(i2));
    for (Integer i : Arrays.asList(4, 7, 3, 8, 9, 25, 20, 23, 52, 3)) {
        list.add(i);
    }
    System.out.println(list);

Anonym

Answer 10

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

Clavicembalo

Answer 11

Since the currently proposed implementations which do implement a sorted list by breaking the Collection API, have an own implementation of a tree or something similar, I was curios how an implementation based on the TreeMap would perform. (Especialy since the TreeSet does base on TreeMap, too)

If someone is interested in that, too, he or she can feel free to look into it:

TreeList

Its part of the core library, you can add it via Maven dependency of course. (Apache License)

Currently the implementation seems to compare quite well on the same level than the guava SortedMultiSet and to the TreeList of the Apache Commons library.

But I would be happy if more than only me would test the implementation to be sure I did not miss something important.

Best regards!

Sternum

Answer 12

https://github.com/geniot/indexed-tree-map

I had the same problem. So I took the source code of java.util.TreeMap and wrote IndexedTreeMap. It implements my own IndexedNavigableMap:

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

The implementation is based on updating node weights in the red-black tree when it is changed. Weight is the number of child nodes beneath a given node, plus one - self. For example when a tree is rotated to the left:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simply updates weights up to the root:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

And when we need to find the element by index here is the implementation that uses weights:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Also comes in very handy finding the index of a key:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);
    
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

You can find the result of this work at https://github.com/geniot/indexed-tree-map

TreeSet/TreeMap (as well as their indexed counterparts from the indexed-tree-map project) do not allow duplicate keys , you can use 1 key for an array of values. If you need a SortedSet with duplicates use TreeMap with values as arrays. I would do that.

Doubleganger

Answer 13

The following method can be used to print the elements of a LinkedList of String objects.

The method accepts a LinkedList object as input and prints each element of the list, separated by a space, to the console. To make the output more readable, the method also adds a newline before and after the list.

public static void printList(LinkedList<String> list) {
    System.out.println("\nList is: ");
    for (String element : list) {
        System.out.print(element + " ");
    }
    System.out.println();
}

Soilure