Sorted List

Sorted List

SortedList is an decorator, which can be used to decorate java.util.List. Unlike to many SortedList implementations, the decorator can be dynmiclly added and removed from the prgram-control-flow. Also the decorator can be combined with diffrent list-implemetations to find the best sollution.

How to create SortedList

The SortedList can be created like any other decorators, see an example below:

//create SortedList
List sortedList = 
    SortedList_1x0.of(    new ArrayList(), 
                        new Comparator(){
                            @Override
                            public int compare(Integer o1, Integer o2) {
                                return o1.compareTo(o2);
                            }
                        });

The performance of the decorated TreeList with SortedList

SortedList can be used to decorate any java.util.List types, thus if you have your own java.util.List-implementation and you want to have it sorted, you can use the SortedList. Because of the binary search the SortedList can dramatically improve the performance. Of course the inserting of the new element produce some overhead, but the searching of the elements is very fast. And so for example if the method List.remove(E obj) will be called, the element, which should be removed, will be found very fast.

But be careful, it is very important which list you want to decorate with the SortedList. For example if you use ArrayList, then big overhead will be produced to hold the ArrayList as sorted. That’s because the inserting of new elements in the middle of the list causes very slow operations. If you use the LinkedList then you can't use binary search methods, because LinkedList .get(index i) method is very slow. The solution for such dilemma is for example the TreeList form appache-collections library. By decorating of the TreeList with the SortedList the performance can dramatically increased. For example assume the three important methods of the java.util.List will be called with the following probabilities:

method	probability
add	20%
remove	20%
contains	60%

Here you find the benchmark which compares the decorated TreeList with the ArrayList.

The performance of the List has increased about ten times (1000%). The performance is not as fast as the java.util.SortedSet, but only few times slower. Don't forget the set can't have duplicates and it is not decorated, but directly implemented.

See more examples in the examples section!