Is there an indexable sorted list in the Java.util

问题:

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?

回答1:

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.

回答2:

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.

回答3:

This question is very similar to

• Sorted array list in Java

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 2³¹-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.)

回答4:

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.

回答5:

Consider List combined with Collections.sort().

回答6:

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

回答7:

Look at PriorityQueue.

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