寫一下跳錶

    class Skiplist {
        // 1.定義跳錶中的節點
        class Node{
            // 值
            int val;
            // 節點的右節點和下節點
            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. 定義跳錶相關屬性
        // 定義頭節點默認值
        final int DEFAULT_VALUE = -1;
        // 定義默認頭結點
        final Node HEAD =  new Node(DEFAULT_VALUE);
        // 跳錶對應的層級
        int levels;
        // 跳錶中原鏈錶的節點數
        int length;
        Node head;
        // 3.初始化,默認層級為1,長度為1,, 默認頭結點
        public Skiplist() {
            this.levels = 1;
            this.length = 1;
            this.head = HEAD;
        }
        // 4. 定義獲取從某個節點開始搜索目標值對應的節點的前一個節點(因為節點之間並沒有指向前節點的屬性,且操作跳錶中的節點
        // 都是需要從目標節點的前一個節點開始, 所以我們取目標節點的前節點)
        private Node get(int num, Node from){
            // 1.從哪個節點開始搜索
            Node node = from;
            // 2.循環的邏輯就是先從左向右，然後從上到下進行查找
            while(node!=null){
                // 2.1 如果當前節點的右節點不為空而且右節點的值還小於目標值，那麼繼續向右搜索
                while(node.right!=null && node.right.val<num){
                    node = node.right;
                }
                // 2.2 當右節點不為空時跳出循環,那麼只有可能是右節點的值大於或等於目標值了
                // 如果是等於，那麼就是找到了，直接返回目標節點的前節點
                Node right =  node.right;
                if(right!=null && right.val == num){
                    return node;
                }
                // 2.3如果不是相等情况，則繼續向下查找
                node = node.down;
            }
            return null;
        }
        // 5.查詢是否存在
        public boolean search(int target) {
            // 直接調用上面的查詢方法，從錶頭開始查找,如果返回不為空，代錶找到
            Node node = get(target, head);
            return node != null;
        }
        // 6.插入節點,大體思路是先找到原鏈錶中插入節點要插入的比特置然後進行插入,
        // 接著通過拋硬幣來决定是否建索引節點
        public void add(int num) {
            // 6.1 定義臨時數組用於存放插入的節點在每一層需要插入的比特置的前節點
            Node[] nodes = new Node[this.levels];
            // 6.2 定義臨時數組的下標變量
            int i = 0;
            // 6.3 定義搜索的開始節點
            Node node = head;
            // 6.4 和get方法的原理一樣
            while(node!=null){
                // 6.4.1 先從左向右
                while(node.right!=null &&node.right.val < num){
                    node = node.right;
                }
                // 6.4.2 跳出循環, 無論如何(不管右節點空了，或者是右節點的值已經大於或等於目標值了)，
                // 此時當前層的這個節點就是插入節點的前節點,所以我們進行記錄
                nodes[i++] = node;
                //6.4.3 繼續向下查找
                node = node.down;
            }
            // 6.5 循環完畢，此時臨時數組的最後一個節點就是原鏈錶中目標節點的前節點
            Node pre = nodes[--i];
            // 6.6 定義目標值的節點
            Node newNode =new Node(num, pre.right, null);
            // 6.7 插入
            pre.right = newNode;
            // 6.8 長度加一
            this.length++;
            // 6.9 拋硬幣决定是否要建索引節點
            coinsFlip(nodes, newNode, i);
        }
        // 拋硬幣决定是否建索引節點的大致邏輯是:通過 0,1隨機數及層級數是否小於基准值决定是否建索引
        // 如果要建，那麼首先得看下需要建索引的當前層是否是在原有層級內，
        // 如果是,則進行插入，並繼續拋硬幣决定上一層是否要建
        //   如果不是則，新建頭結點，接入新索引節點來新建新的一層
        private void coinsFlip(Node[] nodes, Node newNode, int i) {
            // 1.定義0,1的隨機數生成
            Random random = new Random();
            int coins = random.nextInt(2);
            // 2.定義索引節點的下節點
            Node downNode = newNode;
            // 3.拋硬幣决定是否建索引
            while(coins == 1 && this.levels<(this.length>>6)) {
                // 3.1 當拋的硬幣是1且當前層級數小於基准值時,進行索引節點的創建
                if (i > 0) {
                    //3.2 如果是當前需要插入索引節點在當前層級範圍內,則拿到
                    // 插入索引節點的前節點
                    Node pre = nodes[--i];
                    // 定義新索引節點
                    Node newIndex = new Node(newNode.val, pre.right, downNode);
                    // 將前節點的右節點設置為新的索引節點
                    pre.right = newIndex;
                    // 將新索引節點設置為接下來上一層的要建的新索引節點的下節點
                    downNode = newIndex;
                    // 繼續拋硬幣
                    coins = random.nextInt(2);
                } else {
                    // 如果已經超出當前層，則新建索引節點
                    Node newIndex = new Node(newNode.val, null, downNode);
                    // 新建頭結點並將右節點設置為新的索引節點
                    Node newHead = new Node(DEFAULT_VALUE, newIndex, head);
                    // 將跳錶的頭節點指向新的頭結點
                    this.head = newHead;
                    // 層級數加一
                    this.levels++;
                }
            }
        }


        // 7.删除節點,大體思路就是找到每一層目標節點要删除節點的前節點,並進行删除
        public boolean erase(int num) {
            // 7.1 定義結果變量,默認是false沒找到可以删除的節點
            boolean result =  false;
            // 7.2 從頭結點查找下目標節點的前節點
            Node node =  get(num, head);
            // 7.3 如果有,則進行删除,並進行下一層節點的删除
            while(node != null){
                // 7.3.1 獲取删除節點
                Node right = node.right;
                // 7.3.2 將删除節點的前節點的右節點指向要删除的節點的右節點
                node.right = right.right;
                // 7.3.3 將删除節點的右節點指向空,觸發gc
                right.right = null;
                // 7.3.4 將結果值賦值為true
                result = true;
                // 7.3.5 繼續查下一層需要删除的目標節點的前節點
                node =  get(num, node.down);
            }
            // 7.4 如果删除成功了,則長度减一
            if(result){
                this.length--;
            }
            return result;
        }
    }