跳表SkipList的原理和C实现

跳表SkipList，顾名思义是链表的一种，或者说它是单链表的变异实现，使用跳表可以将查询操作的复杂度控制到θ(lg N)，而普通的链表只能通过顺序查找，复杂度为θ(N)，如此跳表的优势就很明显了，虽然它是通过以空间换时间搞定的。

先看一下普通的有序单链表：

要在里面查找一个值就需要顺序比较，复杂度大家都清楚了。如何降低复杂度，折半查找也却可以将复杂度降到θ(lg N)，但不适应单链表，那就将折半的思想抽出来，隔一段位置就建立一个标签索引，根据标签索引缩短查找范围，就是跳表，如下图：

跳表通过对间隔的数据做一个标签索引，产生了多层单链表，在最高层依次确定查找数据的范围，最终将范围缩小到可接受值，我们看跳表其实就是一个二叉查找树的变形，只是所有的数据都在最左段，其他节点用来建立查找索引，如此跳表的插入删除就比二叉查找树方便多了。

查找过程：

例子：查找元素 117

1. 比较 21， 比 21 大，往后面找
2. 比较 37,   比 37大，比链表最大值小，从 37 的下面一层开始找
3. 比较 71,  比 71 大，比链表最大值小，从 71 的下面一层开始找
4. 比较 85， 比 85 大，从后面找
5. 比较 117， 等于 117， 找到了节点。

查找代码：

DataType *search(DataType x)
{
    DataType *p = Top;

    while(1)
    {
         while (p->right->data < x)
         {    p = p->right;
         }
         if (p->down == NULL)
         {
              return p->right;
         }
         p = p->down;
    }
}

插入过程：

首先需要确定插入数值的层数K，即数值要建立K-1个索引。K通过随机数random(0,1)掷硬币得出，即为投掷出0的次数

如：

int get_level()
{
   k=1;
   while(random(0,1))
   {
        k++;
   }
   return k;
}

如果插入的值是119,层数为2,则遍历倒数2层，插入相关的数据节点。

具体代码:

int skipnode_insert(int value)
{

    int max_level = get_skiplist_level();
    int random_level = get_random_levle();
    int level = max_level;

    /*define point to mark insert location*/
    skipnode *skiplist_heads[random_level];
    memset(skiplist_heads,0,sizeof(skipnode));

    skipnode *p = TOP;
    while(p)
    {
        while(p->next->value < value)
        {
            p = p->next;
        }
        if(level < = random_level)
        {
            skiplist_heads[level-1] = p;
            p = p->down;
            level--;
        }
    }

    p = NULL;
    skipnode * down = NULL;

    for (int i = 0; i < random_level; i++)
    {
         p = skiplist_heads[i];
         skipnode *node = (skipnode*)malloc(sizeof(skipnode));
         /*add new line*/
         if(p == NULL)
         {
            skipnode *node_head = (skipnode*)malloc(sizeof(skipnode));
            node_head->value = -1;
            node_head->down = TOP;
            node_head->next = NULL;

            p = node_head;
            TOP = node_head;
        }
        node->value = value;
        node->next = p->next;
        node->down = down;
        p->next = node;
        down = p;

    }
}

跳表SkipList的原理和C实现来自于OENHAN

链接为:https://oenhan.com/skiplist-principle/