简陋跳表

import java.util.Random;

// 跳表 p 取 1/2
class Skiplist {
    final Random random = new Random();
    static final int MAX_LEVEL = 31;

    static class Node {
    	// 当前节点的值
        int key;
        // 每一层当前节点的下一个节点，next 的长度是最大层数
        Node[] next = new Node[MAX_LEVEL];

        Node() {
        }

        Node(int key) {
            this.key = key;
        }
    }

    int level;
    Node head;

    public Skiplist() {
    	// 头节点为一个不存值的哨兵节点
        head = new Node(Integer.MIN_VALUE);
        level = 0;
    }

    // 查询并返回访问过的结点（每一层中小于目标的最大的节点）
    public Node[] searchNodes(int target) {
        Node[] visited = new Node[MAX_LEVEL];
        Node cur = head;
        // 从最上层开始搜索
        for (int i = level; i >= 0; --i) {
            while (cur.next[i] != null && cur.next[i].key < target)
                cur = cur.next[i];
            visited[i] = cur;
        }
        return visited;
    }

    public boolean search(int target) {
        Node[] visitedNodes = searchNodes(target);
        if (visitedNodes[0].next[0] != null && visitedNodes[0].next[0].key == target) {
            return true;
        }
        return false;
    }

    public void add(int num) {
        Node[] visitedNodes = searchNodes(num);
        Node added = new Node(num);
        int curLevel;
        for (curLevel = 0; curLevel < MAX_LEVEL; ++curLevel) {
            if (visitedNodes[curLevel] != null) {
                added.next[curLevel] = visitedNodes[curLevel].next[curLevel];
                visitedNodes[curLevel].next[curLevel] = added;
            } else{
                head.next[curLevel] = added;
            }
            if (random.nextInt(2) == 1)
                break;
        }
        level = curLevel;
    }

    public boolean erase(int num) {
        Node[] visitedNodes = searchNodes(num);
        Node erased = visitedNodes[0].next[0];
        if (erased == null || erased.key != num)
            return false;
        for (int i = 0; i <= level; ++i) {
            if (visitedNodes[i].next[i] == null || visitedNodes[i].next[i].key != num)
                break;
            visitedNodes[i].next[i] = erased.next[i];
        }
        return true;
    }
}

来自：

力扣