1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type Link = Option<Rc<RefCell<SkipNode>>>;

/// 跳表节点
struct SkipNode {
    val: i32,
    next: Vec<Link>,
}

/// 跳表
struct SkipList {
    level: usize, // 跳表最高层级 
    head: Link,   // 跳表头
}

  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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

impl SkipNode {
    /// 新建
    pub fn new(val: i32, level: usize) -> Self {
        Self {
            val,
            next: vec![None; level],
        }
    }
}

// 生成随机level
fn get_rand_level() -> usize {
    let mut level = 1;
    let mut rng = rand::thread_rng();
    while level < LEVEL_MAX && rng.gen::<f64>() < P_FACTOR {
        level += 1;
    }

    level
}

impl SkipList {
    /// 新建跳表
    pub fn new() -> Self {
        Self {
            level: LEVEL_MAX,
            head: Some(Rc::new(RefCell::new(SkipNode::new(std::i32::MIN, LEVEL_MAX)))),
        }
    }

    /// 插入元素
    pub fn add(&mut self, val: i32)  {
        let level = get_rand_level();
        let new_node = Rc::new(RefCell::new(SkipNode::new(val, level)));

        let mut cur_link = self.head.clone();
        // 从level开始, 往下遍历各层
        for l in (0..level).rev() {
            // 从当前节点开始, 往后遍历
            while let Some(link_rc) = cur_link.clone() {
                let mut node = link_rc.borrow_mut();
                if node.val == val {
                    return;
                }
                // next节点val < 新节点val
                if let Some(next) = node.next[l].clone().filter(|n| n.borrow().val < val) {
                    // 往后移动当前指针
                    cur_link.replace(next);
                } else {
                    // 否则, 可以插入了
                    new_node.borrow_mut().next[l] = node.next[l].take();
                    // 将当前节点当前层级下一个节点指针 -> new_node
                    node.next[l].replace(new_node.clone());

                    // 中断当前层级遍历
                    break;
                }
            }
        }
    }

    /// 查找节点
    pub fn search(&self, val: i32) -> bool {
        let mut cur_link = self.head.clone();
        for l in (0..self.level).rev() {
            while let Some(link_rc) = cur_link.clone() {
                let node = link_rc.borrow();
                // 当前节点val == val
                if node.val == val {
                    return true; // 找到
                } 
                // 未找到， 继续找
                // 下个节点val <= val
                if let Some(next) = node.next[l].clone().filter(|n| n.borrow().val <= val) {
                    cur_link.replace(next);
                } else {
                    // 其他情况： 
                    // 1. 下一个节点val > val
                    // 2. 下一个节点为none
                    break;
                }
            }
        }

        false
    }

    /// 移除节点
    pub fn remove(&mut self, val: i32) -> bool {
        let mut exist = false;
        let mut cur_link = self.head.clone();
        for l in (0..self.level).rev() {
            while let Some(cur_link_rc) = cur_link.clone() {
                let mut node = cur_link_rc.borrow_mut();
                match node.next[l].clone() {
                    Some(next) if next.borrow().val == val => {
                        node.next[l] = next.borrow_mut().next[l].take();
                        exist = true;
                        break;
                    }
                    Some(next) if next.borrow().val < val => {
                        cur_link.replace(next);
                    }
                    _ => break,
                }
            }
        }

        exist
    }
}