跳表Skip List是一种随机化的数据结构由William Pugh在1989年提出。它通过在有序链表的基础上增加多层索引实现了近似二分查找的效率同时保持了链表的简单性。在普通链表中查找一个元素需要O(n)的时间。虽然平衡树如红黑树可以实现O(log n)的查找但实现复杂。文字内容参考Skip List–跳表全网最详细的跳表文章没有之一 - 简书完整代码见最下方。跳表通过建立索引来提高查找元素的效率就是典型的“空间换时间”的思想所以在空间上做了一些牺牲空间复杂度是 O(n)。元素插入到单链表的时间复杂度为 O(1)。最坏的情况就是元素 x 需要插入到每层索引中所以插入数据到各层索引中最坏时间复杂度是 O(logn)。删除元素的总时间包含查找元素的时间加删除 logn个元素的时间为 O(logn) O(logn) 2 O(logn)忽略常数部分删除元素的时间复杂度为 O(logn)。Redis 中的有序集合(zset) 支持的操作插入一个元素删除一个元素查找一个元素有序输出所有元素按照范围区间查找元素比如查找值在 [100, 356] 之间的数据其中前四个操作红黑树也可以完成且时间复杂度跟跳表是一样的。但是按照区间来查找数据这个操作红黑树的效率没有跳表高。按照区间查找数据时跳表可以做到 O(logn) 的时间复杂度定位区间的起点然后在原始链表中顺序往后遍历就可以了非常高效。节点结构typedef struct Node { char *key; // 键 char *value; // 值 struct Node **forward; // 指向不同层级的下一个节点的指针数组 } Node;每个节点都有一个forward数组数组的每个元素指向对应层的下一个节点。比如forward[0]指向第0层的下一个节点forward[1]指向第1层的下一个节点。跳表结构typedef struct _SkipList { int level; // 当前最大层数 Node *header; // 头节点不存储实际数据 int node_count; // 节点总数 } SkipList;头节点是一个特殊节点它不存储实际数据但拥有所有层的指针作为各层遍历的起点。随机层数生成int randomLevel() { int level 0; while (rand() RAND_MAX / 2 level MAX_LEVEL) level; return level; }每个节点有1/2的概率增加一层这保证了跳表的平衡性。插入操作插入操作是跳表最核心的功能分为三步int sl_insert(SkipList *skipList, char *key, char *value) { // 1. 查找插入位置 Node *update[MAX_LEVEL 1]; Node *current skipList-header; for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL strcmp(current-forward[i]-key, key) 0) current current-forward[i]; update[i] current; // 记录每层的前驱节点 } current current-forward[0]; // 第一个大于等于key的节点 // 2. 如果key不存在插入新节点 if (current NULL || strcmp(current-key, key) ! 0) { int level randomLevel(); // 随机生成层数 // 处理层数增加的情况 if (level skipList-level) { for (int i skipList-level 1; i level; i) update[i] skipList-header; skipList-level level; } // 3. 创建并插入新节点 Node *newNode createNode(level, key, value); for (int i 0; i level; i) { newNode-forward[i] update[i]-forward[i]; update[i]-forward[i] newNode; } skipList-node_count; return 0; } return 1; // key已存在 }查找操作查找操作利用了多层索引快速定位Node *sl_search(SkipList *skipList, char *key) { Node *current skipList-header; // 从最高层开始查找 for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL strcmp(current-forward[i]-key, key) 0) current current-forward[i]; } // 检查下一个节点是否为目标 current current-forward[0]; if (current strcmp(current-key, key) 0) return current; return NULL; }删除操作删除操作需要更新所有层的指针int sl_delete(SkipList *skipList, char *key) { // 查找并记录每层的前驱 Node *update[MAX_LEVEL 1]; Node *current skipList-header; for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL strcmp(current-forward[i]-key, key) 0) current current-forward[i]; update[i] current; } current current-forward[0]; if (current strcmp(current-key, key) 0) { // 更新所有层的指针跳过当前节点 for (int i 0; i skipList-level; i) { if (update[i]-forward[i] current) update[i]-forward[i] current-forward[i]; } // 更新跳表层数 while (skipList-level 0 skipList-header-forward[skipList-level] NULL) skipList-level--; // 释放内存 free(current-key); free(current-value); free(current-forward); free(current); skipList-node_count--; return 0; } return -1; }修改操作修改操作相对简单先查找后更新int sl_modify(SkipList *skipList, char *key, char *value) { Node *current sl_search(skipList, key); if (current NULL) return -1; char *new_value strdup(value); if (new_value NULL) return -1; free(current-value); // 释放原值 current-value new_value; return 0; }遍历操作遍历跳表只需要沿着第0层最底层移动int sl_trcv(SkipList *skipList) { if (!skipList) return -1; printf(Total nodes: %d, Max level: %d\n, skipList-node_count, skipList-level); Node *current skipList-header-forward[0]; int i 1; while (current ! NULL) { printf(%d key:%s value:%s\n, i, current-key, current-value); current current-forward[0]; i; } return 0; }操作平均时间复杂度最坏时间复杂度空间复杂度查找O(log n)O(n)O(1)插入O(log n)O(n)O(log n)删除O(log n)O(n)O(1)修改O(log n)O(n)O(1)完整代码#include stdio.h #include string.h #include stdlib.h #define MAX_LEVEL 64 // 每一层都相当于一个链表 // 节点可能存在多个层里所以需要forward指针 // 指向当前节点所在的每一层 的下一个节点 typedef struct Node { char *key; char *value; struct Node **forward;// 指向不同层级的下一个节点的指针数组 } Node; typedef struct _SkipList { int level; // 已存节点的最大层数 Node *header;// 头节点不存储实际数据 int node_count; } SkipList; SkipList list; int randomLevel() { int level 0; while (rand() RAND_MAX / 2 level MAX_LEVEL) level; return level; } Node *createNode(int level, char *key, char *value) { Node *newNode (Node *)malloc(sizeof(Node)); if (!newNode) return NULL; newNode-key strdup(key); if (!newNode-key) { free(newNode); return NULL; } newNode-value strdup(value); if (!newNode-value) { free(newNode-key); free(newNode); return NULL; } newNode-forward (Node **)malloc((level 1) * sizeof(Node *)); if (!newNode-forward) { free(newNode-key); free(newNode-value); free(newNode); return NULL; } return newNode; } int createSkipList(SkipList * skipList) { // skipList (SkipList *)malloc(sizeof(SkipList)); if(skipList NULL) return -1; skipList-level 0; skipList-node_count 0; skipList-header createNode(MAX_LEVEL, , ); for (int i 0; i MAX_LEVEL; i) { skipList-header-forward[i] NULL; } return 0; } int sl_insert(SkipList *skipList, char *key, char *value) { if (!skipList || !key || !value) return -1; // update[i] 就是 第i层中小于key的最大元素 Node *update[MAX_LEVEL 1]; // 比如MAX_LEVEL6 物理上对应最大7层 Node *current skipList-header; // 从高往低查询 for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL (strcmp(current-forward[i]-key, key) 0)) current current-forward[i]; update[i] current; } // 此时的current为小于key的最大元素 current current-forward[0]; // 现在到了最底层 current前进一位 // 代码运行后current是第一个大于等于key的节点 if (current NULL || (strcmp(current-key, key) ! 0)) { int level randomLevel(); // 如果新节点层数高于当前最大层数更新header的高层指针 if (level skipList-level) { for (int i skipList-level 1; i level; i) update[i] skipList-header; // header成为新增加层的前驱节点 skipList-level level; } Node *newNode createNode(level, key, value); // 在level下的所有层插入新节点 for (int i 0; i level; i) { newNode-forward[i] update[i]-forward[i]; update[i]-forward[i] newNode; } skipList-node_count; return 0; } else { printf(Key %s already exists\n, key); return 1; } } Node *sl_search(SkipList *skipList, char *key) { if (!skipList || !key) return NULL; Node *current skipList-header; for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL (strcmp(current-forward[i]-key, key) 0)) current current-forward[i]; } current current-forward[0]; if (current (strcmp(current-key, key) 0)) { // printf(Key %s found with value %s\n, key, current-value); return current; } else { // printf(Key %s not found\n, key); return NULL; } } int sl_delete(SkipList *skipList, char *key) { if (!skipList || !key) return -1; // update[i] 就是 第i层中小于key的最大元素 Node *update[MAX_LEVEL 1]; Node *current skipList-header;// 需要删除的节点 for (int i skipList-level; i 0; --i) { while (current-forward[i] ! NULL (strcmp(current-forward[i]-key, key) 0)) current current-forward[i]; update[i] current; } current current-forward[0]; if (current NULL || (strcmp(current-key, key) ! 0)) { return -1; } else if (strcmp(current-key, key) 0) { // 每一层中更新update[i]的节点使其跳过current for (int i 0; i skipList-level; i) { update[i]-forward[i] current-forward[i]; } } else { return -1; } while (skipList-level 0 skipList-header-forward[skipList-level] NULL) { skipList-level--; } free(current-key); free(current-value); free(current-forward); free(current); skipList-node_count--; return 0; } int sl_modify(SkipList *skipList, char *key, char *value) { if (skipList NULL || key NULL || value NULL) { return -1; } Node *current sl_search(skipList, key); if (current NULL) { return -1; } char *new_value strdup(value); if (new_value NULL) { return -1; } free(current-value); // 释放原动态内存避免泄漏 current-value new_value; return 0; } int sl_trcv(SkipList *skipList) { if (!skipList ) return -1; printf(\nTotal nodes: %d, Max level: %d\n, skipList-node_count, skipList-level); Node *current skipList-header-forward[0]; int i 1; while (current ! NULL) { printf(%d key:%s value:%s\n, i, current-key, current-value); current current-forward[0]; i; } return 0; } void test_skipList_all() { // 初始化随机数生成器 srand(48); // Step 1: Create skip list if (createSkipList(list) ! 0) { printf(failed create\n); return; } printf(SkipList: level%d, node_count%d\n, list.level, list.node_count); // Step 2: Test INSERT printf(Insert (keyapple, valuefruit1): %s\n, sl_insert(list, apple, fruit1) 0 ? SUCCESS : FAILED); printf(Insert (keybanana, valuefruit2): %s\n, sl_insert(list, banana, fruit2) 0 ? SUCCESS : FAILED); printf(Insert (keycherry, valuefruit3): %s\n, sl_insert(list, cherry, fruit3) 0 ? SUCCESS : FAILED); printf(Insert (keydate, valuefruit4): %s\n, sl_insert(list, date, fruit4) 0 ? SUCCESS : FAILED); printf(Insert (keyelderberry, valuefruit5): %s\n, sl_insert(list, elderberry, fruit5) 0 ? SUCCESS : FAILED); // Test duplicate insert (should fail) printf(\nInsert duplicate key apple (should fail): %s\n, sl_insert(list, apple, fruit_dup) 0 ? SUCCESS (ERROR) : FAILED (expected)); // Test insert with NULL parameters printf(Insert with NULL key (should fail): %s\n, sl_insert(list, NULL, value) -1 ? FAILED (expected) : SUCCESS (ERROR)); // Display current state sl_trcv(list); // Step 3: Test SEARCH Node* node; char* test_keys[] {apple, banana, cherry, date, elderberry, grape, kiwi}; for (int i 0; i 7; i) { node sl_search(list, test_keys[i]); if (node) { printf(Search %s: FOUND (value%s)\n, test_keys[i], node-value); } else { printf(Search %s: NOT FOUND %s\n, test_keys[i], (i 5) ? (ERROR - should exist) : (expected)); } } // Step 4: Test MODIFY printf(Modify apple to green_apple: %s\n, sl_modify(list, apple, green_apple) 0 ? SUCCESS : FAILED); printf(Modify cherry to sweet_cherry: %s\n, sl_modify(list, cherry, sweet_cherry) 0 ? SUCCESS : FAILED); // Verify modifications node sl_search(list, apple); printf(Verify apple value: %s\n, node ? node-value : NOT FOUND); node sl_search(list, cherry); printf(Verify cherry value: %s\n, node ? node-value : NOT FOUND); // Test modify non-existing key (should fail) printf(Modify non-existing grape (should fail): %s\n, sl_modify(list, grape, purple_grape) 0 ? SUCCESS (ERROR) : FAILED (expected)); // Step 5: Test DELETE printf(Delete banana: %s\n, sl_delete(list, banana) 0 ? SUCCESS : FAILED); printf(Delete date: %s\n, sl_delete(list, date) 0 ? SUCCESS : FAILED); // Verify deletions printf(\nVerify deletions:\n); node sl_search(list, banana); printf(Search banana after delete: %s\n, node ? FOUND (ERROR) : NOT FOUND (expected)); node sl_search(list, date); printf(Search date after delete: %s\n, node ? FOUND (ERROR) : NOT FOUND (expected)); // Test delete non-existing key (should fail) printf(\nDelete non-existing grape (should fail): %s\n, sl_delete(list, grape) 0 ? SUCCESS (ERROR) : FAILED (expected)); printf(Delete non-existing kiwi (should fail): %s\n, sl_delete(list, kiwi) 0 ? SUCCESS (ERROR) : FAILED (expected)); // Step 6: Final state printf(Node count: %d, Max level: %d\n, list.node_count, list.level); sl_trcv(list); // Step 7: Test edge cases printf(Search with NULL key: %s\n, sl_search(list, NULL) NULL ? RETURNS NULL (expected) : RETURNS NON-NULL (ERROR)); printf(Delete with NULL key: %s\n, sl_delete(list, NULL) -1 ? RETURNS -1 (expected) : RETURNS SUCCESS (ERROR)); printf(Modify with NULL value: %s\n, sl_modify(list, apple, NULL) -1 ? RETURNS -1 (expected) : RETURNS SUCCESS (ERROR)); } int main(void) { test_skipList_all(); return 0; }