跳表（skiplist）的代码实现

痛定思痛。 2021-11-05 02:48 274阅读 0赞

[http://www.cnblogs.com/liuhao/archive/2012/07/26/2610218.html][http_www.cnblogs.com_liuhao_archive_2012_07_26_2610218.html]

跳表（skiplist）是一个非常优秀的数据结构，实现简单，插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sorted set数据结构也是有跳表实现的。

其结构如下所示：

![2012072615505668.png][]

所有操作均从上向下逐层查找，越上层一次next操作跨度越大。其实现是典型的空间换时间。

具体的细节，可参考维基百科[http://en.wikipedia.org/wiki/Skip\_list][http_en.wikipedia.org_wiki_Skip_list]

本文作者将redis的sorted set代码进行整理，将跳表部分的实现抽取出来，供参考。

skiplist.h

![复制代码][copycode.gif]

1 #ifndef __SKIPLIST_H
     2 #define __SKIPLIST_H
     3 
     4 #define SKIPLIST_MAXLEVEL 8 
     5 
     6 typedef struct skiplistNode {
     7     double score;
     8     struct skiplistNode *backward;
     9     struct skiplistLevel {
    10         struct skiplistNode *forward;
    11     }level[];
    12 }skiplistNode;
    13 
    14 typedef struct skiplist {
    15     struct skiplistNode *header, *tail;
    16     unsigned long length;
    17     int level;
    18 }skiplist;
    19 
    20 #endif

![复制代码][copycode.gif]

skiplist.c

![复制代码][copycode.gif]

1 #include "skiplist.h"
      2 #include <stdlib.h>
      3 #include <stdio.h>
      4 
      5 skiplistNode *slCreateNode(int level, double score) {
      6     skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel));
      7     sn->score = score;
      8     return sn;
      9 }
     10 
     11 skiplist *slCreate(void) {
     12     int j;
     13     skiplist *sl;
     14 
     15     sl = malloc(sizeof(*sl));
     16     sl->level = 1;
     17     sl->length = 0;
     18     sl->header = slCreateNode(SKIPLIST_MAXLEVEL, 0);
     19     for(j = 0; j < SKIPLIST_MAXLEVEL; j++) {
     20         sl->header->level[j].forward = NULL;
     21     }
     22     sl->header->backward = NULL;
     23     sl->tail = NULL;
     24     return sl;
     25 }
     26 
     27 void slFreeNode(skiplistNode *sn) {
     28     free(sn);
     29 }
     30 
     31 void slFree(skiplist *sl) {
     32     skiplistNode *node = sl->header->level[0].forward, *next;
     33 
     34     free(sl->header);
     35     while(node) {
     36         next = node->level[0].forward;
     37         slFreeNode(node);
     38         node = next;
     39     }
     40     free(sl);
     41 }
     42 
     43 int slRandomLevel(void) {
     44     int level = 1;
     45     while((rand()&0xFFFF) < (0.5 * 0xFFFF)) 
     46         level += 1;
     47     return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
     48 }
     49 
     50 skiplistNode *slInsert(skiplist *sl, double score) {
     51     skiplistNode *update[SKIPLIST_MAXLEVEL];
     52     skiplistNode *node;
     53 
     54     node = sl->header;
     55     int i, level;
     56     for ( i = sl->level-1; i >= 0; i--) {
     57         while(node->level[i].forward && node->level[i].forward->score < score) {
     58             node = node->level[i].forward;
     59         }
     60         update[i] = node;
     61     }
     62     level = slRandomLevel();
     63     if (level > sl->level) {
     64         for (i = sl->level; i< level ;i++) {
     65             update[i] = sl->header;
     66         }
     67         sl->level = level;
     68     }
     69     node = slCreateNode(level, score);
     70     for (i = 0; i < level; i++) {
     71         node->level[i].forward = update[i]->level[i].forward;
     72         update[i]->level[i].forward = node;
     73     }
     74 
     75     node->backward = (update[0] == sl->header? NULL : update[0]);
     76     if (node->level[0].forward)
     77         node->level[0].forward->backward = node;
     78     else
     79         sl->tail = node;
     80     sl->length++;
     81     return node;
     82 }
     83 
     84 void slDeleteNode(skiplist *sl, skiplistNode *x, skiplistNode **update){
     85     int i;
     86     for (i = 0; i < sl->level; i++) {
     87         if (update[i]->level[i].forward == x) {
     88             update[i]->level[i].forward = x->level[i].forward;
     89         }
     90     }
     91     if (x->level[0].forward) {
     92         x->level[0].forward->backward = x->backward;
     93     } else {
     94         sl->tail = x->backward;
     95     }
     96     while (sl->level > 1 && sl->header->level[sl->level-1].forward == NULL) 
     97         sl->level--;
     98     sl->length--;
     99 }
    100 
    101 int slDelete(skiplist *sl, double score) {
    102     skiplistNode *update[SKIPLIST_MAXLEVEL], *node;
    103     int i;
    104 
    105     node = sl->header;
    106     for(i = sl->level-1; i >= 0; i--) {
    107         while (node->level[i].forward && node->level[i].forward->score < score) {
    108             node = node->level[i].forward;
    109         }
    110         update[i] = node;
    111     }
    112     node = node->level[0].forward;
    113     if (node && score == node->score) {
    114         slDeleteNode(sl, node, update);
    115         slFreeNode(node);
    116         return 1;
    117     } else {
    118         return 0;
    119     }
    120     return 0;
    121 }
    122 
    123 int slSearch(skiplist *sl, double score) {
    124     skiplistNode *node;
    125     int i;
    126 
    127     node = sl->header;
    128     for (i = sl->level-1; i >= 0 ;i--) {
    129         while(node->level[i].forward && node->level[i].forward->score < score) {
    130             node = node->level[i].forward;
    131         }
    132     }
    133     node = node->level[0].forward;
    134     if (node && score == node->score) {
    135         printf("Found %d\n",(int)node->score);
    136         return 1;
    137     } else {
    138         printf("Not found %d\n", (int)score);
    139         return 0;
    140     }
    141 }
    142 
    143 void slPrint(skiplist *sl) {
    144     skiplistNode *node;
    145     int i;
    146     for (i = 0; i < SKIPLIST_MAXLEVEL; i++) {
    147         printf("LEVEL[%d]: ", i);
    148         node = sl->header->level[i].forward;
    149         while(node) {
    150             printf("%d -> ", (int)(node->score));
    151             node = node->level[i].forward;
    152         }
    153         printf("NULL\n");
    154     }
    155 }
    156 
    157 #ifdef SKIP_LIST_TEST_MAIN
    158 int main() {
    159     srand((unsigned)time(0));
    160     int count = 20, i;
    161 
    162     printf("### Function Test ###\n");
    163 
    164     printf("=== Init Skip List ===\n");
    165     skiplist * sl = slCreate();
    166     for ( i = 0; i < count; i++) {
    167         slInsert(sl,i);
    168     }
    169     printf("=== Print Skip List ===\n");
    170     slPrint(sl);
    171 
    172     printf("=== Search Skip List ===\n");
    173     for (i = 0; i < count; i++) {
    174         int value = rand()%(count+10);
    175         slSearch(sl, value);
    176     }
    177     printf("=== Delete Skip List ===\n");
    178     for (i = 0; i < count+10; i+=2) {
    179         printf("Delete[%d]: %s\n", i, slDelete(sl, i)?"SUCCESS":"NOT FOUND");
    180     }
    181     slPrint(sl);
    182 
    183     slFree(sl);
    184     sl = NULL;
    185 }
    186 #endif

![复制代码][copycode.gif]

测试结果如下所示：

![复制代码][copycode.gif]

1 ### Function Test ###
     2 === Init Skip List ===
     3 === Print Skip List ===
     4 LEVEL[0]: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
     5 LEVEL[1]: 0 -> 2 -> 4 -> 7 -> 9 -> 10 -> 11 -> 12 -> 14 -> 15 -> 17 -> 18 -> NULL
     6 LEVEL[2]: 7 -> 10 -> 12 -> 14 -> 15 -> NULL
     7 LEVEL[3]: 10 -> 14 -> 15 -> NULL
     8 LEVEL[4]: 10 -> 14 -> NULL
     9 LEVEL[5]: NULL
    10 LEVEL[6]: NULL
    11 LEVEL[7]: NULL
    12 === Search Skip List ===
    13 Found 1
    14 Found 18
    15 Not found 21
    16 Not found 24
    17 Found 10
    18 Not found 20
    19 Found 14
    20 Found 10
    21 Found 19
    22 Found 18
    23 Not found 27
    24 Found 5
    25 Found 0
    26 Found 0
    27 Found 18
    28 Not found 26
    29 Found 13
    30 Not found 28
    31 Not found 29
    32 Not found 23
    33 === Delete Skip List ===
    34 Delete[0]: SUCCESS
    35 Delete[2]: SUCCESS
    36 Delete[4]: SUCCESS
    37 Delete[6]: SUCCESS
    38 Delete[8]: SUCCESS
    39 Delete[10]: SUCCESS
    40 Delete[12]: SUCCESS
    41 Delete[14]: SUCCESS
    42 Delete[16]: SUCCESS
    43 Delete[18]: SUCCESS
    44 Delete[20]: NOT FOUND
    45 Delete[22]: NOT FOUND
    46 Delete[24]: NOT FOUND
    47 Delete[26]: NOT FOUND
    48 Delete[28]: NOT FOUND
    49 LEVEL[0]: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> NULL
    50 LEVEL[1]: 7 -> 9 -> 11 -> 15 -> 17 -> NULL
    51 LEVEL[2]: 7 -> 15 -> NULL
    52 LEVEL[3]: 15 -> NULL
    53 LEVEL[4]: NULL
    54 LEVEL[5]: NULL
    55 LEVEL[6]: NULL
    56 LEVEL[7]: NULL

[http_www.cnblogs.com_liuhao_archive_2012_07_26_2610218.html]: http://www.cnblogs.com/liuhao/archive/2012/07/26/2610218.html
[2012072615505668.png]: /images/20211104/dc8dbb7a58d7418bafc28e4f008c6d77.png
[http_en.wikipedia.org_wiki_Skip_list]: http://en.wikipedia.org/wiki/Skip_list
[copycode.gif]: /images/20211104/ac07b522c3044b7a94f25bcd7455aa62.png