Skip List Java est une structure de données utilisée pour stocker une liste triée d'éléments à l'aide d'une hiérarchie de listes chaînées qui se connecte à des sous-séquences d'éléments. Skip List permet de traiter la recherche d'éléments de manière efficace. La liste à ignorer est une structure de données probabiliste, ce qui signifie qu'elle ignore plusieurs éléments de la liste entière et est donc connue sous le nom de liste à ignorer. Nous pouvons considérer la liste de sauts comme une version étendue d'une liste chaînée. De la même manière que la liste chaînée permet l'insertion, la suppression et la recherche d'éléments, la liste Ignorer permet également de rechercher des éléments, de supprimer des éléments de la liste et d'insérer des éléments. Il contiendra une liste de base qui comprend un ensemble d'éléments qui maintiendraient la hiérarchie des liens des éléments suivants.
PUBLICITÉ
Cours populaire dans cette catégorie
MAÎTRISÉE JAVA - Spécialisation | 78 séries de cours | 15 tests simulés
Commencez votre cours de développement de logiciels libres
Développement Web, langages de programmation, tests de logiciels et autres
Syntaxe :
Skip List n'a pas de syntaxe particulière, mais elle a un algorithme. Avant d'examiner l'algorithme, nous devons vérifier les types d'opérations de base de liste de sauts.
-
Opération d'insertion : Dans la liste Skip, elle est utilisée pour ajouter un nouveau nœud à un emplacement particulier dans une situation spécifique
-
Opération de recherche : Dans la liste Skip, elle est utilisée pour rechercher un nœud particulier
-
Opération de suppression : Dans la liste Skip, elle est utilisée pour supprimer un nœud dans une situation spécifique
Fonctionnement de la liste de sauts en Java
Voyons donc comment Skip List fonctionne réellement de manière algorithmique.
Algorithme d'insertion
Étape 1 : Décider des niveaux de nœuds car chaque élément de la liste est représenté par nœud et le niveau d'un nœud est choisi aléatoirement au moment de l'insertion dans la liste
Étape 2 : Le niveau d'un nœud est décidé en fonction des étapes ci-dessous
Étape 3 : Recherchez le niveau maximum comme étant la limite supérieure du nombre de niveaux dans la liste à sauter, qui est déterminée par L(N) = logp/2N. Cela garantit que le niveau aléatoire sera supérieur au niveau maximum
Étape 4 : L'insertion commence par le niveau le plus élevé et compare le nœud suivant du nœud actuel
Étape 5 : Si la clé du nœud suivant est inférieure à la clé insérée, alors nous pouvons avancer avec le même niveau
Étape 6 : Si la clé du nœud suivant est supérieure à la clé insérée, nous devons alors stocker un pointeur vers le nœud actuel I et descendre d'un niveau en poursuivant la recherche.
Algorithme de recherche
Étape 1 : Comme l'élément de recherche est très similaire à la recherche d'un endroit pour insérer un élément dans la liste Skip.
Étape 2 : Si la clé du nœud suivant est inférieure à la clé de recherche, alors nous pouvons avancer au même niveau
Étape 3 : Si la clé du nœud suivant est supérieure à la clé insérée, nous devons alors stocker un pointeur vers le nœud actuel I et descendre d'un niveau en poursuivant la recherche.
Étape 4 : Au niveau le plus bas, si l'élément suivant à l'extrême droite a des clés égales à la clé de recherche, alors nous avons trouvé la clé sinon c'est un échec.
Algorithme de suppression
Étape 1 : Pour supprimer un élément, disons k, nous devons d'abord localiser l'élément dans la liste Ignorer à l'aide de l'algorithme de recherche.
Étape 2 : Une fois que nous avons trouvé l'élément à l'aide de l'algorithme de recherche, le réarrangement du pointeur est effectué pour supprimer l'élément de la liste comme nous le faisons dans une liste chaînée unique.
Étape 3 : Nous devons commencer par le niveau le plus bas de la liste de sauts et réorganiser les éléments à côté de I et non de l'élément k.
Étape 4 : Après la suppression d'un élément, il peut y avoir une situation où des niveaux sans éléments, nous devons donc supprimer ces niveaux en décrémentant le niveau de la liste de sauts.
Exemple de liste de sauts en 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();
}
}Copier après la connexion
Sortie :
Nous avons écrit ce code pour l'ajouter à la liste à ignorer, la recherche dans la liste à ignorer et la suppression de la liste à ignorer.
Conclusion
Avec cela, nous conclurons ce sujet « Skip List Java ». Nous avons vu ce qu'est Java Skip List et comment il fonctionne avec l'algorithme de recherche, d'insertion et de suppression/suppression d'un élément de la liste Skip. Ayez également un bon exemple qui présente toutes les opérations de la liste de sauts en une seule fois. Vous pouvez toujours essayer avec d'autres exemples ou logiques que vous pourriez avoir en tête. Le concept de liste de sauts est le même dans n'importe quel langage de programmation, l'un des principaux algorithmes de structure de données.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
