Hat Java eine Skip-Listen-Implementierung?

Da Sie eine Liste erwähnt haben, die sowohl indexierbar ist (ich nehme an, Sie wollen schnellen Abruf) und Duplikate erlauben müssen, würde ich Ihnen raten, für ein benutzerdefiniertes Set mit einer LinkedList oder ArrayList vielleicht zu gehen.

Sie müssen ein Basis-Set, zum Beispiel ein Hash-Set, haben und Werte hinzufügen. Wenn Sie einem Duplikat gegenüberstehen, sollte der Wert dieses Sets auf eine Liste verweisen. So, dass Sie sowohl Speedy Retrieval haben und natürlich werden Sie Ihre Objekte in einer Art pseudo Collection speichern.

Dies sollte Ihnen eine gute Effizienz beim Abruf geben. Im Idealfall, wenn Ihre Schlüssel keine Duplikate sind, erhalten Sie ein O (1) als Abrufgeschwindigkeit.

Diese Antwort ist 3 Jahre zu spät, aber ich hoffe, dass es für diejenigen, die ab diesem Moment eine Java-Skip-Liste wünschen, nützlich sein wird:)

Diese Lösung erlaubt Duplikate wie Sie gefragt haben. Ich folge grob dem Leitfaden hier Ссылка , also sind die Komplexitäten ähnlich, außer delete kostet O (nlogn) - da ich mich nicht darum gekümmert habe, doppelt verknüpfte Knoten zu verwenden, würde ich mir vorstellen, dies zu tun, würde delete auf O (logn) herunterbringen.

Code besteht aus: einer Schnittstelle, der Überspringungsliste, die die Schnittstelle implementiert, und der Knotenklasse. Es ist auch generisch.

Sie können den Parameter LEVELS für die Leistung optimieren, aber denken Sie an den Raum-Zeit-Kompromiss.

Sie können das folgende Code verwenden, um Ihre eigene Basis-Ausnahmeliste zu erstellen:

1) Machen Sie start und end auf represent start and end of skip list .

2) Add the nodes und assign pointers bis nächste based on

Java-Code für die Basis-Überspringungsliste (Sie können weitere Funktionen hinzufügen, wenn Sie möchten):

Ausgabe:

- Einfaches Traversal -

1 = & gt; 2 = & gt; 3 = & gt; 4 = & gt; 5 = & gt; 6 = & gt;

- Fast Lane Traversal -

2 == & gt; 4 == & gt; 6 == & gt;

Ich stimme der Verwendung von TreeList aus apache-collections zu und dekoriere sie mit SortedList von Happy Java Libraries Ссылка

Ich behaupte nicht, dass dies meine eigene Implementierung ist. Ich kann mich nicht erinnern, wo ich es gefunden habe. Wenn Sie wissen, lassen Sie mich wissen, und ich werde aktualisieren. Das hat sehr gut für mich funktioniert:

Der Fehler in der von @PoweredByRice bereitgestellten Implementierung wurde behoben. Es warf eine NPE für Fälle, in denen der gelöschte Knoten der erste Knoten war. Andere Aktualisierungen umfassen umbenannte Variablennamen und umgekehrtes Drucken der Reihenfolge der Überspringungsliste.