20

I'm looking for a data structure in the java.util package. I need it to meet the following requirements:

  • The number of elements is (theoretically) unbounded.
  • The elements are sorted in an ascending order.
  • You can get the nth element (fast).
  • You can remove the nth element (fast).

I expected to find an indexable skip list, but I didn't. Do they have any data structure which meets the requirements I'v stated?

snakile
  • 52,936
  • 62
  • 169
  • 241

7 Answers7

6

There is no such container in the Java standard libraries.

When I need a data structure with these properties, I use a List implementation (generally an ArrayList, but it doesn't matter), and I do all the insertions using Collections.binarySearch.

If I had to encapsulate a sorted list as a reusable class, I'd implement the List interface, delegating all methods to a 'standard' List implementation (it can even be passed as a parameter to the constructor). I'd implement every insertion method (add, addAll, set, Iterator's remove) by throwing an exception (UnsupportedOperationException), so that nobody can break the 'always sorted' property. Finally, I'd provide a method insertSorted that would use Collections.binarySearch to do the insertion.

barjak
  • 10,842
  • 3
  • 33
  • 47
3

There exists no simple data structure that fulfills all your criteria.

The only one that I know which does fulfills them all would be an indexable skip list. Hoewever,I don't know of any readily available Java implementations.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • Another data structure is an indexable search tree. A simple example is a binary search tree that also stores that size of the subtree at each node. – Travis Jan 10 '18 at 16:03
2

This question is very similar to

Have a look at my answer to that question.

Basically it suggests the following:

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

A note on your first requirement: "The number of elements is unbounded.":

You may want to restrict this to something like "The number of elements should not be bound by less than 231-1..." since otherwise you're ruling out all options which are backed by a Java array. (You could get away with an arbitrary number of elements using for instance a LinkedList, but I can't see how you could do fast lookups in that.)

Community
  • 1
  • 1
aioobe
  • 413,195
  • 112
  • 811
  • 826
  • 3
    Extending a specific collection implementation is rarely a good idea. Especially when you try to enforce a new contract (the add methods can break the sort, in your case). Look at the `Properties` class for a good example of what *not* to do ! – barjak Nov 22 '10 at 19:28
  • Deleting from an ArrayList is an O(n) operation. I don't have any better ideas, but thought that should be pointed out. – user506069 Nov 22 '10 at 19:33
  • @barjak, that's a good point. One could for instance override these methods and just throw an UnsupportedOperationException. Still though, I can't see why it would be better to implement the List interface from scratch just because of this... – aioobe Nov 22 '10 at 19:37
  • @user852631, good point. It should also be note that the `insertSorted` is also in O(n) while it perhaps could have been implemented in O(log n) by using a different data structure. – aioobe Nov 22 '10 at 19:38
  • because there is no reason to be tied to `ArrayList`. For example, if you want a `SortedList` with the "iterator never fails" property, then your solution can't be reused. You'd have to redo the same work, but this time extending `CopyOnWriteArrayList` instead of `ArrayList`. If you use composition instead of inheritance here, then you can use any implementation backend you want (at instanciation time, for example). This is the mistake of the `Properties` class : it extends the almost-deprecated `Hashtable` class, and this fact can't be changed anymore. – barjak Nov 23 '10 at 10:05
1

TreeSet provides you the functionality of natural sorting while adding elements to the list. But if you don't need this and Collections.sort() is permitted you can use simple ArrayList.

Vladimir Ivanov
  • 42,730
  • 18
  • 77
  • 103
  • 2
    ArrayList - elements are not ordered. TreeSet - cannot get/remove the nth element (can only get/remove an element if I have a key) – snakile Nov 22 '10 at 18:58
  • Yes, I know, but it can be sorted, if, for example the collection is fullfilled up to the some moment and not updated any more. – Vladimir Ivanov Nov 22 '10 at 19:00
0

Consider List combined with Collections.sort().

DwB
  • 37,124
  • 11
  • 56
  • 82
0

Going with what dwb stated with List<T> and Collections.sort(), you can use ArrayList<T> as that implements List<T> (and is not synchronized like Vector<T> unless of course you want that overhead). That is probably your best bet because they (Sun) typically do lots of research into these areas (from what I've seen anyway). If you need to sort by something other than the "default" (i.e. you are not sorting a list of integers, etc), then supply your own comparator.

EDIT: The only thing that does not meet your requirements are the fast removals...

Merky
  • 494
  • 2
  • 4
-1

Look at PriorityQueue.

If you don't need similar elements in your data structure, then usual TreeSet also fits your requirements.

Roman
  • 64,384
  • 92
  • 238
  • 332