javalistcollectionsinsertion-order

List implementation that maintains ordering


Is there an existing List implementation in Java that maintains order based on provided Comparator?

Something that can be used in the following way:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

so that someT gets inserted such that the order in the list is maintained according to cmp

(On @andersoj suggestion I am completing my question with one more request)

Also I want to be able to traverse the list in sorted order without removing the elements, i.e:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

should pass.

All suggestions are welcome (except telling me to use Collections.sort on the unordered full list), though, I would prefer something in java.* or eventually org.apache.* since it would be hard to introduce new libraries at this moment.

Note: (UPDATE4) I realized that implementations of this kind of list would have inadequate performance. There two general approaches:

  1. Use Linked structure (sort of) B-tree or similar
  2. Use array and insertion (with binary search)

No 1. has problem with CPU cache misses No 2. has problem with shifting elements in array.

UPDATE2: TreeSet does not work because it uses the provided comparator (MyComparator) to check for equality and based on it assumes that the elements are equal and exclude them. I need that comparator only for ordering, not "uniqueness" filtering (since the elements by their natural ordering are not equal)

UPDATE3: PriorityQueue does not work as List (as I need) because there is no way to traverse it in the order it is "sorted", to get the elements in the sorted order you have to remove them from the collection.

UPDATE:

Similar question:
A good Sorted List for Java
Sorted array list in Java


Solution

  • Response to new requirement. I see two potentials:

    The below addresses the uniqueness/filtering problem you were having when using a SortedSet. I see that you also want an iterator, so this won't work.

    If what you really want is an ordered list-like thing, you can make use of a PriorityQueue.

    Comparator<T> cmp = new MyComparator<T>();
    PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
    pq.add(someT);
    

    Take note of what the API documentation says about the time properties of various operations:

    Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

    You should also be aware that the iterators produced by PriorityQueue do not behave as one might expect:

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

    I just noticed that Guava provides a MinMaxPriorityQueue. This implementation is array-backed, rather than the linked form provided in the JDK's PriorityQueue, and thus likely has different timing behavior. If you're doing something performance sensitive, you may wish to take a look. While the notes give slightly different (linear and logarithmic) big-O times, all those times should also be bounded, which may be useful.

    There is not a List implementation per se that maintains ordering, but what you are likely looking for are implementations of SortedSet. A TreeSet is the most common. The other implementation, a ConcurrentSkipListSet is for more specific uses. Note that a SortedSet provides ordering, but does not allow duplicate entries, as does a List.

    Refs: