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?

Siemens

@To everyone offering PriorityQueue, it's implemented via Heap [backed by an array], thus it's not Iterable in its natural order but the heap 'building' order. Each operation to the heap needs sift-up/down. – Thundersquall

Use a TreeSet if you don't need any of the List features. – Manzo

Such a thing would break the contract of List because List operations specify where they add the element... add(E) adds to the end, add(int, e) adds at the specified index, etc. set(int, E) would be even weirder. – Revolute

While technically true, I don't think breaking the contract for add(e) is a big deal. You would want to throw exceptions for add(int, e) and set(int, e) and whatever else doesn't make sense. – Methodius

@ColinD, you can always consider 'em UnsupportedOperationException() :) – Thundersquall

@Eric: It's a big deal if this List might be used by any code that expects a List that doesn't break its contract. – Revolute

@ColinD: But I would argue that most code that uses a List doesn't care about the appending or not. They're using lists to hold things. But definitely something to consider, yes. – Methodius

@Eric: I'd say if all you want is to hold things, a Set or Multiset is more appropriate depending on whether you need to allow duplicate elements or not. Both of these also happen to have implementations that allow Comparator based ordering. Explicit, user-defined order (by insertion order and indexed insertion) is a core property of a List. – Revolute

@ColinD: I don't disagree with you, but maybe the OP is dealing with an API that only takes a List or whatever. Hard to say without knowing the full context of why they want a sorted list. That's one thing I don't like about many SO questions, not enough context to tell the questioner what the best solution is, as opposed to answering the literal question... – Methodius

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

Autism

+1, for a simple and effective solution. just, it might be better to return the result of super.add(..) rather than always true. Although in this case it doesn't matter, since ArrayList has hardcoded return true as well. – Farrel

PriorityQueue has more advantages: It's surely much more efficient both in terms of size and speed. – Decency

@Bozho, If we where using a Set, the answer would be very different. – Autism

@maaartinus, Not sure its more efficient than TreeSet. If you have to have a List, it won't help. If you don't, its not the only option. – Autism

you need to override everything, though, set, add(int, O), addAll.. iterator.set... Backing the day had to write proxies for the JDO impl, we did. LinkedList was the worst of all, though. – Thundersquall

sorting via Collections.sorts like that is quite inefficient, call toArray, clones the array and then uses sets via ListIterator. In that regard using LinkedList and inserting at the right position is a lot better option. – Thundersquall

Not sure its more efficient than TreeSet. - What I meant: Using a TreeSet as a replacement for PriorityQueue would be possible but quite inefficient. As a PQ offers neither random access nor an ordered iterator, I refuse to think about it as a base for a SortedList. – Decency

It is a good option to keep in mind, but I agree it would require overriding more methods to have a proper implementation....EDIT: I see your comment about binary search -- that is a good point. – Siemens

Btw., this solution is very slow. Using binarySearch and inserting at the proper position would be much faster. – Decency

Using a LinkedList makes the insert faster, but the search slower. (as you can't use binarySearch efficiently) I would prefer to take a fixed cost on the insert and be less dependant on the Comparator (which could be much more expensive) – Autism

@david, it really depends on what you want the "list" to do. PriorityQueue doesn't provide an ordered iterator and TreeSet doesn't provide random access. – Autism

@Decency you need tree for efficient binary search algo, for arraylist insert copies the remained past the index. – Thundersquall

@bestsss: What about Collections.binarySearch? The OP wants his List to be sorted all the time, so it works. No tree needed. – Decency

@bestsss, what do you mean by "you need tree"? Do you mean TreeSet? – Autism

I would be surprised if COllections.binarySearch() was slower than TreeSet. The insertion cost is higher, but if you need to allow duplicates, you have to have a List. – Autism

This solution is O(n^2 * log(n)) for n inserts. – Trench

@Peter Lawrey, not TreeSet exactly. some balanced binary tree. Trees can be decent structures but they have some overhead and worst of all many just don't understand them. Having a sorted/random index structure that has O(log2n) is possible. TreeSet just doesn't have log2n get(index) and does not allow duplicates, but duplicates are easily solvable by using TreeMap<Key, Integer> – Thundersquall

@maaartinus, binary search is useful if you have random access to the elements. Collection.binarySearch is no different. If you have random access in array-alike structure, you have very slow inserts. To combine both use binary trees. – Thundersquall

@rlibby, The simple solution provided is O(N*log2(n)), using a binarySearch() instead is O(n) for the insert only. However, unless you know otherwise, the simplest solution is often the best. – Autism

I proposed already using a tree in my own answer. Here I only wanted to improve the solution presented in this answer. Replacing sort by binarySearch and insertion in the proper place makes for sure a big speed difference here, that's all. – Decency

@bestsss, You are right that TreeMap<Key, Integer> could be used to store the count of the keys, provided all equal Keys are interchangeable. – Autism

@Peter Lawrey, yes, it is O(nlog(n)) for a _single insert_. However for a list of n elements, you do n inserts, yielding O(n^2 * log(n)). Yes, the binary search modification gives you O(n) for a single insert, yielding O(n^2) for n inserts. Is that supposed to be impressive? Using a balanced binary search tree gives you O(nlog(n)) for n inserts. – Trench

@maaartinus, binartSearch returns an index, it's slow to get the index and then slow to use it. W/ ListItearator you can 'add' easily at any position (for LinkedList). It's like 4 lines of code anyways. – Thundersquall

@bestsss: Right, for LinkedList makes binarySearch no sense. But I haven't written a single line about LinkedList, and the answer uses it neither. Whenever 1. there are a lot of random reads or 2. the comparator is slow, ArrayList with binarySearch wins. – Decency

@rlibby, how can adding an element to an array be anything other than O(N) ? Where does the log come from? – Autism

@bestsss, can you give an example of where you can insert (or extract for PriorityQueue) without performing a binary search? – Autism

@Peter Lawrey, in your first code block above, it comes from Collections.sort (line 4), since Omega(n*log(n)) is the lower bound on a comparison sort. – Trench

@Peter, I will try and edit my answer to include that, binary search in the LinkedList+insert. Extracting off Heap (PriorityQueue) is O(n+2*log2n), indexOf(Object) is O(n) and then 2 times to siftDown/up. – Thundersquall

@Peter Lawrey, added the code. This discussion has become quite messy, I hope I got your idea. – Thundersquall

@PeterLawrey as always, your solutions are excellent! you should be working on the framework at Google or Oracle (if you are not already). – Topology

The above solution works fine if the new elements are added bu list.add method, but fails if another list is assigned to the variable i.e list=otherList; – Blastoff

Will it affect performance if using binarysearch in larget amount of data? – Lauzon

@FranzD you raise a valid point that it depends on you use the class, including, is the element class mutable, should it allow duplicates as TreeMap doesn't. You also have newer methods added to list which won't behave as expected. retainAll, replaceAll, set by index, subLists, – Autism

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.

Foreshorten

You could simulate the random access using an iterator. It wouldn't be worse then for LinkedList. With a proprietary implementation it can be done in O(log(size)), see my answer. – Decency

You can also use SkipList. – Wolver

Answer 3

Commentary

There is probably a good reason that there is no SortedList implementation in the JDK. I personally can't think of a reason to have one auto-sort in the JDK.

It reeks of premature optimization gone wrong. If the list is not read from as often as it is inserted into, then you are wasting cycles sorting repeatedly for no reason. Sorting right before a read would be much more reactive and having a boolean somewhere indicating that the list does or does not need to be sorted before reading it would be even better.

The thing is you only really care about order when traversing the list with an Iterator or for each loop, so calling Collections.sort() before any code that iterates would probably be more performant than trying to keep the list sorted all the time on every insertion.

There are ambiguities with List because of duplicates, how do you order duplicates deterministically? There is SortedSet, and that makes sense because of the uniqueness. But sorting a List can have more complications from the side effects of duplicates and other constraints like making every object Comparable or as I show in my code having to have a Comparator that can do the work instead.

Sorting on .add()

If you have some very special situation where a auto-sorting List would be useful then one thing you might do is sub-class a List implementation and over-ride .add() to do a Collections.sort(this, comparator) that you pass into a custom constructor. I used LinkedList instead of ArrayList for a reason, ArrayList is a natural insertion sorted order List to begin with. It also has the ability to .add() at an index which is pretty useless if you want a constantly sorted List, that would have to be handled in someway that would probably be less than ideal. According to the Javadoc;

void    add(int index, Object element)

Inserts the specified element at the specified position in this list (optional operation).

So it just throwing UnSupportedOperationException would be acceptable, or you could just ignore the index and delegate to .add(Object element); if you document it in a JavaDoc on the method.

Usually when you want to lots of inserts/removals and sorting you would use a LinkedList because of better performance characteristics given the usage of the `List'.

Here is a quick example:

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    /**
    * this ignores the index and delegates to .add() 
    * so it will be sorted into the correct place immediately.
    */
    @Override
    public void add(int index, Object element)
    {
        this.add(element);     
    }

    @Override
    public boolean add(final E e)
    {
        final boolean result = super.add(e);
        Collections.sort(this, this.comparator);
        return result;
    }
}

Most Efficient Solution:

Alternatively you could only sort when getting the Iterator and this would be more performance oriented if the sorted order was only really important when iterating over the List. This would cover the use case of the client code not having to call, Collections.sort() before every iteration and encapsulate that behavior into the class.

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    @Override
    public Iterator<E> iterator()
    {
        Collections.sort(this, this.comparator);
        return super.iterator();
    }
}

Of course there would need to be error checking and handling to see if the Comparator was null or not and what to do if that was the case, but this gives you the idea. You still don't have any deterministic way to deal with duplicates.

Guava Solution:

If you are using Guava and you should be, you can just use

Ordering.immutableSortedCopy() only when you need to iterate and be done with it.

Threadfin

why would you call sort on add, it's much better to insert at right position? – Thundersquall

because the OP wanted it that way, maybe they don't know what the "right" position is, that is what the Comparator is for, to determine the "right" position for all items relative to the other items. – Threadfin

Ordered data structures are a fundamental building block in Computer Science. It's strange that you can't think of a single use case for them. – Chui

@AryaPourtabatabaie - read for comprehension, it is not about not needing sorted structures, it is about an auto sorting List not being a good idea as a general purpose structure and not being in the JDK. – Threadfin

Answer 4

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.

Decency

Yes, tree alike structure can have O(log2n) random access by index same for insert/remove/indexOf, etc. – Thundersquall

For what it's worth, Java does have a TreeSet: docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html – Chiu

Answer 5

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.

Verada

Answer 6

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.

Revolute

Answer 7

commons-collections have TreeBag

Initially I suggested PriorityQueue, but its iteration order is undefined, so it's no use, unless you iterate it by getting the head of a clone of the queue until it gets empty.

Since you are most likely concerned with the iteration order, I believe you can override the iterator() method:

public class OrderedIterationList<E> extends ArrayList<E> {
    @Override
    public Iterator<E> iterator() {
        Object[] array = this.toArray(); // O(1)
        Arrays.sort(array);
        return Arrays.asList(array).iterator(); // asList - O(1)
    }
}

You can improve this by storing a snapshot of the sorted collection, and use modCount to verify whether the collection is not changed.

Depending on the use-cases, this may be less or more efficient than Peter's suggestion. For example if you add multiple items, and iterate. (without adding items between iterations), then this might be more efficient.

Farrel

iteration of a PriorityQueue does NOT perserve order, and the most common reason to sort a List is to iterate over it in a specific sorted order. – Threadfin

Answer 8

The only way to have any sorted structure with less than O(n) time to add/indexOf/remove/get element is using a tree. In that case operations generally have O(log2n) and traverse is like O(1).

O(n) is just a linked list.

---

Edit: inserting into linked list w/ binary search. For inserts operations, not using binary structure, and not small sizes, that should be optimal.

@Peter: There is the algo w/ O(log2n) compares (which are slow) to insert and O(n) moves. If you need to override LinkedList, so be it. But that's as neat as it can get. I keep the algorithm as clean as possible to be easily understandable, it can be optimized a little.

package t1;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class SortedList {


    private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
        int low = 0;
        int high= i.previousIndex();
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

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

    private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
    private static void move(ListIterator<?> i, int index) {        
        int pos = i.nextIndex();
        if (pos==index)
            return;

        if (pos < index) {
            do {
                i.next();
            } while (++pos < index);
        } 
        else {
            do {
                i.previous();
            } while (--pos > index);
        }
    }
    @SuppressWarnings("unchecked")
    static  <T> int insert(List<? extends Comparable<? super T>> list, T key){
        ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
        int idx = binarySearch(i, key); 
        if (idx<0){
            idx=~idx;
        }
        move(i, idx);
        ((ListIterator<T>)i).add(key);
        return i.nextIndex()-1;
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> unsorted = new LinkedList<Integer>();
        Random r =new Random(11);
        for (int i=0;i<33;i++){
            Integer n = r.nextInt(17);
            insert(list, n);
            unsorted.add(n);            
        }

        System.out.println("  sorted: "+list);
        System.out.println("unsorted: "+unsorted);
    }

Thundersquall

Answer 9

The obvious solution is to create your own class that implements the java.util.List interface and takes a Comparator as an argument to the constructor. You would use the comparator in the right spots, i.e. the add method would iterate through the existing items and insert the new item at the right spot. You would disallow calls to methods like add(int index, Object obj) and so on.

In fact, someone has to have created this already... a quick Google search reveals at least one example:

http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html

Methodius

Answer 10

Consider indexed-tree-map that I created while facing a similar problem, you will be able to access elements by index and get index of elements while keeping the sort order. Duplicates can be put into arrays as values under the same key.

Fakir

Answer 11

In the JavaFX TransformationList hierarchy, there is something called a SortedList. The list is entirely observable so that additions/removals will notify any other listeners watching the list.

The basic approach to doing this is you watch another ObservableList for changes and strategically use Collections.binarySearch() as others have suggested to locate the index of the addition or removal in Olog(n) time.

There is one problem that I have not seen mentioned here and that is the ability to track items added that have the same compareTo signature, i.e. T1.compareTo(T2) == 0. In this case the sorted list (I will post my own source code below) must have a wrapper element type, that I will call Element. This is similar to what the creators in JavaFX did with SortedList. The reason for this is entirely due to removal operations, it is impossible to locate the original element if there are compareTo duplicates. Normally in a NavigableSet implementation like TreeSet, these duplicates would never enter the Set. A list is different.

I have a library of observable lists that can be effectively chained together (very similar to Java Streams) that fully propagate results downstream as the previous source in the chain updates.

Class Hierarchy

Interface

/**
 * Binds the elements of this list to the function application of each element of a
 * source observable list.
 * <p>
 * While a {@code IListContentBinding} is bound, any attempt to modify its contents
 * will result in an {@code UnsupportedOperationException}. To unbind the list, call
 * {@link #unbind() unbind}.
 *
 * @param <S> The element type of the input source list that will generate change
 *            events.
 * @param <T> The element type of this output list.
 */
public interface IListContentBinding<S, T> extends ObservableList<T>, ObservableListValue<T>, IContentBinding {... details not shown ....}

Abstract Base Class for all Binding Types (Sort, Distinct, Map, FlatMap, etc.)

/**
 * Binds the elements of this list to the function application of each element of a
 * source observable list.
 * <p>
 * While a {@code ListContentBinding} is bound, any attempt to modify its contents
 * will result in an {@code UnsupportedOperationException}. To unbind the list, call
 * {@link #unbind() unbind}.
 *
 * @param <S> The element type of the source list that will generate change events.
 * @param <T> The element type of this binding.
 */
public abstract class ListContentBinding<S, T> extends ObservableListWrapper<T>
    implements IListContentBinding<S, T> {.... details not shown ....}

Sort Binding Class

/**
 * A {@code ListContentBinding} implementation that generates sorted elements from a
 * source list. The comparator can be set to another {@code Comparator} function at
 * any time through the {@link #comparatorProperty() comparator} property.
 * <p>
 * Unlike the Collections {@link Collections#sort(List) list sort} or Arrays
 * {@link Arrays#sort(Object[]) array sort}, once this binding has been added to the
 * order of duplicate elements cannot be guaranteed to match the original order of
 * the source list. That is the insertion and removal mechanism do not guarantee that
 * the original order of duplicates (those items where T1.compareTo(T2) == 0) is
 * preserved. However, any removal from the source list is <i>guaranteed</i> to
 * remove the exact object from this sorted list. This is because an int <i>ID</i> field
 * is added to the wrapped item through the {@link Element} class to ensure that
 * matching duplicates can be further compared.
 * <p>
 * Added/Removed objects from the source list are placed inside this sorted list
 * through the {@link Arrays#binarySearch(Object[], Object, Comparator) array binary
 * search} algorithm. For any duplicate item in the sorted list, a further check on
 * the ID of the {@code Element} corresponding to that item is compared to the
 * original, and that item. Each item added to this sorted list increases the
 * counter, the maximum number of items that should be placed in this list should be
 * no greater than {@code Integer.MAX_VALUE - Integer.MIN_VALUE}, or 4,294,967,295
 * total elements. Sizes greater than this value for an instance of this class
 * may produce unknown behavior.
 * <p>
 * Removal and additions to this list binding are proportional to <i>O(logn)</i>
 * runtime, where <i>n</i> is the current total number of elements in this sorted
 * list.
 *
 * @param <T> The element type of the source and this list binding.
 */
class ListContentSortBinding<T> extends ListContentBinding<T, T> implements IListContentSortBinding<T> {

    /**
     * Each location in the source list has a random value associated it with to deal
     * with duplicate elements that would return T1.compareTo(T2) == 0.
     */
    private Element[] elements = newElementArray(10);

    /**
     * The same elements from {@link #elements} but placed in their correct sorted
     * position according to the {@link #elementComparator element comparator}.
     */
    protected Element[] sortedElements = newElementArray(10);

    /**
     * Create a new instance.
     *
     * @param source The source observable list. Sorted elements will be generated
     *            from the source and set as the content of this list binding.
     * @param comparator The sorter. An observable that will update the comparator of
     *            this binding when invalidated. The sorter can be set to another
     *            {@code Comparator} function at anytime through the
     *            {@link #comparatorProperty() comparator} property.
     * @param options The options of this binding. Considers {@code DependencyOption}
     *            instances.
     *            <p>
     *            All bindings consider {@code BeforeChangeOption} and
     *            {@code AfterChangeOption}.
     */
    @SafeVarargs
    ListContentSortBinding(ObservableList<T> source, ObservableObjectValue<Comparator<? super T>> comparator,
        BindingOption<T, T>... options) {
        this(source, comparator.get(), options);

        comparatorProperty().bind(comparator);
    }

    /**
     * Create a new instance.
     *
     * @param source The source observable list. Sorted elements will be generated
     *            from the source and set as the content of this list binding.
     * @param comparator The sorter. The sorter can be set to another
     *            {@code Comparator} function at anytime through the
     *            {@link #comparatorProperty() comparator} property.
     * @param options The options of this binding. Considers {@code DependencyOption}
     *            instances.
     *            <p>
     *            All bindings consider {@code BeforeChangeOption} and
     *            {@code AfterChangeOption}.
     */
    @SafeVarargs
    ListContentSortBinding(ObservableList<T> source, Comparator<? super T> comparator,
        BindingOption<T, T>... options) {
        super(new ArrayList<>(), options);

        List<Observable> observables = new ArrayList<>(
            Arrays.asList(BindingOptionBuilder.extractDependencies(options)));

        setComparator(comparator);
        observables.add(comparatorProperty());

        bind(source, observables.toArray(new Observable[observables.size()]));
    }

    @Override
    protected void sourceChanged(Change<? extends T> change) {
        List<? extends T> source = change.getList();

        while (change.next()) {
            int from = change.getFrom();

            if (change.wasPermutated() || change.wasUpdated()) {
                List<? extends T> srcMod = source.subList(from, change.getTo());

                removed(source, from, srcMod.size());
                added(source, from, srcMod);
            } else {
                List<? extends T> removed = change.getRemoved();
                List<? extends T> added = change.getAddedSubList();

                if (change.wasReplaced()) {
                    int min = Math.min(added.size(), removed.size());
                    replaced(source, from, added.subList(0, min));

                    added = added.subList(min, added.size());
                    removed = removed.subList(min, removed.size());
                }

                if (removed.size() > 0) {
                    removed(source, from, removed.size());
                }

                if (added.size() > 0) {
                    if (source.size() >= elements.length) {
                        ensureSize(source.size());
                    }

                    added(source, from, added);
                }

                ensureSize(source.size());
            }
        }
    }

    /**
     * Replace the items in this sorted list binding resulting from a replacement
     * operation in the source list. For each of the items added starting at the
     * <i>from</i> index in the source list, and items was removed at the same source
     * position.
     *
     * @param source The source list.
     * @param from The index of where the replacement started in the source
     *            (inclusive). The removed and added elements occurred starting at
     *            the same source position.
     * @param added The added source elements from the change.
     */
    @SuppressWarnings({})
    private void replaced(List<? extends T> source, int from, List<? extends T> added) {
        int oldSize = size();

        for (int i = 0; i < added.size(); i++) {
            int index = from + i;
            Element e = elements[index];

            // Find the old element and remove it
            int pos = findPosition(e, index, oldSize);

            System.arraycopy(sortedElements, pos + 1, sortedElements, pos, oldSize - pos - 1);

            remove(pos);

            T t = added.get(i);

            // Create a new element and add it
            e = new Element(t);

            elements[index] = e;

            pos = findPosition(e, index, oldSize - 1);

            if (pos < 0) {
                pos = ~pos;
            }

            System.arraycopy(sortedElements, pos, sortedElements, pos + 1, oldSize - pos - 1);
            sortedElements[pos] = e;

            add(pos, t);
        }
    }

    /**
     * Add the elements from the source observable list to this binding.
     *
     * @param source The source list.
     * @param from The index of where the addition started in the source (inclusive).
     * @param added The added source elements from the change.
     */
    @SuppressWarnings({})
    private void added(List<? extends T> source, int from, List<? extends T> added) {
        if (size() == 0) {
            int size = added.size();
            Element[] temp = newElementArray(size);

            for (int i = 0; i < added.size(); i++) {
                T t = added.get(i);
                Element e = new Element(t);

                elements[i] = e;
                temp[i] = e;
            }

            if (elementComparator == null) {
                addAll(added);
                return;
            }

            Arrays.sort(temp, elementComparator);
            System.arraycopy(temp, 0, sortedElements, 0, temp.length);

            addAll(Arrays.stream(temp).map(e -> (T) e.t).collect(Collectors.toList()));

            return;
        }

        int size = size();
        System.arraycopy(elements, from, elements, from + added.size(), size - from);

        for (int i = 0; i < added.size(); i++) {
            int index = from + i;

            T t = added.get(i);
            Element e = new Element(t);

            int pos = findPosition(e, index, size);

            if (pos < 0) {
                pos = ~pos;
            }

            elements[index] = e;

            if (pos < size) {
                System.arraycopy(sortedElements, pos, sortedElements, pos + 1, size - pos);
            }

            sortedElements[pos] = e;

            add(pos, t);
            size++;
        }
    }

    /**
     * Remove the elements from this binding that were removed from the source list.
     * Update the {@link #elements} mapping.
     *
     * @param source The source list.
     * @param from The index of where the removal started in the source (inclusive).
     * @param removedSize The total number of removed elements from the source list
     *            for the change.
     */
    @SuppressWarnings({})
    private void removed(List<? extends T> source, int from, int removedSize) {
        if (source.size() == 0) {
            elements = newElementArray(10);
            sortedElements = newElementArray(10);
            elementCounter = Integer.MIN_VALUE;
            clear();
            return;
        }

        int oldSize = size();
        int size = oldSize;

        for (int i = 0; i < removedSize; i++) {
            int index = from + i;

            Element e = elements[index];

            int pos = findPosition(e, index, size);

            System.arraycopy(sortedElements, pos + 1, sortedElements, pos, size - pos - 1);

            remove(pos);
            sortedElements[--size] = null;
        }

        System.arraycopy(elements, from + removedSize, elements, from, oldSize - from - removedSize);

        for (int i = size; i < oldSize; i++) {
            elements[i] = null;
        }
    }

    /**
     * Locate the position of the element in this sorted binding by performing a
     * binary search. A binary search locates the index of the add in Olog(n) time.
     *
     * @param e The element to insert.
     * @param sourceIndex The index of the source list of the modification.
     * @param size The size of the array to search, exclusive.
     *
     * @return The position in this binding that the element should be inserted.
     */
    private int findPosition(Element e, int sourceIndex, int size) {
        if (size() == 0) {
            return 0;
        }

        int pos;

        if (elementComparator != null) {
            pos = Arrays.binarySearch(sortedElements, 0, size, e, elementComparator);
        } else {
            pos = sourceIndex;
        }

        return pos;
    }

    /**
     * Ensure that the element array is large enough to handle new elements from the
     * source list. Also shrinks the size of the array if it has become too large
     * with respect to the source list.
     *
     * @param size The minimum size of the array.
     */
    private void ensureSize(int size) {
        if (size >= elements.length) {
            int newSize = size * 3 / 2 + 1;

            Element[] replacement = newElementArray(newSize);
            System.arraycopy(elements, 0, replacement, 0, elements.length);
            elements = replacement;

            replacement = newElementArray(newSize);
            System.arraycopy(sortedElements, 0, replacement, 0, sortedElements.length);
            sortedElements = replacement;

        } else if (size < elements.length / 4) {
            int newSize = size * 3 / 2 + 1;

            Element[] replacement = newElementArray(newSize);
            System.arraycopy(elements, 0, replacement, 0, replacement.length);
            elements = replacement;

            replacement = newElementArray(newSize);
            System.arraycopy(sortedElements, 0, replacement, 0, replacement.length);
            sortedElements = replacement;
        }
    }

    /**
     * Combines the {@link #comparatorProperty() item comparator} with a secondary
     * comparison if the items are equal through the <i>compareTo</i> operation. This
     * is used to quickly find the original item when 2 or more items have the same
     * comparison.
     */
    private Comparator<Element> elementComparator;

    /**
     * @see #comparatorProperty()
     */
    private ObjectProperty<Comparator<? super T>> comparator =
        new SimpleObjectProperty<Comparator<? super T>>(this, "comparator") {
            @Override
            protected void invalidated() {
                Comparator<? super T> comp = get();

                if (comp != null) {
                    elementComparator = Comparator.nullsLast((e1, e2) -> {
                        int c = comp.compare(e1.t, e2.t);
                        return c == 0 ? Integer.compare(e1.id, e2.id) : c;
                    });
                } else {
                    elementComparator = null;
                }
            }
        };

    @Override
    public final ObjectProperty<Comparator<? super T>> comparatorProperty() {
        return comparator;
    }

    @Override
    public final Comparator<? super T> getComparator() {
        return comparatorProperty().get();
    }

    @Override
    public final void setComparator(Comparator<? super T> comparator) {
        comparatorProperty().set(comparator);
    }

    @Override
    protected void onInvalidating(ObservableList<T> source) {
        clear();
        ensureSize(source.size());
        added(source, 0, source);
    }

    /**
     * Counter starts at the Integer min value, and increments each time a new
     * element is requested. If this list becomes empty, the counter is restarted at
     * the min value.
     */
    private int elementCounter = Integer.MIN_VALUE;

    /**
     * Generate a new array of {@code Element}.
     *
     * @param size The size of the array.
     *
     * @return A new array of null Elements.
     */
    @SuppressWarnings("unchecked")
    private Element[] newElementArray(int size) {
        return new ListContentSortBinding.Element[size];
    }

Wrapper Element Class

    /**
     * Wrapper class to further aid in comparison of two object types <T>. Since
     * sorting in a list allows duplicates we must assure that when a removal occurs
     * from the source list feeding this binding that the removed element matches. To
     * do this we add an arbitrary <i>int</i> field inside this element class that
     * wraps around the original object type &lt;T>.
     */
    final class Element {
        /** Object */
        private final T t;
        /** ID helper for T type duplicates */
        private int id;

        Element(T t) {
            this.t = Objects.requireNonNull(t);
            this.id = elementCounter++;
        }

        @Override
        public String toString() {
            return t.toString() + " (" + id + ")";
        }
    }
}

JUNIT VERIFICATION TEST

@Test
public void testSortBinding() {
    ObservableList<IntWrapper> source = FXCollections.observableArrayList();

    int size = 100000;

    for (int i = 0; i < size / 2; i++) {
        int index = (int) (Math.random() * size / 10);
        source.add(new IntWrapper(index));
    }

    ListContentSortBinding<IntWrapper> binding =
        (ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();

    Assert.assertEquals("Sizes not equal for sorted binding | Expected: " +
        source.size() + ", Actual: " + binding.size(),
        source.size(), binding.size());

    List<IntWrapper> sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Equal: Complete.");

    // Randomly add chunks of elements at random locations in the source

    int addSize = size / 10000;

    for (int i = 0; i < size / 4; i++) {
        List<IntWrapper> added = new ArrayList<>();
        int toAdd = (int) (Math.random() * addSize);

        for (int j = 0; j < toAdd; j++) {
            int index = (int) (Math.random() * size / 10);
            added.add(new IntWrapper(index));
        }

        int atIndex = (int) (Math.random() * source.size());
        source.addAll(atIndex, added);
    }

    sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Equal - Add Multiple Elements: Complete.");

    // Remove one element at a time from the source list and compare
    // to the elements that were removed from the sorted binding
    // as a result. They should all be identical index for index.

    List<IntWrapper> sourceRemoved = new ArrayList<>();
    List<IntWrapper> bindingRemoved = new ArrayList<>();

    ListChangeListener<IntWrapper> bindingListener = change -> {
        while (change.next()) {
            if (change.wasRemoved()) {
                bindingRemoved.addAll(change.getRemoved());
            }
        }
    };

    // Watch the binding for changes after the upstream source changes

    binding.addListener(bindingListener);

    for (int i = 0; i < size / 4; i++) {
        int index = (int) (Math.random() * source.size());
        IntWrapper removed = source.remove(index);
        sourceRemoved.add(removed);
    }

    for (int i = 0; i < bindingRemoved.size(); i++) {
        IntWrapper expected = bindingRemoved.get(i);
        IntWrapper actual = sourceRemoved.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected + ", Actual: " + actual,
            expected.value, actual.value);

        Assert.assertEquals("Element refs not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.r, actual.r, 0);
    }

    System.out.println("Sorted Remove Single Element: Complete.");

    // Replace random elements from the source list

    bindingRemoved.clear();
    sourceRemoved.clear();
    int removeSize = size / 10000;

    for (int i = 0; i < size / 1000; i++) {
        int replaceIndex = (int) (Math.random() * source.size());

        int index = (int) (Math.random() * size / 10);
        IntWrapper replace = new IntWrapper(index);

        source.set(replaceIndex, replace);
    }

    sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Replace: Complete.");

    // Remove random chunks from the source list

    bindingRemoved.clear();
    sourceRemoved.clear();
    Set<IntWrapper> sourceRemovedSet =
        Collections.newSetFromMap(new IdentityHashMap<>()); // set for speed

    while (source.size() > 0) {
        int index = (int) (Math.random() * source.size());
        int toRemove = (int) (Math.random() * removeSize);
        toRemove = Math.min(toRemove, source.size() - index);

        List<IntWrapper> removed = source.subList(index, index + toRemove);
        sourceRemovedSet.addAll(new ArrayList<>(removed));

        removed.clear(); // triggers list change update to binding
    }

    Assert.assertEquals(bindingRemoved.size(), sourceRemovedSet.size());

    // The binding removed will not necessarily be placed in the same order
    // since the change listener on the binding will make sure that the final
    // order of the change from the binding is in the same order as the binding
    // element sequence. We therefore must do a contains() to test.

    for (int i = 0; i < bindingRemoved.size(); i++) {
        IntWrapper expected = bindingRemoved.get(i);

        Assert.assertTrue("Binding Removed Did Not Contain Source Removed",
            sourceRemovedSet.contains(expected));
    }

    System.out.println("Sorted Removed Multiple Elements: Complete.");
}

JUNIT BENCHMARK TEST

  @Test
public void sortBindingBenchmark() {
    ObservableList<IntWrapper> source = FXCollections.observableArrayList();

    ObservableList<IntWrapper> binding =
        (ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();

    int size = 200000;

    Set<IntWrapper> toAdd = new TreeSet<>();

    while (toAdd.size() < size) {
        int index = (int) (Math.random() * size * 20);
        toAdd.add(new IntWrapper(index));
    }

    // Randomize the order
    toAdd = new HashSet<>(toAdd);

    System.out.println("Sorted Binding Benchmark Setup: Complete.");

    long time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        source.add(w);
    }

    long bindingTime = System.currentTimeMillis() - time;

    System.out.println("Sorted Binding Time: Complete.");

    source.clear(); // clear the list and re-add

    ObservableList<IntWrapper> sortedList = new SortedList<>(source);

    time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        source.add(w);
    }

    long sortedListTime = System.currentTimeMillis() - time;

    System.out.println("JavaFX Sorted List Time: Complete.");

    // Make the test "fair" by adding a listener to an observable
    // set that populates the sorted set

    ObservableSet<IntWrapper> obsSet = FXCollections.observableSet(new HashSet<>());
    Set<IntWrapper> sortedSet = new TreeSet<>();

    obsSet.addListener((SetChangeListener<IntWrapper>) change -> {
        sortedSet.add(change.getElementAdded());
    });

    time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        obsSet.add(w);
    }

    long setTime = System.currentTimeMillis() - time;

    System.out.println("Sorted Binding Benchmark Time: Complete");

    Assert.assertEquals(sortedSet.size(), binding.size());

    System.out.println("Binding: " + bindingTime + " ms, " +
        "JavaFX Sorted List: " + sortedListTime + " ms, " +
        "TreeSet: " + setTime + " ms");
}

Wrapper Class for Tests Only

    /**
     * Wrapper class for testing sort bindings. Verifies that duplicates were sorted
     * and removed correctly based on the object instance.
     */
private static class IntWrapper implements Comparable<IntWrapper> {
    static int counter = Integer.MIN_VALUE;
    final int value;
    final int id;

    IntWrapper(int value) {
        this.value = value;
        this.id = counter++;
    }

Galbanum

The results of the 'JUnit Benchmark Test' are as follows: – Galbanum

TreeSet: 330 ms – Galbanum

Binding: 16611 ms – Galbanum

JavaFX Sorted List: 165826 ms – Galbanum

Parameters: Randomly add 200,000 (non-duplicate) Randomized IntWrapper test items to each of the following: ListContentSortBinding (my class), SortedList (JavaFX), and TreeSet. – Galbanum

The JavaFX SortedList is absolutely terrible, probably due to all the indexing updates. I get around this in the class I have because binarySearch() is used for both adding AND removing the correct object, by using the extra 'int ID' object in the Element wrapper class. TreeSet is beast. – Galbanum

The ListContentSortBinding is slower than Ologn, due to the overhead of System.arrayCopy() each time the array of sorted elements must be changed. I don't really see a way around this. – Galbanum

However due to the nature of array backed lists the System.arrayCopy has an overhead proportional to O(n^2). Therefore a single add/remove operation on this sorted list is on the order of: t = k1 * O(logn) + k2 * O(n^2) – Galbanum

Answer 12

I also find it mind-boggling that this does not exist in the Java standard libraries. (But good luck with proposing the addition of any new class to the JDK team! I have never had luck with that.)

Assuming that your compareTo function is a proper transitive relation, then the fastest algorithm for this (assuming the list is read approximately as many times as it is written) is to override List.add with a method that performs a binary search to find the insertion point of the new item before inserting it. This is O(log(N)) in the number of added elements.

Dowitcher

I'm surprised this is mind-boggling to you. The need for a self-sorting List in particular seems very rare and easy to implement on one's own. – Spindling

@KartikChugh Please tell me you don't re-implement every collection class every time you need one. There is a reason we have standard libraries. – Dowitcher

Standard libraries are for operations that are commonly used - Java definitely has a problem of underinclusion, but a self-sorting list is not one of them (evident by the lack of inclusion in most other languages' standard libraries) – Spindling

@KartikChugh I have needed this functionality dozens of times during my career. I have had to resort to a priority queue (not iterable in most implementations), or had to keep re-sorting the list. Java at least has a TreeMap that allows you to traverse the keys in order, but the keys have to be unique, so it is not a solution to this problem. You can use a heap, but you have to remove items from the heap to traverse them in order. Balanced tree algos work but are complex to implement, which is one very strong justification for their inclusion in standard libraries that you didn't mention. – Dowitcher

Answer 13

The best way to do this would be to override the add implementation of a list. I'm going to use a LinkedList to demonstrate it, as it allows for efficient insertion.

public boolean add(Integer e)
{
    int i = 0;
    for (Iterator<Integer> it = this.iterator(); it.hasNext();)
    {
        int current = it.next();
        if(current > e)
        {
            super.add(i, e);
            return true;
        }
        i++;
    }
    return super.add(e);
}

The above code creates a sorted list of integers, that is always sorted. It can easily be modified to work with any other datatype. However here you will have to avoid using the add(index, value) function, as that would obviously break the sorting.

Although people above suggested using Arrays.sort(), I would avoid that, as it can be a significantly less efficient approach, especially since the sort method must be called with every addition to the list.

Diva

Yeah, If I were to use a ArrayList, I'd definitely go with Binarysearch.However, I chose to go with a LinkedList, because I was going for efficient insertion. If efficient traversal were important, I'd do it differently. – Diva

This solution is O(n^2) to insert n elements. – Trench

Yes, as oppsed to O(n^3) if arrays.sort uses insertion-sort, or O(n^2 log n) if it uses something like quick-sort. – Diva

those comparisons are correct except for two things. 1: java.util.Arrays.sort and java.util.Collections.sort both guarantee O(nlog(n)) behavior. 2: The correct comparison is vs a self-balancing binary search tree, which gives O(nlog(n)) total to insert n elements. – Trench

The use of the iterator is good, but this solution will still require 2 scans of the list: one to find the insertion point, and then another to perform the insertion. It would be more efficient to use a ListIterator. I will post an example. – Steve

Answer 14

The contract of the ListIterator interface makes it a bit cumbersome, but this method will perform the insertion using a single scan of the list (up to the insertion point):

private void add(Integer value) {
    ListIterator<Integer> listIterator = list.listIterator();

    Integer next = null;

    while (listIterator.hasNext()) {
        next = listIterator.next();

        if (next.compareTo(value) > 0) {                
            break;
        }
    }

    if (next == null || next.compareTo(value) < 0) {
        listIterator.add(value);
    } else {
        listIterator.set(value);
        listIterator.add(next);
    }
}

Steve

Answer 15

SortedSet

Any implementation of the SortedSet interface carries your desired behavior.

By default, objects added are sorted in their natural order, that is, based on their implementation of the Comparable::compareTo interface method.

Alternatively, you can pass a Comparator implementation to determine the sort.

TreeSet

The TreeSet is a commonly used implantation of SortedSet. You can also find others.

Duplicates

The major difference between a List and a SortedSet is duplicates, objects that compare as equal. A List allows duplicates whereas a SortedSet, like any Set, does not.

Access by index

Another difference is that a Set cannot be accessed by index. You can not locate an object by its position number within the collection.

If you need such access after constructing your SortedSet, make a List. There are multiple ways to do this, such as passing the SortedSet to constructor of ArrayList. A mote recent way, as of Java 10, is to make an umodifiable List by passing the SortedSet to List.copyOf.

Chelsae

Answer 16

As stated clearly prior, the need for a sorted list over a SortedSet is the need for indexing and duplicates. I needed both.

As of Java8, java.util.List<E> has a "conscientious" List<E>.sort() method.

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted.

My list is pre-loaded prior to being referenced and load-order is almost always the order; references need to be very fast. Therefore, the only change to user177800's answer is for me to defer to the now provided sort:

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    /**
    * this ignores the index and delegates to .add() 
    * so it will be sorted into the correct place immediately.
    */
    @Override
    public void add(int index, Object element)
    {
        this.add(element);     
    }

    @Override
    public boolean add(final E e)
    {
        final boolean result = super.add(e);
        this.sort(this, this.comparator);
        return result;
    }
}

I don't know how many items will be held ahead, so LinkedList<E>.

Aaaand now I notice that Collections.sort(List<T> list, Comparator<? super T> c) now defers to List.sort(c). 🤷

Hearten

Answer 17

I believe a Priority Queue will do the job.

Caveat (from the same doc page):

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Heritage

iteration of a PriorityQueue does NOT perserve order, and the most common reason to sort a List is to iterate over it in a specific sorted order. – Threadfin

A downvote based on an assumption that the OP did not explicitly state? Nice. Adding the caveat anyway... – Heritage

PriorityQueue does not implement the List interface. The OP explicitly states they want a List. – Threadfin