跳表的实现

思路

对于顺序单链表来说，插入的时间复杂度是O(1)，但是查找的时间复杂度是O(n)，因为没法进行二分查找。
但是如果链表每几个结点建立一个索引，那么就类似于二分查找了。跳表就是这种思想。

对于怎么建立索引，一般来说，都是每几个结点抽出来一个结点，然后作为索引结点。跳表思想类似，不过采用的是一种随机化的思想。比如想要每两个结点抽出来一个
作为索引结点。那么每一个结点被抽取的概率是二分之一,然后建立一个新的链表。然后对于新的链表重复以上的过程。直到链表个数到了给定的值为止。

所以说，是这样的一个链表：

• 每一个结点含有一个值
• 一堆next指针，next[i]指针指向第i层的下一个结点。

操作

查找：

1. 从最高层的第一个开始查找。
2. 如果小于，走到本层的下一个，否则走到下一层。
3. 直到最后一层位置。

插入：

1. 首先找到每一层带插入的结点的位置
2. 从第一层开始插入，插入完成之后根据概率计算是否想上一层插入。
3. 直到概率为0，或者到了最高层。

删除：

1. 同删除的步骤相同，从下向上删除。
2. 需要注意如果某一层已经不含有这个结点了，就没必要继续删除了。

实现细节：

1. 为了方便插入和删除，写一个查找待处理节点前一个结点的函数，返回每一层待插入结点的前一个结点是什么。
2. Java类中nx数组可以直接申请，因为是懒加载，所以只有使用的时候才分配空间。
3. 创建头结点，不保存值，每次操作都从头节点的开始，从最高层开始查找，直到查找到最后一层为止。

代码

class Skiplist {

    int level = 10;
    class Node {
        int val;
        Node[] ne = new Node[level];
        Node(int _val) {
            val = _val;
        }
    }
    Random random = new Random();
    Node he = new Node(-1);
    private void find(int t, Node[] ns) {       // 找到待插入结点的前一个结点
        Node cur = he;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i];
            ns[i] = cur;
        }
    }
    public boolean search(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        return ns[0].ne[0] != null && ns[0].ne[0].val == t;
    }
    public void add(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = new Node(t);
        for (int i = 0; i < level; i++) {
            node.ne[i] = ns[i].ne[i];
            ns[i].ne[i] = node;
            if (random.nextInt(2) == 0) break;
        }
    }

    public boolean erase(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = ns[0].ne[0];
        if (node == null || node.val != t) return false;
        for (int i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i];
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45