Gibt es eine indizierbare sortierte Liste im Java.util-Paket?

Question

Ich bin auf der Suche nach einer Datenstruktur aus dem java.util-Paket. Ich brauche es, um die folgenden Anforderungen zu erfüllen:

• Die Anzahl der Elemente ist (theoretisch) unbegrenzt.
• Die Elemente werden in aufsteigender Reihenfolge sortiert.
• Sie können das n-te Element (schnell) erhalten.
• Sie können das n-te Element (schnell) entfernen.

Ich hatte erwartet, eine indizierbare Auslassungsliste zu finden, aber das war nicht der Fall. Gibt es eine Datenstruktur, die die von mir genannten Anforderungen erfüllt?

Answer 1

In den Java-Standardbibliotheken gibt es keinen solchen Container.

Wenn ich eine Datenstruktur mit diesen Eigenschaften benötige, verwende ich eine List Implementierung (im Allgemeinen eine ArrayList aber das spielt keine Rolle), und ich führe alle Einfügungen mit Collections.binarySearch .

Wenn ich eine sortierte Liste als wiederverwendbare Klasse kapseln müsste, würde ich die List-Schnittstelle implementieren und alle Methoden an eine "Standard"-List-Implementierung delegieren (sie kann sogar als Parameter an den Konstruktor übergeben werden). Ich würde jede Einfügemethode (add, addAll, set, Iterator's remove) implementieren, indem ich eine Ausnahme werfe ( UnsupportedOperationException ), so dass niemand die Eigenschaft "immer sortiert" brechen kann. Schließlich würde ich eine Methode bereitstellen insertSorted Das würde bedeuten Collections.binarySearch um die Einfügung vorzunehmen.

Answer 2

Es gibt keine einfache Datenstruktur, die alle Ihre Kriterien erfüllt.

Die einzige, die ich kenne, die alle diese Anforderungen erfüllt, ist ein indizierbare Sprungliste . Allerdings kenne ich keine leicht verfügbaren Java-Implementierungen.

Answer 3

Diese Frage ist sehr ähnlich zu

• Sortierte Array-Liste in Java

Werfen Sie einen Blick auf meine Antwort auf diese Frage .

Sie schlägt im Wesentlichen Folgendes vor:

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

---

Eine Anmerkung zu Ihrer ersten Anforderung: " Die Anzahl der Elemente ist unbegrenzt. ":

Sie können dies einschränken auf etwas wie "Die Anzahl der Elemente sollte nicht kleiner als 2 sein. 31 -1...", da Sie sonst alle Optionen ausschließen, die durch ein Java-Array unterstützt werden. (Sie könnten mit einer beliebigen Anzahl von Elementen weg mit zum Beispiel eine LinkedList, aber ich kann nicht sehen, wie Sie schnelle Lookups in das tun könnte).

Answer 4

TreeSet bietet Ihnen die Funktionalität der natürlichen Sortierung beim Hinzufügen von Elementen zur Liste. Wenn Sie dies jedoch nicht benötigen und Collections.sort() erlaubt ist, können Sie die einfache ArrayList .

Answer 5

Erwägen Sie List kombiniert mit Collections.sort() .