Warum gibt es in Java keine SortedList?

Question

In Java gibt es die SortedSet y SortedMap Schnittstellen. Beide gehören zu den Java Collections-Framework und bieten einen geordneten Zugang zu den Elementen.

Nach meinem Verständnis gibt es jedoch keine SortedList in Java. Sie können verwenden java.util.Collections.sort() um eine Liste zu sortieren.

Haben Sie eine Idee, warum sie so gestaltet ist?

Answer 1

Für alle Neulinge: Seit April 2015 hat Android nun eine SortierteListe Klasse in der Support-Bibliothek, die speziell für die Arbeit mit RecyclerView . Hier ist die ブログ記事 darüber.

Answer 2

Ein weiterer Punkt ist die Zeitkomplexität von Einfügeoperationen. Bei einer Listeneinfügung erwartet man eine Komplexität von O(1). Bei einer sortierten Liste kann dies jedoch nicht garantiert werden.

Und der wichtigste Punkt ist, dass Listen nichts über ihre Elemente aussagen. Sie können zum Beispiel Listen von Dingen erstellen, die nicht equals o compare .

Answer 3

Man muss sich das so vorstellen: Die List Schnittstelle hat Methoden wie add(int index, E element) , set(int index, E element) . Der Vertrag sieht vor, dass Sie ein einmal hinzugefügtes Element an der Position X wiederfinden, wenn Sie nicht vorher Elemente hinzufügen oder entfernen.

Würde eine Listenimplementierung Elemente in einer anderen Reihenfolge als auf der Grundlage des Indexes speichern, würden die oben genannten Listenmethoden keinen Sinn ergeben.

Answer 4

Wenn Sie nach einer Möglichkeit suchen, Elemente zu sortieren, aber auch effizient nach Index auf sie zugreifen zu können, können Sie Folgendes tun:

1. Verwenden Sie eine Zufallszugriffsliste für die Speicherung (z. B. ArrayList )
2. Sorgen Sie dafür, dass sie immer sortiert ist

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

例

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

(Eine ausführlichere Implementierung finden Sie in diese Antwort )

Answer 5

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

Das bedeutet nicht, dass Sie die Liste nicht sortieren können, aber Java hält sich strikt an seine Definition und bietet standardmäßig keine sortierten Versionen von Listen an.