Was ist eine Skip-Liste?

Eine Sprungliste ist eine probabilistische Datenstruktur. Die Sprungliste wird zum Speichern einer sortierten Liste von Elementen oder Daten mit einer verknüpften Liste verwendet. Es ermöglicht eine effiziente Anzeige des Prozesses der Elemente oder Daten. In einem einzigen Schritt werden mehrere Elemente der gesamten Liste übersprungen, weshalb sie als Überspringliste bezeichnet wird.

Die Sprungliste ist eine erweiterte Version der verknüpften Liste. Es ermöglicht dem Benutzer, das Element sehr schnell zu suchen, zu entfernen und einzufügen. Sie besteht aus einer Basisliste, die eine Reihe von Elementen enthält, die die Linkhierarchie der nachfolgenden Elemente aufrechterhält.

Listenstruktur überspringen

Es besteht aus zwei Schichten: der untersten Schicht und der obersten Schicht.

Die unterste Ebene der Sprungliste ist eine allgemein sortierte verknüpfte Liste, und die obersten Ebenen der Sprungliste ähneln einer „Expresslinie“, in der die Elemente übersprungen werden.

Komplexitätstabelle der Skip-Liste

Funktionsweise der Skip-Liste

Nehmen wir ein Beispiel, um die Funktionsweise der Sprungliste zu verstehen. In diesem Beispiel haben wir 14 Knoten, sodass diese Knoten in zwei Schichten unterteilt sind, wie im Diagramm gezeigt.

Die untere Ebene ist eine gemeinsame Linie, die alle Knoten verbindet, und die obere Ebene ist eine Expresslinie, die nur die Hauptknoten verbindet, wie Sie im Diagramm sehen können.

Angenommen, Sie möchten in diesem Beispiel 47 finden. Sie beginnen die Suche am ersten Knoten der Express-Linie und setzen die Suche auf der Express-Linie fort, bis Sie einen Knoten finden, der gleich 47 oder größer als 47 ist.

Sie können im Beispiel sehen, dass 47 in der Express-Zeile nicht existiert, also suchen Sie nach einem Knoten mit weniger als 47, also 40. Nun gehen Sie mit Hilfe von 40 zur normalen Zeile und suchen nach 47. wie im Diagramm dargestellt.

Hinweis: Sobald Sie einen solchen Knoten auf der „Expresslinie“ gefunden haben, wechseln Sie von diesem Knoten aus mit einem Zeiger zu einer „normalen Spur“ und suchen den Knoten auf der normalen Linie.

Grundlegende Vorgänge der Liste überspringen

In der Überspringliste gibt es die folgenden Arten von Vorgängen.

Einfügevorgang:Es wird verwendet, um in einer bestimmten Situation einen neuen Knoten an einem bestimmten Standort hinzuzufügen.Löschvorgang:Es wird verwendet, um einen Knoten in einer bestimmten Situation zu löschen.Suchvorgang:Mit der Suchoperation wird ein bestimmter Knoten in einer Sprungliste durchsucht.

Algorithmus der Einfügeoperation

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Algorithmus des Löschvorgangs

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Algorithmus der Suchoperation

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

Beispiel 1: Erstellen Sie eine Skip-Liste. Wir möchten die folgenden Schlüssel in die leere Skip-Liste einfügen.

1. 6 mit Stufe 1.
2. 29 mit Level 1.
3. 22 mit Level 4.
4. 9 mit Level 3.
5. 17 mit Level 1.
6. 4 mit Level 2.

Jahre:

Schritt 1: 6 mit Stufe 1 einfügen

Schritt 2: 29 mit Stufe 1 einfügen

Schritt 3: 22 mit Stufe 4 einfügen

Schritt 4: Fügen Sie 9 mit Ebene 3 ein

Schritt 5: 17 mit Stufe 1 einfügen

Schritt 6: 4 mit Stufe 2 einfügen

Beispiel 2: Betrachten Sie dieses Beispiel, in dem wir nach Schlüssel 17 suchen möchten.

Jahre:

Vorteile der Skip-Liste

1. Wenn Sie einen neuen Knoten in die Überspringliste einfügen möchten, wird der Knoten sehr schnell eingefügt, da es in der Überspringliste keine Rotationen gibt.
2. Die Sprungliste ist im Vergleich zur Hash-Tabelle und dem binären Suchbaum einfach zu implementieren.
3. Es ist sehr einfach, einen Knoten in der Liste zu finden, da die Knoten in sortierter Form gespeichert werden.
4. Der Skip-List-Algorithmus kann sehr einfach in eine spezifischere Struktur geändert werden, z. B. indizierte Skip-Listen, Bäume oder Prioritätswarteschlangen.
5. Die Sprungliste ist eine robuste und zuverlässige Liste.

Nachteile der Skip-Liste

1. Es benötigt mehr Speicher als der ausgeglichene Baum.
2. Eine Rückwärtssuche ist nicht zulässig.
3. Die Sprungliste durchsucht den Knoten viel langsamer als die verknüpfte Liste.

Anwendungen der Skip-Liste

1. Es wird in verteilten Anwendungen verwendet und stellt die Zeiger und das System in den verteilten Anwendungen dar.
2. Es wird verwendet, um eine dynamische elastische gleichzeitige Warteschlange mit geringem Sperrkonflikt zu implementieren.
3. Es wird auch mit der QMap-Vorlagenklasse verwendet.
4. Die Indizierung der Sprungliste wird bei der Ausführung von Medianproblemen verwendet.
5. Die Skip-Liste wird für die Delta-Verschlüsselungsbuchung in der Lucene-Suche verwendet.