Écrivez une liste de sauts

    class Skiplist {
        // 1.Définir les noeuds dans la table Hop
        class Node{
            // Valeur
            int val;
            // Noeud droit et noeud inférieur du noeud
            Node right, down;
            public Node(int val, Node right, Node down){
                this.val = val;
                this.right = right;
                this.down =  down;
            }
            public Node(int val){
                this(val, null, null);
            }
        }
        //2. Définir les attributs liés à la table Hop
        // Définir les valeurs par défaut du noeud d'en - tête
        final int DEFAULT_VALUE = -1;
        // Définir le noeud d'en - tête par défaut
        final Node HEAD =  new Node(DEFAULT_VALUE);
        // Niveau correspondant à la table de saut
        int levels;
        // Nombre de noeuds dans la liste de liens originale dans la table de saut
        int length;
        Node head;
        // 3.Initialisation,Le niveau par défaut est1,La longueur est1,, Noeud d'en - tête par défaut
        public Skiplist() {
            this.levels = 1;
            this.length = 1;
            this.head = HEAD;
        }
        // 4.  Définir le noeud précédent qui obtient le noeud correspondant à la valeur de la cible de recherche à partir d'un noeud ( Parce qu'il n'y a pas d'attribut entre les noeuds qui se réfère au noeud avant , Et le noeud dans la table de saut d'opération 
        //  Il est nécessaire de commencer par le noeud précédent du noeud cible ,  Donc nous prenons le noeud avant du noeud cible )
        private Node get(int num, Node from){
            // 1. À partir de quel noeud commencer la recherche 
            Node node = from;
            // 2. La logique de la boucle est d'abord de gauche à droite , Et ensuite chercher de haut en bas 
            while(node!=null){
                // 2.1  Si le noeud droit du noeud courant n'est pas vide et que la valeur du noeud droit est inférieure à la valeur cible , Continuez à chercher à droite. 
                while(node.right!=null && node.right.val<num){
                    node = node.right;
                }
                // 2.2  Sortir de la boucle lorsque le noeud droit n'est pas vide , Alors seulement si la valeur du noeud droit est supérieure ou égale à la valeur cible 
                // Si égal à, Alors on a trouvé , Renvoie directement le noeud avant du noeud cible 
                Node right =  node.right;
                if(right!=null && right.val == num){
                    return node;
                }
                // 2.3 Si ce n'est pas l'égalité , Alors continuez à chercher vers le bas 
                node = node.down;
            }
            return null;
        }
        // 5.Demande s'il existe
        public boolean search(int target) {
            //  Appelez directement la méthode de requête ci - dessus , Commencez par l'en - tête ,Si le retour n'est pas vide,Représentant trouvé
            Node node = get(target, head);
            return node != null;
        }
        // 6.Insérer un noeud, L'idée générale est de trouver l'emplacement du noeud d'insertion dans la liste de liens d'origine et de l'insérer ,
        //  Ensuite, en lançant des pièces, vous décidez si vous voulez construire un noeud d'index 
        public void add(int num) {
            // 6.1  Définissez le noeud avant que le tableau temporaire soit utilisé pour stocker le noeud inséré à l'endroit où chaque couche doit être insérée 
            Node[] nodes = new Node[this.levels];
            // 6.2  Définir la variable d'indice du tableau temporaire 
            int i = 0;
            // 6.3  Définir le noeud de démarrage de la recherche 
            Node node = head;
            // 6.4 Etget La méthode fonctionne de la même façon 
            while(node!=null){
                // 6.4.1  D'abord de gauche à droite 
                while(node.right!=null &&node.right.val < num){
                    node = node.right;
                }
                // 6.4.2 Sortir de la boucle, Quoi qu'il en soit,( Que le noeud droit soit vide , Ou la valeur du noeud droit est déjà supérieure ou égale à la valeur cible ),
                //  Ce noeud de la couche courante est le noeud avant d'insérer le noeud , Alors, on enregistre 
                nodes[i++] = node;
                //6.4.3 Continuer à chercher vers le bas
                node = node.down;
            }
            // 6.5 Cycle terminé, Le dernier noeud du tableau temporaire est le noeud avant du noeud cible dans la liste originale 
            Node pre = nodes[--i];
            // 6.6  Noeud qui définit la valeur cible 
            Node newNode =new Node(num, pre.right, null);
            // 6.7 Insérer
            pre.right = newNode;
            // 6.8 Longueur plus un
            this.length++;
            // 6.9  Lancer une pièce détermine si un noeud d'index doit être construit 
            coinsFlip(nodes, newNode, i);
        }
        //  La logique générale pour lancer une pièce pour décider s'il faut construire un noeud d'index est :Adoption 0,1 La question de savoir si le nombre aléatoire et la série de niveaux sont inférieurs à la valeur de référence détermine si l'indice doit être établi 
        //  Si vous construisez , Il faut d'abord voir si le niveau actuel à indexer est dans le niveau original ,
        // Si oui,Insérer, Et continuer à lancer des pièces pour décider si la couche supérieure doit être construite 
        //   Sinon, Nouveau noeud d'en - tête , Accédez au nouveau noeud d'index pour créer un nouveau niveau 
        private void coinsFlip(Node[] nodes, Node newNode, int i) {
            // 1.Définition0,1Génération de nombres aléatoires pour
            Random random = new Random();
            int coins = random.nextInt(2);
            // 2. Définir le noeud inférieur du noeud index 
            Node downNode = newNode;
            // 3. Lancer des pièces pour déterminer si l'index est construit ou non 
            while(coins == 1 && this.levels<(this.length>>6)) {
                // 3.1  Quand la pièce est lancée 1 Et lorsque la série actuelle de couches est inférieure à la valeur de référence , Créer un noeud d'index 
                if (i > 0) {
                    //3.2  Si vous avez actuellement besoin d'insérer un noeud d'index dans le niveau actuel ,Je l'ai.
                    //  Insérer le noeud avant du noeud index 
                    Node pre = nodes[--i];
                    //  Définir un nouveau noeud d'index 
                    Node newIndex = new Node(newNode.val, pre.right, downNode);
                    //  Définir le noeud droit du noeud avant comme nouveau noeud index 
                    pre.right = newIndex;
                    //  Définissez le nouveau noeud d'index au noeud inférieur du nouveau noeud d'index à construire au niveau supérieur suivant 
                    downNode = newIndex;
                    //  Continue à jouer des pièces 
                    coins = random.nextInt(2);
                } else {
                    //  Si vous avez dépassé le niveau actuel , Nouveau noeud d'index 
                    Node newIndex = new Node(newNode.val, null, downNode);
                    //  Créer un nouveau noeud d'en - tête et définir le noeud droit comme nouveau noeud d'index 
                    Node newHead = new Node(DEFAULT_VALUE, newIndex, head);
                    //  Pointez le noeud d'en - tête de la table Hop vers le nouveau noeud d'en - tête 
                    this.head = newHead;
                    //  Nombre de niveaux plus un 
                    this.levels++;
                }
            }
        }


        // 7.Supprimer le noeud, L'idée générale est de trouver le noeud cible de chaque couche pour supprimer le noeud avant , Et supprimer 
        public boolean erase(int num) {
            // 7.1 Définir les variables de résultat,Par défautfalse Aucun noeud à supprimer n'a été trouvé 
            boolean result =  false;
            // 7.2  Trouver le noeud avant du noeud cible inférieur à partir du noeud de départ 
            Node node =  get(num, head);
            // 7.3 S'il y a,Supprimer, Et supprimer le noeud de la couche suivante 
            while(node != null){
                // 7.3.1  Obtenir supprimer le noeud 
                Node right = node.right;
                // 7.3.2  Pointez le noeud droit du noeud avant de supprimer le noeud vers le noeud droit du noeud à supprimer 
                node.right = right.right;
                // 7.3.3  Pointez le noeud droit du noeud supprimé vers NULL ,Déclencheurgc
                right.right = null;
                // 7.3.4  Assigner la valeur résultante à true
                result = true;
                // 7.3.5  Continuer à rechercher le noeud avant du noeud cible à supprimer au niveau suivant 
                node =  get(num, node.down);
            }
            // 7.4  Si la suppression réussit , La longueur est réduite d'un 
            if(result){
                this.length--;
            }
            return result;
        }
    }