简介

跳表是一种基于有序链表的数据结构，通过引入多级索引来加速查找操作。它类似于多级索引的有序链表，每一层的索引指向更稀疏的元素，从而减少查找的步骤。

核心思想

  1. 有序链表：底层是一个有序链表，存储所有元素。
  2. 多级索引：在有序链表的基础上，引入多级索引，每一层索引指向更稀疏的元素。
  3. 随机化：通过随机化的方式决定每个节点的层数，从而保证跳表的性能。

优点

  1. 高效查找：平均时间复杂度为 O(log n)，与平衡树相当。
  2. 简单实现：比平衡树（如红黑树）更容易实现。
  3. 动态操作：支持高效的插入和删除操作。

题目

1206. 设计跳表 - 力扣（LeetCode）

简易代码实现

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Node{
    int v;
    List<Node> next = new ArrayList<>();

    Node(){}

    Node(int _v, int _l){
        this.v = _v;
        for(int i = 0;i < _l;++i){
            next.add(null);
        }
    }

    public void expand(int level){
        // 扩容某个节点的层数为l，实际代码中只用来扩充虚拟头节点
        while(next.size() < level) next.add(null);
    }
}

class Skiplist {
    Node dummyHead;
    Random random;

    public Skiplist() {
        dummyHead = new Node(-1, 1);
        random = new Random();
    }

    // 掷硬币，0.5概率扩容一层(初始一定有一层)
    public int flipCoin(){
        int x = random.nextInt(10);
        int ret = 1;
        while(x >= 5){
            ret++;
            x = random.nextInt(10);
        }
        return ret;
    }

    public boolean search(int target) {
        Node cur = dummyHead;
        // 从最高层开始，一直找到当前层 <= target的最右侧节点，for单次循环结束后，往低处走一层
        for(int curLevel = dummyHead.next.size();curLevel >= 1;--curLevel){
            while(cur.next.get(curLevel-1) != null && cur.next.get(curLevel-1).v <= target){
                cur = cur.next.get(curLevel-1);            
            }
            if(cur.v == target) return true;
        }
        return false;
    }
    
    public void add(int num) {
        int level = flipCoin(); // 投硬币确定当前节点的层数
        // 当前节点层数大于虚拟节点层数，则先对虚拟节点进行扩容
        if(level > dummyHead.next.size()) dummyHead.expand(level);   
        Node newNode = new Node(num, level);
        Node cur = dummyHead;
        for(int curLevel = dummyHead.next.size();curLevel >= 1;--curLevel){
            // 从最高层开始，一直找到当前层小于等于num的最右侧节点
            while(cur.next.get(curLevel-1) != null && cur.next.get(curLevel-1).v <= num){
                cur = cur.next.get(curLevel-1);            
            }
            // 如果当前层处在了当前节点的层数范围内，那么将当前节点插入到当前层的链表中
            if(curLevel <= level){
                Node tmp = cur.next.get(curLevel-1);
                newNode.next.set(curLevel-1, tmp);
                cur.next.set(curLevel-1, newNode);
            }
        }
    }
    
    public boolean erase(int num) {
        Node cur = dummyHead;
        boolean ret = false;
        for(int curLevel = dummyHead.next.size();curLevel >= 1;--curLevel){
            // 找到待删除节点的前一个节点，因此要找到当前层小于num的最右侧节点，注意不是小于等于
            while(cur.next.get(curLevel-1) != null && cur.next.get(curLevel-1).v < num){
                cur = cur.next.get(curLevel-1);            
            }
            if(cur.next.get(curLevel-1) != null && cur.next.get(curLevel-1).v == num){
                Node nxt = cur.next.get(curLevel-1);
                cur.next.set(curLevel-1, nxt.next.get(curLevel-1));
                nxt.next.set(curLevel-1, null);
                ret = true;
            }
        }
        return ret;
    }
}

__END__