W Javie są interfejsy SortedSeti SortedMap. Oba należą do środowiska Java Collections i zapewniają uporządkowany sposób dostępu do elementów.

Jednak w moim rozumieniu nie ma SortedListJava. Możesz użyć java.util.Collections.sort()do sortowania listy.

Masz pojęcie, dlaczego jest tak zaprojektowany?

Iteratory list gwarantują przede wszystkim, że elementy listy są uporządkowane wewnętrznie (np. Kolejność wstawiania ). Mówiąc dokładniej, jest to w kolejności wstawiania elementów lub sposobu manipulowania listą. Sortowanie może być postrzegane jako manipulacja strukturą danych i istnieje kilka sposobów sortowania listy.

Zamienię sposoby w kolejności użyteczności, tak jak ja to widzę:

1. Zastanów się nad użyciem Setlub Bagkolekcjami

UWAGA: Umieszczam tę opcję na górze, ponieważ i tak zwykle chcesz to zrobić.

Posortowany zestaw automatycznie sortuje kolekcję przy wstawianiu , co oznacza, że ​​wykonuje sortowanie podczas dodawania elementów do kolekcji. Oznacza to również, że nie trzeba go ręcznie sortować.

Ponadto, jeśli masz pewność, że nie musisz się martwić (lub mieć) zduplikowanymi elementami, możesz TreeSet<T>zamiast tego użyć . Implementuje SortedSeti NavigableSetinterfejsy oraz działa tak, jak można się spodziewać po liście:

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"

Jeśli nie chcesz naturalnego uporządkowania, możesz użyć parametru konstruktora, który przyjmuje parametr Comparator<T>.

Alternatywnie możesz użyć Multisets (znanych również jako Torby ) , czyli takich, Setktóre pozwalają na duplikowanie elementów, a są one ich implementacje innych firm. Przede wszystkim z bibliotek Guava istnieje taki TreeMultiset, który działa podobnie jak TreeSet.

2. Posortuj listę za pomocą Collections.sort()

Jak wspomniano powyżej, sortowanie Lists jest manipulacją strukturą danych. Tak więc w sytuacjach, w których potrzebujesz „jednego źródła prawdy”, które zostanie posortowane na różne sposoby, a następnie posortowanie go ręcznie.

Możesz posortować listę za pomocą java.util.Collections.sort()metody. Oto przykładowy kod:

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"

Korzystanie z komparatorów

Jedną z wyraźnych korzyści jest to, że możesz użyć Comparatortej sortmetody. Java zapewnia także pewne implementacje dla Comparatortakich, Collatorktóre są przydatne do łańcuchów sortujących wrażliwych na ustawienia regionalne. Oto jeden przykład:

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

Collections.sort(strings, usCollator);

Sortowanie w współbieżnych środowiskach

Należy jednak pamiętać, że użycie tej sortmetody nie jest przyjazne w środowiskach współbieżnych, ponieważ instancja kolekcji zostanie zmanipulowana, a zamiast tego należy rozważyć użycie niezmiennych kolekcji. Jest to coś, co Guava zapewnia w Orderingklasie i jest prostym, jedno-liniowym tekstem:

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

3. Zawiń listę java.util.PriorityQueue

Chociaż w Javie nie ma posortowanej listy, istnieje jednak posortowana kolejka, która prawdopodobnie będzie dla Ciebie równie dobra. To jest java.util.PriorityQueueklasa.

Nico Haase podał w komentarzach powiązane pytanie, które również na to odpowiada.

W posortowanej kolekcji najprawdopodobniej nie chcesz manipulować wewnętrzną strukturą danych, dlatego PriorityQueue nie implementuje interfejsu List (ponieważ to dałoby ci bezpośredni dostęp do jego elementów).

Zastrzeżenie dotyczące PriorityQueueiteratora

Do PriorityQueueklasy implementuje Iterable<E>i Collection<E>interfejsy więc może należy powtórzyć, jak zwykle. Jednak nie ma gwarancji, że iterator zwróci elementy w posortowanej kolejności. Zamiast tego (jak wskazuje Alderath w komentarzach) musisz stać w poll()kolejce, aż będzie pusty.

Zauważ, że możesz przekonwertować listę do kolejki priorytetowej za pomocą konstruktora, który pobiera dowolną kolekcję :

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. Napisz własną SortedListklasę

UWAGA: Nie powinieneś tego robić.

Możesz napisać własną klasę List, która będzie sortować za każdym razem, gdy dodasz nowy element. Może to być trudne do obliczeń w zależności od implementacji i jest bezcelowe , chyba że chcesz to zrobić jako ćwiczenie, z dwóch głównych powodów:

1. Łamie kontrakt, który List<E>ma interfejs, ponieważ addmetody powinny zapewnić, że element znajdzie się w indeksie określonym przez użytkownika.
2. Po co wymyślać koło ponownie? Zamiast tego powinieneś używać TreeSet lub Multisets, jak wskazano w pierwszym punkcie powyżej.

Jeśli jednak chcesz to zrobić jako ćwiczenie, tutaj jest próbka kodu na początek, korzysta z AbstractListklasy abstrakcyjnej:

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

}

Zauważ, że jeśli nie przesłoniłeś potrzebnych metod, wówczas domyślne implementacje z AbstractListwyrzucą UnsupportedOperationExceptions.

Ponieważ pojęcie listy jest niezgodne z pojęciem kolekcji automatycznie sortowanej. Punktem listy jest to, że po wywołaniu nastąpi powrót list.add(7, elem)do połączenia . Dzięki automatycznie posortowanej liście element może znaleźć się w dowolnej pozycji.list.get(7)elem

Ponieważ wszystkie listy są już „sortowane” według kolejności, w której elementy zostały dodane (kolejność FIFO), można „zastosować” je w innej kolejności, w tym naturalnej kolejności elementów java.util.Collections.sort().

EDYTOWAĆ:

Listy jako struktury danych oparte są na tym, co ciekawe, w kolejności, w której elementy zostały wstawione.

Zestawy nie zawierają tych informacji.

Jeśli chcesz zamówić, dodając czas, użyj List. Jeśli chcesz zamówić według innych kryteriów, użyj SortedSet.

Zestaw i mapa to nieliniowa struktura danych. Lista jest liniową strukturą danych.

Struktura danych drzewa SortedSeti SortedMapinterfejsy są implementowane TreeSeti TreeMapodpowiednio używane algorytm implementacji drzewa czerwono-czarnego . Więc upewnij się, że nie ma zduplikowanych elementów (lub kluczy w przypadku Map).

• List utrzymuje już uporządkowaną kolekcję i strukturę danych opartą na indeksie, drzewa nie są strukturami opartymi na indeksie.
• Tree z definicji nie może zawierać duplikatów.
• W Listmożemy mieć duplikaty, więc nie maTreeList (tj. Nie SortedList).
• Lista zachowuje elementy w kolejności wstawiania. Więc jeśli chcemy posortować listę, musimy użyć java.util.Collections.sort(). Sortuje określoną listę w porządku rosnącym, zgodnie z naturalnym uporządkowaniem jej elementów.

JavaFX SortedList

Chociaż zajęło to trochę czasu, Java 8 ma posortowane List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Jak widać w javadocs, jest to część kolekcji JavaFX , która ma zapewnić posortowany widok na ObservableList.

Aktualizacja: należy pamiętać, że w Javie 11 zestaw narzędzi JavaFX został przeniesiony poza JDK i jest teraz osobną biblioteką. JavaFX 11 jest dostępny jako pakiet SDK do pobrania lub z MavenCentral. Zobacz https://openjfx.io

Dla wszystkich nowych użytkowników, od kwietnia 2015 r., Android ma teraz klasę SortedList w bibliotece pomocy technicznej, zaprojektowaną specjalnie do pracy RecyclerView. Oto post na ten temat na blogu .

Kolejnym punktem jest złożoność czasowa operacji wstawiania. W przypadku wstawiania listy oczekuje się złożoności O (1). Nie można tego jednak zagwarantować za pomocą posortowanej listy.

Najważniejsze jest to, że listy nie zakładają niczego o swoich elementach. Na przykład możesz tworzyć listy rzeczy, które nie są implementowane equalslub compare.

Pomyśl o tym w ten sposób: Listinterfejs ma takie metody add(int index, E element),set(int index, E element) . Umowa polega na tym, że po dodaniu elementu w pozycji X znajdziesz go tam, chyba że dodasz lub usuniesz elementy przed nim.

Jeśli jakakolwiek implementacja listy przechowałaby elementy w innej kolejności niż na podstawie indeksu, powyższe metody listy nie miałyby sensu.

Pierwszy wiersz w interfejsie API List mówi, że jest to uporządkowana kolekcja (znana również jako sekwencja). Jeśli posortujesz listę, nie możesz utrzymać kolejności, więc w Javie nie ma TreeList.
Jak mówi API, lista Java została zainspirowana sekwencją i zobacz właściwości sekwencji http://en.wikipedia.org/wiki/Sequence_(mathematics )

Nie oznacza to, że nie można sortować listy, ale Java jest ściśle zgodna z jego definicją i domyślnie nie zapewnia posortowanych wersji list.

Jeśli szukasz sposobu na sortowanie elementów, ale możesz także uzyskać do nich dostęp za pomocą indeksu w efektywny sposób, możesz wykonać następujące czynności:

1. Do przechowywania użyj listy o swobodnym dostępie (np ArrayList )
2. Upewnij się, że zawsze jest posortowane

Następnie, aby dodać lub usunąć element, którego możesz użyć Collections.binarySearch aby uzyskać indeks wstawiania / usuwania. Ponieważ twoja lista implementuje losowy dostęp, możesz skutecznie modyfikować listę za pomocą określonego indeksu.

Przykład:

/**
 * @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);
    }
}

Rozważ użycie indeksowanej mapy drzewa . Jest to udoskonalony TreeSet JDK, który zapewnia dostęp do elementu według indeksu i znajdowanie indeksu elementu bez iteracji lub ukrytych bazowych list, które wykonują kopię zapasową drzewa. Algorytm opiera się na aktualizacji wag zmieniających się węzłów za każdym razem, gdy następuje zmiana.