1.简介

跳跃表(Skip List)是在链表的基础上增加了“跳跃”的功能，即加上了【多级索引】，通过索引来快速查找，可以支持快速的删除、插入和查找操作。它实际上是一种增加了前向指针的链表，是一种随机化的数据结构。其具有如下性质：

1. 由很多层链表组成
2. 每一层都是一个有序的链表
3. 最底层（level 1）的链表包含所有元素
4. 如果一个元素出现在 level i 层的链表中，则它在 level i 之下的链表也都会出现
5. 每个节点都包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

例如，对于下图所示的单链表而言，即使数据是有序的，但是如果想要查找某个数据，只能从头节点开始向后遍历，查询效率低，时间复杂度为 (O(n))：

将其变为跳表形式，则如下图所示：

如果给其继续添加多级索引，那么其结构如下所示：

2.代码实现

2.1 节点定义

一个普通节点，既要指向同一层的下一个节点，还要指向下一层的同一个节点，因此要有两个指针域 next_ 和 down_。此外，为了便于操作，还需要一个头节点类型，且在头节点中还需要记录当前跳表的最大层数，其代码实现如下：

    // 普通节点类型
    struct Node {
        Node(int data = int())
            : data_(data)
            , next_(nullptr)
            , down_(nullptr) { }
        int   data_; // 数据域
        Node* next_; // 指向同一层后一个节点的指针域
        Node* down_; // 指向下一层同一个节点的指针域
    };
    
    // 跳跃表的头节点类型
    struct HeadNode : public Node {
        HeadNode(int level)
            : level_(level) { }
        int level_; // 跳跃表的层数
    };

2.2 查询操作

如下图所示，为在一个跳跃表中查询元素 90 时的过程：

其步骤如下：

1. 比较 -1，比 -1 大，往后面找；
2. 比较 21，比 21 大，往后面找；
3. 比较 37，比 37 大，由于 37 的下一个节点为空，故从 37 的下面一层开始找；
4. 比较 71，比 71 大，由于 71 的下一个节点为空，故从 71 的下面一层开始找；
5. 比较 85，比 85 大，往后面找；
6. 比较 90，等于 90，找到了该节点；

其代码实现如下：

bool SkipList::find(int val) {
    Node *pre = head_, *cur = pre->next_;
    for (;;) {
        if (cur != nullptr) {
            if (cur->data_ < val) {
                pre = cur;
                cur = cur->next_;
                continue;
            } else if (cur->data_ == val) {
                return true;
            }
        }
        
        if (pre->down_ == nullptr) {
            // 此时遍历到了第一层 都没有找到该节点
            break;
        }
        
        pre = pre->down_;
        cur = pre->next_;
    }
    return false;
}

2.3 插入操作

当插入一个元素时，我们应该通过丢硬币的方式选择其所在的层数，其代码实现如下：

int SkipList::getLevel() const {
    int level = 1;
    while (rand() % 2 == 1) {
        level++;
    }
    return level;
}

当确定了元素所在的层数为 k 之后，就需要在 1~k 层之间都创建该节点，同时也要确保最多增加 1 层。当创建完成后，就需要从头节点开始往下查找，找到第 k 层，然后就开始向后查找，直到找到合适的位置，将新节点插入，完成后进入下一层，继续向后查找合适位置，重复此操作直到进入了第 1 层并插入完成为止。

其代码实现如下：

void SkipList::add(int val) {
    if (find(val)) return;

    int level = getLevel();
    // level过大时 只增长一层
    if (level > head_->level_) {
        level           = head_->level_ + 1;
        HeadNode* hnode = new HeadNode(level);
        hnode->down_    = head_;
        head_           = hnode;
    }
    
    // 创建level层的data节点 修改down_指针域
    Node** nodelist = new Node*[level];
    for (int i = level - 1; i >= 0; i--) {
        nodelist[i] = new Node(val);
        if (i < level - 1) {
            nodelist[i]->down_ = nodelist[i + 1];
        }
    }
    
    Node* head = head_;
    for (int i = head_->level_; i > level; i--) {
        head = head->down_;
    }
    
    Node *pre = head, *cur = pre->next_;
    for (int i = 0; i < level; i++) {
        while (cur != nullptr && cur->data_ < val) {
            pre = cur;
            cur = cur->next_;
        }
        
        // 新节点插入到pre和cur之间
        nodelist[i]->next_ = cur;
        pre->next_         = nodelist[i];
        pre = pre->down_;
        if (pre != nullptr) {
            cur = pre->next_;
        }
    }
    
    delete[] nodelist;
    nodelist = nullptr;
}

2.4 删除操作

删除操作类似于查询操作，首先需要找到待删除的节点，然后采用类似链表删除的方式进行删除即可。需要注意的是，当删除一个存在于多层的节点时，首先需要删除最上面一层的节点，然后不断进入下一层进行删除操作，而且如果删除某个节点后，当前层为空，则需要删除头节点，减小层数目。

其代码实现如下：

void SkipList::remove(int val) {
    Node *pre = head_, *cur = pre->next_;
    
    for (;;) {
        if (cur != nullptr) {
            if (cur->data_ < val) {
                pre = cur;
                cur = cur->next_;
                continue;
            } else if (cur->data_ == val) {
                // 删除cur指向的节点
                pre->next_ = cur->next_;
                delete cur;
            }
        }
        
        if (pre->down_ == nullptr) {
            break;
        }
        
        pre = pre->down_;
        if (head_->next_ == nullptr) {
            delete head_;
            head_ = static_cast<HeadNode*>(pre);
        }
        cur = pre->next_;
    }
}