В Java есть такие SortedSetи SortedMapинтерфейсы. Оба принадлежат платформе Java Collections и предоставляют отсортированный способ доступа к элементам.

Тем не менее, в моем понимании нет SortedListв Java. Вы можете использовать java.util.Collections.sort()для сортировки списка.

Есть идеи, почему он так устроен?

Итераторы списка гарантируют, прежде всего, то, что вы получите элементы списка во внутреннем порядке списка (он же порядок вставки ). Точнее, в том порядке, в котором вы вставили элементы, или о том, как вы манипулировали списком. Сортировка может рассматриваться как манипулирование структурой данных, и существует несколько способов сортировки списка.

Я закажу пути в порядке полезности, как лично вижу:

1. Рассмотрите возможность использования Setили Bagколлекции вместо

ПРИМЕЧАНИЕ: я поставил эту опцию сверху, потому что это то, что вы обычно хотите делать в любом случае.

Сортированный набор автоматически сортирует коллекцию при вставке , что означает, что он выполняет сортировку при добавлении элементов в коллекцию. Это также означает, что вам не нужно сортировать вручную.

Кроме того, если вы уверены, что вам не нужно беспокоиться о (или иметь) дубликаты элементов, вы можете использовать TreeSet<T>вместо этого. Он реализует SortedSetи NavigableSetинтерфейсы и работает , как вы, вероятно , планирующие из списка:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Если вы не хотите естественного упорядочения, вы можете использовать параметр конструктора, который принимает Comparator<T>.

В качестве альтернативы, вы можете использовать Multisets (также известный как Bags ) , то есть, Setкоторый позволяет дублировать элементы, и есть их сторонние реализации. В частности, из библиотек Guava есть TreeMultiset, который работает так же, как TreeSet.

2. Сортируйте свой список с помощью Collections.sort()

Как упоминалось выше, сортировка Lists - это манипулирование структурой данных. Так что для ситуаций, когда вам нужен «один источник правды», который будет отсортирован различными способами, тогда сортировка вручную - это путь.

Вы можете отсортировать свой список с помощью java.util.Collections.sort()метода. Вот пример кода о том, как:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Использование компараторов

Одно очевидное преимущество заключается в том, что вы можете использовать Comparatorэтот sortметод. Java также предоставляет некоторые реализации для Comparatorтаких, как, например, Collatorкоторые полезны для строк сортировки, чувствительных к локали. Вот один пример:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Сортировка в параллельных средах

Тем не менее, обратите внимание, что использование sortметода не подходит для параллельных сред, поскольку экземпляром коллекции будет манипулировать, и вам следует рассмотреть возможность использования неизменяемых коллекций. Это то, что Guava предоставляет в Orderingклассе, и это простая однострочная строка:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Оберните ваш список java.util.PriorityQueue

Хотя в Java нет отсортированного списка, тем не менее есть отсортированная очередь, которая, вероятно, сработает для вас. Это java.util.PriorityQueueкласс.

Нико Хааз в комментариях связался с соответствующим вопросом, который также отвечает на этот вопрос.

В отсортированной коллекции вы, скорее всего, не хотите манипулировать внутренней структурой данных, поэтому PriorityQueue не реализует интерфейс List (потому что это даст вам прямой доступ к его элементам).

Будьте осторожны с PriorityQueueитератором

В PriorityQueueклассе реализует Iterable<E>и Collection<E>интерфейсы , поэтому он может быть итерированным как обычно. Тем не менее, итератор не гарантированно возвращает элементы в отсортированном порядке. Вместо этого (как указывает Альдерат в комментариях), вам нужно poll()стоять в очереди, пока она не опустеет.

Обратите внимание, что вы можете преобразовать список в приоритетную очередь через конструктор, который принимает любую коллекцию :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Напишите свой собственный SortedListкласс

ПРИМЕЧАНИЕ. Вам не нужно этого делать.

Вы можете написать свой собственный класс List, который сортирует каждый раз, когда вы добавляете новый элемент. Это может привести к значительным вычислительным нагрузкам в зависимости от вашей реализации и будет бессмысленным , если только вы не захотите сделать это в качестве упражнения по двум основным причинам:

1. Это нарушает контракт, который List<E>имеет интерфейс, потому что addметоды должны гарантировать, что элемент будет находиться в индексе, указанном пользователем.
2. Зачем изобретать велосипед? Вместо этого вы должны использовать TreeSet или Multisets, как указано в первом пункте выше.

Однако, если вы хотите сделать это в качестве упражнения, вот пример кода для начала работы, он использует AbstractListабстрактный класс:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Обратите внимание, что если вы не переопределили нужные вам методы, то реализации по умолчанию AbstractListсгенерируют UnsupportedOperationExceptions.

Потому что концепция списка несовместима с концепцией автоматически отсортированной коллекции. Смысл списка состоит в том, что после вызова list.add(7, elem)вызов list.get(7)будет возвращен elem. С автоматически отсортированным списком элемент может оказаться в произвольной позиции.

Поскольку все списки уже «отсортированы» по порядку добавления элементов (упорядочение по FIFO), вы можете «прибегнуть» к ним с другим порядком, включая естественное упорядочение элементов, используя java.util.Collections.sort().

РЕДАКТИРОВАТЬ:

Списки как структуры данных основаны на том, что интересует порядок, в котором элементы были вставлены.

Наборы не имеют этой информации.

Если вы хотите заказать, добавив время, используйте List. Если вы хотите заказать по другим критериям, используйте SortedSet.

Set и Map являются нелинейной структурой данных. Список представляет собой линейную структуру данных.

Древовидная структура данных SortedSetи SortedMapинтерфейсы реализуют TreeSetи TreeMapсоответственно используют используемый алгоритм реализации красно-черного дерева . Так что убедитесь, что нет дублирующихся предметов (или ключей в случае Map).

• List уже поддерживает упорядоченную коллекцию и структуру данных на основе индекса, деревья не являются структурами данных на основе индекса.
• Tree по определению не может содержать дубликатов.
• У Listнас могут быть дубликаты, поэтому их нет TreeList(т.е. нет SortedList).
• Список поддерживает элементы в порядке вставки. Так что, если мы хотим отсортировать список, мы должны использовать java.util.Collections.sort(). Он сортирует указанный список в порядке возрастания в соответствии с естественным порядком его элементов.

JavaFX SortedList

Хотя это заняло некоторое время, в Java 8 есть сортировка List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Как вы можете видеть в javadocs, это часть коллекций JavaFX , предназначенная для предоставления отсортированного представления в ObservableList.

Обновление: обратите внимание, что в Java 11 инструментарий JavaFX вышел за пределы JDK и теперь является отдельной библиотекой. JavaFX 11 доступен в виде загружаемого SDK или от MavenCentral. Смотрите https://openjfx.io

Для любого новичка, начиная с апреля 2015 года, Android теперь имеет класс SortedList в библиотеке поддержки, специально разработанный для работы с ним RecyclerView. Вот пост в блоге об этом.

Другой момент - временная сложность операций вставки. Для вставки списка ожидается сложность O (1). Но это не может быть гарантировано с отсортированным списком.

И самое главное, списки ничего не предполагают об их элементах. Например, вы можете составить списки вещей, которые не реализуются equalsили compare.

Думайте об этом так: Listинтерфейс имеет такие методы , как add(int index, E element), set(int index, E element). Контракт заключается в том, что, как только вы добавили элемент в позиции X, вы найдете его там, если вы не добавите или не удалите элементы перед ним.

Если любая реализация списка будет хранить элементы в каком-то порядке, отличном от индекса, вышеприведенные методы списка не будут иметь смысла.

Первая строка в List API говорит, что это упорядоченная коллекция (также известная как последовательность). Если вы сортируете список, вы не можете поддерживать порядок, поэтому в Java нет TreeList.
Как говорит API, Java List вдохновлен Sequence и видит свойства последовательности http://en.wikipedia.org/wiki/Sequence_(matmatics )

Это не значит, что вы не можете отсортировать список, но Java строго его определена и не предоставляет отсортированные версии списков по умолчанию.

В случае, если вы ищете способ сортировки элементов, но также можете эффективно обращаться к ним по индексу, вы можете сделать следующее:

1. Используйте список произвольного доступа для хранения (например ArrayList)
2. Убедитесь, что он всегда отсортирован

Затем, чтобы добавить или удалить элемент, вы можете использовать, Collections.binarySearchчтобы получить индекс вставки / удаления. Поскольку в вашем списке реализован произвольный доступ, вы можете эффективно изменить список с помощью определенного индекса.

Пример:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}

Рассмотрите возможность использования indexed-tree-map . Это расширенный набор JDK TreeSet, который предоставляет доступ к элементу по индексу и находит индекс элемента без итерации или скрытых базовых списков, которые поддерживают дерево. Алгоритм основан на обновлении весов смены узлов каждый раз, когда происходит изменение.