In Java gibt es die SortedSetund SortedMapSchnittstellen. Beide gehören zum Java Collections-Framework und bieten eine sortierte Möglichkeit, auf die Elemente zuzugreifen.

Nach meinem Verständnis gibt es jedoch kein SortedListJava. Sie können java.util.Collections.sort()eine Liste sortieren.

Irgendeine Idee, warum es so gestaltet ist?

Listeniteratoren garantieren in erster Linie, dass Sie die Elemente der Liste in der internen Reihenfolge der Liste (auch bekannt als Einfügereihenfolge ) erhalten. Genauer gesagt in der Reihenfolge, in der Sie die Elemente eingefügt haben oder wie Sie die Liste bearbeitet haben. Das Sortieren kann als Manipulation der Datenstruktur angesehen werden, und es gibt verschiedene Möglichkeiten, die Liste zu sortieren.

Ich werde die Wege in der Reihenfolge ihrer Nützlichkeit ordnen, wie ich es persönlich sehe:

1. Erwägen Sie stattdessen die Verwendung von Setoder BagSammlungen

HINWEIS: Ich habe diese Option oben platziert, da Sie dies normalerweise sowieso tun möchten.

Ein sortierter Satz sortiert die Sammlung beim Einfügen automatisch. Dies bedeutet, dass die Sortierung durchgeführt wird, während Sie der Sammlung Elemente hinzufügen. Dies bedeutet auch, dass Sie es nicht manuell sortieren müssen.

Wenn Sie sicher sind, dass Sie sich keine Gedanken über doppelte Elemente machen müssen (oder haben), können Sie TreeSet<T>stattdessen das verwenden. Es implementiert SortedSetund NavigableSetverbindet und funktioniert so, wie Sie es wahrscheinlich von einer Liste erwarten würden:

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"

Wenn Sie die natürliche Reihenfolge nicht möchten, können Sie den Konstruktorparameter verwenden, der a akzeptiert Comparator<T>.

Alternativ Sie können Multimengen (auch bekannt als Beutel ) , das ist eine , Setdie doppelten Elemente erlaubt es , statt und es gibt Drittanbieter - Implementierungen von ihnen. Vor allem aus den Guava-Bibliotheken gibt es eine TreeMultiset, die sehr ähnlich funktioniert wie die TreeSet.

2. Sortieren Sie Ihre Liste mit Collections.sort()

Wie oben erwähnt, ist das Sortieren von Lists eine Manipulation der Datenstruktur. In Situationen, in denen Sie "eine Quelle der Wahrheit" benötigen, die auf verschiedene Arten sortiert wird, ist das manuelle Sortieren der richtige Weg.

Sie können Ihre Liste mit der java.util.Collections.sort()Methode sortieren . Hier ist ein Codebeispiel, wie:

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"

Komparatoren verwenden

Ein klarer Vorteil ist, dass Sie Comparatorin der sortMethode verwenden können. Java bietet auch einige Implementierungen für Comparatorsolche, wie z. B. die, Collatordie für länderspezifische Sortierzeichenfolgen nützlich sind. Hier ist ein Beispiel:

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

Collections.sort(strings, usCollator);

Sortieren in gleichzeitigen Umgebungen

Beachten Sie jedoch, dass die Verwendung der sortMethode in gleichzeitigen Umgebungen nicht benutzerfreundlich ist, da die Sammlungsinstanz manipuliert wird und Sie stattdessen die Verwendung unveränderlicher Sammlungen in Betracht ziehen sollten. Dies ist etwas, was Guava in der OrderingKlasse bietet und ist ein einfacher Einzeiler:

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

3. Wickeln Sie Ihre Liste mit ein java.util.PriorityQueue

Obwohl es in Java keine sortierte Liste gibt, gibt es eine sortierte Warteschlange, die wahrscheinlich genauso gut für Sie funktionieren würde. Es ist die java.util.PriorityQueueKlasse.

Nico Haase hat in den Kommentaren eine verwandte Frage verlinkt , die auch diese beantwortet.

In einer sortierten Sammlung möchten Sie höchstwahrscheinlich die interne Datenstruktur nicht manipulieren, weshalb PriorityQueue die List-Schnittstelle nicht implementiert (da Sie dadurch direkten Zugriff auf ihre Elemente erhalten).

Vorsichtsmaßnahme für den PriorityQueueIterator

Die PriorityQueueKlasse implementiert die Schnittstellen Iterable<E>und Collection<E>, sodass sie wie gewohnt iteriert werden kann. Es ist jedoch nicht garantiert, dass der Iterator Elemente in der sortierten Reihenfolge zurückgibt. Stattdessen müssen Sie (wie Alderath in den Kommentaren hervorhebt) in poll()die Warteschlange gestellt werden, bis sie leer ist.

Beachten Sie, dass Sie eine Liste über den Konstruktor, der eine beliebige Sammlung akzeptiert, in eine Prioritätswarteschlange konvertieren können :

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. Schreiben Sie Ihre eigene SortedListKlasse

HINWEIS: Sie sollten dies nicht tun müssen.

Sie können Ihre eigene List-Klasse schreiben, die jedes Mal sortiert wird, wenn Sie ein neues Element hinzufügen. Dies kann abhängig von Ihrer Implementierung ziemlich rechenintensiv werden und ist aus zwei Hauptgründen sinnlos , es sei denn, Sie möchten es als Übung ausführen:

1. Es bricht den Vertrag, den die List<E>Schnittstelle hat, weil die addMethoden sicherstellen sollten, dass sich das Element in dem vom Benutzer angegebenen Index befindet.
2. Warum das Rad neu erfinden? Sie sollten stattdessen das TreeSet oder Multisets verwenden, wie im ersten Punkt oben ausgeführt.

Wenn Sie dies jedoch als Übung ausführen möchten, verwenden Sie hier ein Codebeispiel, um den Einstieg zu erleichtern. Es wird die AbstractListabstrakte Klasse verwendet:

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

}

Beachten Sie , wenn Sie die Methoden nicht außer Kraft gesetzt haben , Sie benötigen, dann von dem Standardimplementierungen AbstractListwerfen UnsupportedOperationExceptions.

Weil das Konzept einer Liste nicht mit dem Konzept einer automatisch sortierten Sammlung kompatibel ist. Der Punkt einer Liste ist, dass nach dem Aufruf list.add(7, elem)ein Anruf an zurückgegeben list.get(7)wird elem. Bei einer automatisch sortierten Liste könnte das Element an einer beliebigen Position landen.

Da alle Listen bereits nach der Reihenfolge "sortiert" sind, in der die Elemente hinzugefügt wurden (FIFO-Reihenfolge), können Sie sie mit einer anderen Reihenfolge "neu sortieren", einschließlich der natürlichen Reihenfolge der Elemente java.util.Collections.sort().

BEARBEITEN:

Listen als Datenstrukturen basieren auf der Reihenfolge, in der die Elemente eingefügt wurden.

Sets haben diese Informationen nicht.

Wenn Sie durch Hinzufügen von Zeit bestellen möchten, verwenden Sie List. Wenn Sie nach anderen Kriterien bestellen möchten, verwenden Sie SortedSet.

Set und Map sind nichtlineare Datenstrukturen. Liste ist lineare Datenstruktur.

Die Baumdatenstruktur SortedSetund SortedMapSchnittstellen implementiert TreeSetund TreeMapjeweils verwendete Verwendung Rot-Schwarz - Baum Implementierung Algorithmus. So wird sichergestellt, dass keine doppelten Elemente (oder Schlüssel im Fall von Map) vorhanden sind.

• List Wird bereits eine geordnete Sammlung und indexbasierte Datenstruktur gepflegt, sind Bäume keine indexbasierten Datenstrukturen.
• Tree per definitionem dürfen keine Duplikate enthalten sein.
• In können Listwir Duplikate haben, also gibt es keine TreeList(dh keine SortedList).
• Liste verwaltet Elemente in Einfügereihenfolge. Wenn wir also die Liste sortieren wollen, müssen wir sie verwenden java.util.Collections.sort(). Es sortiert die angegebene Liste in aufsteigender Reihenfolge entsprechend der natürlichen Reihenfolge ihrer Elemente.

JavaFX SortedList

Obwohl es eine Weile gedauert hat, hat Java 8 eine sortierte List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Wie Sie in den Javadocs sehen können, ist es Teil der JavaFX- Sammlungen, die eine sortierte Ansicht einer ObservableList bereitstellen sollen.

Update: Beachten Sie, dass mit Java 11 das JavaFX-Toolkit außerhalb des JDK verschoben wurde und jetzt eine separate Bibliothek ist. JavaFX 11 ist als herunterladbares SDK oder bei MavenCentral erhältlich. Siehe https://openjfx.io

Für alle Neulinge hat Android ab April 2015 eine SortedList- Klasse in der Support-Bibliothek, die speziell für die Arbeit mit entwickelt wurde RecyclerView. Hier ist der Blog-Beitrag darüber.

Ein weiterer Punkt ist die zeitliche Komplexität von Einfügeoperationen. Für eine Listeneinfügung erwartet man eine Komplexität von O (1). Dies konnte jedoch mit einer sortierten Liste nicht garantiert werden.

Und der wichtigste Punkt ist, dass Listen nichts über ihre Elemente annehmen. Sie können beispielsweise Listen mit Dingen erstellen, die nicht implementiert sind equalsoder compare.

Stellen Sie sich das so vor: Die ListSchnittstelle verfügt über Methoden wie add(int index, E element), set(int index, E element). Der Vertrag sieht vor, dass Sie ein Element an Position X dort finden, wenn Sie es hinzugefügt haben, es sei denn, Sie fügen zuvor Elemente hinzu oder entfernen sie.

Wenn eine Listenimplementierung Elemente in einer anderen Reihenfolge als basierend auf dem Index speichern würde, wären die obigen Listenmethoden nicht sinnvoll.

Die erste Zeile in der Listen-API besagt, dass es sich um eine geordnete Sammlung handelt (auch als Sequenz bezeichnet). Wenn Sie die Liste sortieren, können Sie die Reihenfolge nicht beibehalten, sodass in Java keine Baumliste vorhanden ist.
Wie API sagt, wurde Java List von Sequence inspiriert und siehe die Sequenzeigenschaften http://en.wikipedia.org/wiki/Sequence_(mathematics )

Dies bedeutet nicht, dass Sie die Liste nicht sortieren können, aber Java entspricht seiner Definition und bietet standardmäßig keine sortierten Versionen von Listen.

Wenn Sie nach einer Möglichkeit suchen, Elemente zu sortieren, aber auch effizient über einen Index darauf zugreifen können, haben Sie folgende Möglichkeiten:

1. Verwenden Sie einen Direktzugriffsliste für die Lagerung (zB ArrayList)
2. Stellen Sie sicher, dass es immer sortiert ist

Um dann ein Element hinzuzufügen oder zu entfernen, können Collections.binarySearchSie den Einfüge- / Entfernungsindex abrufen. Da Ihre Liste einen Direktzugriff implementiert, können Sie die Liste mit dem ermittelten Index effizient ändern.

Beispiel:

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

Erwägen Sie die Verwendung einer indizierten Baumkarte . Es handelt sich um ein erweitertes JDK-TreeSet, das den Zugriff auf Elemente über den Index ermöglicht und den Index eines Elements ohne Iteration oder versteckte zugrunde liegende Listen findet, die den Baum sichern. Der Algorithmus basiert auf der Aktualisierung der Gewichte sich ändernder Knoten bei jeder Änderung.