Liste Java überspringen

Skip List Java ist eine Datenstruktur, die zum Speichern einer sortierten Liste von Elementen mithilfe einer verknüpften Listenhierarchie verwendet wird, die eine Verbindung zu Teilsequenzen von Elementen herstellt. Mit der Skip-Liste können Sie die Elementsuche auf effiziente Weise verarbeiten. Die Überspringliste ist eine probabilistische Datenstruktur, das heißt, sie überspringt mehrere Elemente in der gesamten Liste und wird daher als Überspringliste bezeichnet. Wir können die Sprungliste als erweiterte Version einer verknüpften Liste betrachten. Ähnlich wie die verknüpfte Liste das Einfügen, Entfernen und Durchführen einer Suche nach Elementen ermöglicht, ermöglicht die Liste „Überspringen“ auch das Suchen nach Elementen, das Entfernen von Elementen aus der Liste und das Einfügen von Elementen. Es enthält eine Basisliste, die eine Reihe von Elementen enthält, die die Linkhierarchie nachfolgender Elemente beibehalten würden.

WERBUNG Beliebter Kurs in dieser Kategorie JAVA MASTERY - Spezialisierung | 78 Kursreihe | 15 Probetests

Starten Sie Ihren kostenlosen Softwareentwicklungskurs

Webentwicklung, Programmiersprachen, Softwaretests und andere

Syntax:

Skip List hat keine bestimmte Syntax, aber einen Algorithmus. Bevor wir uns den Algorithmus ansehen, müssen wir die Arten grundlegender Skip-List-Operationen überprüfen.

• Einfügevorgang:In der Skip-Liste wird es verwendet, um einen neuen Knoten an einem bestimmten Ort in einer bestimmten Situation hinzuzufügen
• Suchvorgang: In der Überspringliste wird es verwendet, um einen bestimmten Knoten zu durchsuchen
• Löschvorgang:In der Überspringliste wird es verwendet, um einen Knoten in einer bestimmten Situation zu löschen

Funktionsweise der Skip-Liste in Java

Sehen wir uns also an, wie die Skip-Liste auf algorithmische Weise tatsächlich funktioniert.

Einfügungsalgorithmus

Schritt 1: Festlegung der Knotenebenen, da jedes Element in der Liste durch einen Knoten dargestellt wird und die Ebene eines Knotens zum Zeitpunkt des Einfügens in die Liste zufällig ausgewählt wird

Schritt 2: Die Ebene für einen Knoten wird anhand der folgenden Schritte festgelegt

Schritt 3: Finden Sie die maximale Ebene als Obergrenze für die Anzahl der Ebenen in der Sprungliste, die durch L(N) = logp/2N bestimmt wird. Dadurch wird sichergestellt, dass das zufällige Level größer als das maximale Level ist

Schritt 4: Das Einfügen beginnt auf der höchsten Ebene und vergleicht den nächsten Knoten mit dem aktuellen Knoten

Schritt 5:Wenn der Schlüssel für den nächsten Knoten kleiner als der eingefügte Schlüssel ist, können wir mit derselben Ebene fortfahren

Schritt 6: Wenn der Schlüssel des nächsten Knotens größer als der eingefügte Schlüssel ist, müssen wir einen Zeiger auf den aktuellen Knoten I speichern und eine Ebene nach unten verschieben, um die Suche fortzusetzen.

Suchalgorithmus

Schritt 1: Da das Suchelement der Suche nach einer Stelle zum Einfügen eines Elements in die Überspringliste sehr ähnlich ist.

Schritt 2:Wenn der nächste Knotenschlüssel kleiner als der Suchschlüssel ist, können wir auf derselben Ebene vorwärts gehen

Schritt 3: Wenn der Schlüssel des nächsten Knotens größer als der eingefügte Schlüssel ist, müssen wir einen Zeiger auf den aktuellen Knoten I speichern und eine Ebene nach unten verschieben, um die Suche fortzusetzen.

Schritt 4: Wenn auf der untersten Ebene das nächste Element ganz rechts Schlüssel hat, die dem Suchschlüssel entsprechen, dann haben wir den Schlüssel gefunden, andernfalls handelt es sich um einen Fehler.

Löschalgorithmus

Schritt 1:Um ein Element, sagen wir k, zu löschen, müssen wir zuerst das Element in der Skip-Liste mithilfe des Suchalgorithmus suchen.

Schritt 2: Sobald wir das Element mithilfe des Suchalgorithmus gefunden haben, wird eine Neuanordnung des Zeigers durchgeführt, um das Element aus der Liste zu entfernen, wie wir es in einer einfach verknüpften Liste tun.

Schritt 3:Wir müssen auf der untersten Ebene der Überspringliste beginnen und die Elemente neben I, nicht Element k, neu anordnen.

Schritt 4: Nach dem Löschen eines Elements kann es vorkommen, dass Ebenen ohne Elemente vorhanden sind. Daher müssen wir diese Ebenen entfernen, indem wir die Ebene der Überspringliste verringern.

Beispiel einer Sprungliste in Java

Code:

import java.util.Iterator;
import java.util.Random;
import java.util.NoSuchElementException;
public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {
private int listsize;
private double pb;
protected static final Random randomGen = new Random();
protected static final double DEFAULT_PB = 0.5;
private NodeKeyValue<K, V> head;
public SkipListJava() {
this(DEFAULT_PB);
}
public SkipListJava(double pb) {
this.head = new NodeKeyValue<K, V>(null, null, 0);
this.pb = pb;
this.listsize = 0;
}
public V get(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey().compareTo(key) == 0)
return listnode.getValue();
else
return null;
}
public void add(K key, V value) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {
listnode.setValue(value);
return;
}
NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, newlistNode);
int curLevel = listnode.getLevel();
int headlistLevel = head.getLevel();
while (isBuildLevel()) {
if (curLevel >= headlistLevel) {
NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);
verticalLink(newHeadEle, head);
head = newHeadEle;
headlistLevel = head.getLevel();
}
while (listnode.getUp() == null) {
listnode = listnode.getPrevious();
}
listnode = listnode.getUp();
NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());
horizontalInsertList(listnode, tmp);
verticalLink(tmp, newlistNode);
newlistNode = tmp;
curLevel++;
}
listsize++;
}
public void remove(K key) {
checkKeyValid(key);
NodeKeyValue<K, V> listnode = findNode(key);
if (listnode == null || listnode.getKey().compareTo(key) != 0)
throw new NoSuchElementException("Key does not exist!");
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
NodeKeyValue<K, V> previous = null;
NodeKeyValue<K, V> next = null;
for (; listnode != null; listnode = listnode.getUp()) {
previous = listnode.getPrevious();
next = listnode.getNext();
if (previous != null)
previous.setNext(next);
if (next != null)
next.setPreviousVal(previous);
}
while (head.getNext() == null && head.getDownList() != null) {
head = head.getDownList();
head.setUp(null);
}
listsize--;
}
public boolean contains(K key) {
return get(key) != null;
}
public int listsize() {
return listsize;
}
public boolean empty() {
return listsize == 0;
}
protected NodeKeyValue<K, V> findNode(K key) {
NodeKeyValue<K, V> listnode = head;
NodeKeyValue<K, V> next = null;
NodeKeyValue<K, V> down = null;
K nodeKey = null;
while (true) {
next = listnode.getNext();
while (next != null && lessThanEqual(next.getKey(), key)) {
listnode = next;
next = listnode.getNext();
}
nodeKey = listnode.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
down = listnode.getDownList();
if (down != null) {
listnode = down;
} else {
break;
}
}
return listnode;
}
protected void checkKeyValid(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
protected boolean lessThanEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
protected boolean isBuildLevel() {
return randomGen.nextDouble() < pb;
}
protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
b.setPreviousVal(a);
b.setNext(a.getNext());
if (a.getNext() != null)
a.getNext().setPreviousVal(b);
a.setNext(b);
}
protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {
a.setDown(b);
b.setUp(a);
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
NodeKeyValue<K, V> listnode = head;
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
while (listnode != null) {
stringbuild.append(listnode.toString()).append("\n");
listnode = listnode.getNext();
}
return stringbuild.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private NodeKeyValue<K, V> listnode;
public SkipListIterator(NodeKeyValue<K, V> listnode) {
while (listnode.getDownList() != null)
listnode = listnode.getDownList();
while (listnode.getPrevious() != null)
listnode = listnode.getPrevious();
if (listnode.getNext() != null)
listnode = listnode.getNext();
this.listnode = listnode;
}
@Override
public boolean hasNext() {
return this.listnode != null;
}
@Override
public K next() {
K result = listnode.getKey();
listnode = listnode.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
protected static class NodeKeyValue<K extends Comparable<K>, V> {
private K key;
private V value;
private int skiplevel;
private NodeKeyValue<K, V> up, down, next, previous;
public NodeKeyValue(K key, V value, int skiplevel) {
this.key = key;
this.value = value;
this.skiplevel = skiplevel;
}
@Override
public String toString() {
StringBuilder stringbuild = new StringBuilder();
stringbuild.append("Node[")
.append("key:");
if (this.key == null)
stringbuild.append("None");
else
stringbuild.append(this.key.toString());
stringbuild.append(", value:");
if (this.value == null)
stringbuild.append("None");
else
stringbuild.append(this.value.toString());
stringbuild.append("]");
return stringbuild.toString();
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int getLevel() {
return skiplevel;
}
public void setLevel(int skiplevel) {
this.skiplevel = skiplevel;
}
public NodeKeyValue<K, V> getUp() {
return up;
}
public void setUp(NodeKeyValue<K, V> up) {
this.up = up;
}
public NodeKeyValue<K, V> getDownList() {
return down;
}
public void setDown(NodeKeyValue<K, V> down) {
this.down = down;
}
public NodeKeyValue<K, V> getNext() {
return next;
}
public void setNext(NodeKeyValue<K, V> next) {
this.next = next;
}
public NodeKeyValue<K, V> getPrevious() {
return previous;
}
public void setPreviousVal(NodeKeyValue<K, V> previous) {
this.previous = previous;
}
}
public static void main(String[] args) {
SkipListJava<Integer, String> skip = new SkipListJava<>();
for (int i = 20; i < 35; i++) {
skip.add(i, String.valueOf(i));
}
System.out.println(skip);
assert skip.listsize() == 10;
int count = 0;
for (Integer i : skip)
assert i.equals(count++);
skip.remove(23);
System.out.println(skip);
skip.remove(25);
skip.remove(33);
skip.remove(30);
System.out.println(skip);
skip.remove(28);
skip.add(25, "25");
System.out.println(skip);
assert skip.listsize() == 0;
assert skip.empty();
}
}

Ausgabe:

Wir haben diesen Code zum Hinzufügen zur Überspringliste, zum Suchen in der Überspringliste und zum Entfernen aus der Überspringliste geschrieben.

Fazit

Damit schließen wir dieses Thema „Java überspringen“ ab. Wir haben gesehen, was Skip-List-Java ist und wie es mit dem Algorithmus zum Suchen, Einfügen und Löschen/Entfernen von Elementen aus der Skip-Liste funktioniert. Außerdem haben Sie ein gutes Beispiel, das alle Vorgänge der Skip-Liste auf einmal enthält. Sie können es auch mit ganz anderen Beispielen oder Logiken versuchen, die Ihnen in den Sinn kommen. Das Konzept der Sprungliste ist in jeder Programmiersprache das gleiche, einer der wichtigsten Algorithmen in der Datenstruktur.

Das obige ist der detaillierte Inhalt vonListe Java überspringen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!