跳表(skip List)是一種隨機化的數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，實現(xiàn)簡單，插入、刪除、查找的復(fù)雜度均為O(logN)。跳表是由William Pugh發(fā)明的，跳表的實質(zhì)是一種特殊的鏈表，只不過它在鏈表的基礎(chǔ)上增加了跳躍功能，正是這個跳躍的功能，使得在查找元素時，能夠提供O(log n)的時間復(fù)雜度。 紅黑樹等這樣的平衡數(shù)據(jù)結(jié)構(gòu)查找的時間復(fù)雜度也是O(log n)，并且相對于紅黑樹這樣的平衡二叉樹skiplist的優(yōu)點是更好的支持并發(fā)操作，因為紅黑樹在插入和刪除可能需要做一些rebanlance操作，這樣的操作會涉及到整個樹的其他部分，而skiplist的操作就顯得局部性一些，需要鎖住的節(jié)點更少，對并發(fā)也就更友好一些。并且只要熟悉鏈表的基本操作,再加之對跳表原理的理解，實現(xiàn)一個跳表數(shù)據(jù)結(jié)構(gòu)就是一個很自然的事情了，但是要實現(xiàn)像紅黑樹這樣的數(shù)據(jù)結(jié)構(gòu)并非易事。

跳表在當(dāng)前熱門的開源項目中也有很多應(yīng)用，比如LevelDB的核心數(shù)據(jù)結(jié)構(gòu)memtable是用跳表實現(xiàn)的，Redis的sorted set數(shù)據(jù)結(jié)構(gòu)也是由跳表實現(xiàn)的。

跳表的基本特征：

1. 一個跳表應(yīng)該有幾個層（level）組成；
2. 跳表的第一層包含所有的元素；
3. 每一層都是一個有序的鏈表；
4. 如果元素x出現(xiàn)在第i層，則所有比i小的層都包含x；

5. 每個節(jié)點包含key/value和一個指向同一層鏈表的下個節(jié)點的指針數(shù)組。

   
   
   跳表的圖示

跳表的代碼實現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define LEVEL_MAX 32

typedef struct skiplist_node_s
{
    int key;
    int value;
    struct skiplist_node_s *next[1];
} skiplist_node_t;

typedef struct skiplist_list_s
{
    int level;
    skiplist_node_t *head;
} skiplist_list_t;


skiplist_list_t *skiplist_create(void);
bool skiplist_insert(skiplist_list_t *list, int key, int value);
bool skiplist_remove(skiplist_list_t *list, int key);
int *skiplist_find(skiplist_list_t *list, int key);
void skiplist_free(skiplist_list_t *list);

int main(int argc, char **argv)
{
    skiplist_list_t *list = skiplist_create();

    for (int i = 0; i < 1000; i++) {
        skiplist_insert(list, i, i);
    }

    for (int i = 1000 - 1; i >= 0; i--) {
        if (!skiplist_find(list, i)) {
            printf("oh no, not found...\n");
        }
    }

    for (int i = 0; i < 1000; i++) {
        skiplist_remove(list, i);
    }

    for (int i = 1000 - 1; i >= 0; i--) {
        if (skiplist_find(list, i)) {
            printf("oh no, found it...\n");
        }
    }

    skiplist_free(list);
    printf("hello skiplist\n");

    return 0;
}

int skiplist_random_level(void)
{
    int level = 1;

    while (rand() % 2) {
        level++;
    }

    return level < LEVEL_MAX ? level : LEVEL_MAX;
}

skiplist_node_t *skiplist_create_node(int level, int key, int value)
{
    skiplist_node_t *node = (skiplist_node_t *) malloc(sizeof(skiplist_node_t) +
                                                       (level - 1) * sizeof(skiplist_node_t *));
    if (!node) {
        return NULL;
    }

    memset(node, 0, sizeof(skiplist_node_t) + (level - 1) * sizeof(skiplist_node_t *));
    node->key = key;
    node->value = value;

    return node;
}

skiplist_list_t *skiplist_create(void)
{
    skiplist_list_t *list = NULL;
    skiplist_node_t *head = NULL;

    list = (skiplist_list_t *) malloc(sizeof(skiplist_list_t));
    if (!list) {
        return NULL;
    }

    head = skiplist_create_node(LEVEL_MAX, 0, 0);
    if (!head) {
        free(list);
        return NULL;
    }

    /* init srand seed */
    srand(time(0));
    memset(head, 0, sizeof(skiplist_node_t) + (LEVEL_MAX - 1) * sizeof(skiplist_node_t *));
    list->level = 0;
    list->head = head;

    return list;
}

bool skiplist_insert(skiplist_list_t *list, int key, int value)
{
    skiplist_node_t *update[LEVEL_MAX];
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    /* record update array */
    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        update[i] = p;
    }
    /* if key exists, just return */
    if (q && (q->key == key)) {
        q->value = value;
        return true;
    }

    int level = skiplist_random_level();
    if (level > list->level) {
        for (i = list->level; i < level; i++) {
            update[i] = list->head;
        }
        list->level = level;
    }

    /* create node and insert it */
    p = skiplist_create_node(level, key, value);
    if (!p) {
        return false;
    }
    for (i = level - 1; i >= 0; i--) {
        p->next[i] = update[i]->next[i];
        update[i]->next[i] = p;
    }
    
    return true;
}

bool skiplist_remove(skiplist_list_t *list, int key)
{
    skiplist_node_t *update[LEVEL_MAX];
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    /* record update array */
    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        update[i] = p;
    }
    /* if key not exists, just return */
    if (!q || (q && q->key != key)) {
        return false;
    }

    /* remove node according to level */
    for (i = list->level - 1; i >= 0; i--) {
        if (update[i]->next[i] == q) {
            update[i]->next[i] = q->next[i];
            if (list->head->next[i] == NULL) {
                /* the removed node is highest level node */
                list->level--;
            }
        }
    }

    free(q);
    return true;
}

int *skiplist_find(skiplist_list_t *list, int key)
{
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        if (q && q->key == key) {
            return &(q->key);
        }
    }

    return NULL;
}

void skiplist_free(skiplist_list_t *list)
{
    if (!list) {
        return;
    }

    skiplist_node_t *curr = list->head;
    skiplist_node_t *next = NULL;
    while (curr) {
        next = curr->next[0];
        free(curr);
        curr = next;
    }

    free(list);
}

參考資料：

1. skiplist 跳躍表詳解及其編程實現(xiàn)
2. 《數(shù)據(jù)結(jié)構(gòu)與算法分析 C語言版》跳躍表章節(jié)