Is there an indexable sorted list in the Java.util package?

Question

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?

Answer 1

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.