Есть ли индексируемый отсортированный список в пакете Java.util?

Question

Я ищу структуру данных в пакете java.util. Мне это нужно для удовлетворения следующих требований:

• Количество элементов (теоретически) не ограничено.
• Элементы отсортированы в порядке возрастания.
• Вы можете получить n-й элемент (быстро).
• Вы можете удалить n-й элемент (быстро).

Я ожидал найти индексируемый список пропусков, но не нашел. Есть ли у них какая-либо структура данных, которая соответствует заявленным мною требованиям?

Answer 1

В стандартных библиотеках Java такого контейнера нет.

Когда мне нужна структура данных с этими свойствами, я использую реализацию List (обычно ArrayList, но это не имеет значения), и я делаю все вставки, используя Collections.binarySearch.

Если бы мне пришлось инкапсулировать отсортированный список как класс многократного использования, я бы реализовал интерфейс List, делегировав все методы«стандартная» реализация List (она может даже передаваться в качестве параметра конструктору).Я бы реализовал каждый метод вставки (add, addAll, set, итератор для удаления), создав исключение (UnsupportedOperationException), чтобы никто не мог сломать свойство «всегда отсортировано».Наконец, я бы предоставил метод insertSorted, который будет использовать Collections.binarySearch для выполнения вставки.

Answer 2

Не существует простой структуры данных, которая удовлетворяла бы всем вашим критериям.

Единственный, кого я знаю, который выполняет их все, будет индексируемый список пропусков . Однако я не знаю ни одной легко доступной реализации Java.

Answer 3

Этот вопрос очень похож на

• Список отсортированных массивов в Java

Посмотрите на мой ответ на этот вопрос .

В основном это предлагает следующее:

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

---

Примечание по первому требованию: « Количество элементов не ограничено. »:

Возможно, вы захотите ограничить это чем-то вроде «Количество элементов не должно быть меньше 2 ³¹ -1 ...», так как в противном случае вы исключаете все опции, которые поддерживаются массивом Java. (Вы могли бы избежать произвольного числа элементов, используя, например, LinkedList, но я не вижу, как вы могли бы сделать быстрый поиск в этом.)

Answer 4

TreeSet предоставляет вам функции естественной сортировки при добавлении элементов в список.Но если вам это не нужно, и Collections.sort () разрешен, вы можете использовать простой ArrayList.

Answer 5

Исходя из того, что dwb указано с List<T> и Collections.sort(), вы можете использовать ArrayList<T>, поскольку он реализует List<T> (и не синхронизируется, как Vector<T>, если, конечно, вы не хотите, чтобы эти издержки были)Это, вероятно, ваш лучший выбор, потому что они (Sun) обычно проводят много исследований в этих областях (из того, что я видел в любом случае).Если вам нужно отсортировать что-то, кроме «по умолчанию» (т. Е. Вы не сортируете список целых чисел и т. Д.), Укажите свой собственный компаратор.

РЕДАКТИРОВАТЬ: единственное, что не соответствует вашим требованиямбыстрые удаления ...

Answer 6

Рассмотрим List в сочетании с Collections.sort().

Answer 7

Посмотрите на PriorityQueue .

Если вам не нужны подобные элементы в вашей структуре данных, тогда обычный TreeSet также соответствует вашим требованиям.