SkipList是一种快速查找链表，链表元素的是有序的。由W.Pugh发明于1989年。
其算法复杂度如下：
Average Worst case
Space O(n) O(n log n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
（图片来源于WiKi）
均算法复杂度不亚于AVL和红黑树。其数据结构和操作也简单。AVL树和红黑树为保
持平衡，维护树的平衡代价高。
SkipList 现用于Redis，LevelDB等开源项目, *可以看它到很多应用场景。
根据W.Pugh的论文，其算法实现如下：
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <random>
using namespace std; #define MaxLevel 5 typedef struct SkipListNode {
int value;
int key;
int level;
SkipListNode* forward[MaxLevel];
} SkipListNode; typedef struct SkipList {
SkipListNode* head;
int level;
int length;
} SkipList; SkipListNode* makeNode(int level, int key, int value)
{
SkipListNode* pNode = (SkipListNode *)malloc(sizeof(SkipListNode));
if (!pNode) {
return NULL;
}
pNode->key = key;
pNode->value = value;
pNode->level = level;
for (int i = ; i < MaxLevel; ++i)
pNode->forward[i] = NULL; return pNode;
} void initSkipList(SkipList *pSkipList)
{
if (!pSkipList)
return;
SkipListNode* head = makeNode(, , );
if (!head)
return;
pSkipList->head = head;
pSkipList->length = ;
pSkipList->level = ; for (int i = ; i < MaxLevel; i++)
pSkipList->head->forward[i] = NULL;
} int randomLevel()
{
int newLevel = ;
while ((rand() & 0xFFFF) < (0.4 * 0xFFFF))
++newLevel;
return newLevel < MaxLevel ? newLevel : MaxLevel;
}
bool insertNode(SkipList *pSkipList, int searchKey, int newValue)
{
SkipListNode* update[MaxLevel];
if (!pSkipList)
return false; SkipListNode* pNode = pSkipList->head;
if (!pNode) {
return false;
}
for (int i = pSkipList->level - ; i >= ; i--) {
while (pNode->forward[i] && pNode->forward[i]->key < searchKey)
pNode = pNode->forward[i]; // pNode->key < searchKey < pNode->forward[i]->key
update[i] = pNode;
}
pNode = pNode->forward[];
if (pNode && pNode->key == searchKey) {
pNode->value = newValue;
}
else {
int level = randomLevel();
if (level > pSkipList->level) {
for (int i = pSkipList->level; i < level; i++) {
update[i] = pSkipList->head;
}
pSkipList->level = level;
}
pNode = makeNode(level, searchKey, newValue);
if (!pNode) {
return false;
}
for (int i = ; i < pSkipList->level; ++i) {
pNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = pNode;
}
pSkipList->length++;
}
return true;
} SkipListNode* searchNode(SkipList *pSkipList, int searchKey) {
if (!pSkipList)
return NULL; SkipListNode *pNode = pSkipList->head;
if (!pNode)
return NULL; for (int i = pSkipList->level - ; i >= ; --i) {
while (pNode->forward[i] && pNode->forward[i]->key < searchKey)
pNode = pNode->forward[i];
} pNode = pNode->forward[];
if (pNode && pNode->key == searchKey)
return pNode;
return NULL;
} bool deleteNode(SkipList* pSkipList, int searchKey) {
if (!pSkipList)
return false; SkipListNode *pNode = pSkipList->head;
SkipListNode *update[MaxLevel]; for (int i = pSkipList->level - ; i >= ; i--) {
while (pNode->forward[i] && pNode->forward[i]->key < searchKey) {
pNode = pNode->forward[i];
}
update[i] = pNode;
} pNode = pNode->forward[];
if (pNode && pNode->key == searchKey) {
for (int i = ; i < pSkipList->level; ++i) {
if (update[i] && update[i]->forward[i] != pNode) {
break;
}
update[i]->forward[i] = pNode->forward[i];
}
free(pNode);
while (pSkipList->level > &&
pSkipList->head->forward[pSkipList->level - ] == NULL) {
pSkipList->level--;
}
pSkipList->length--;
return true;
}
return false;
} void travelList(SkipList* pSkipList)
{
SkipListNode* pNode = pSkipList->head;
if (!pNode)
return; while (pNode->forward[]) {
cout << pNode->forward[]->value << " " << pNode->forward[]->level << endl;
pNode = pNode->forward[];
}
} int main()
{
SkipList list;
initSkipList(&list); insertNode(&list, , );
insertNode(&list, , );
insertNode(&list, , ); travelList(&list); SkipListNode* pNode = searchNode(&list, );
cout << pNode->value << endl; pNode = searchNode(&list, );
cout << pNode->value << endl; cout << "----" << endl;
deleteNode(&list, );
travelList(&list); cout << "----" << endl;
deleteNode(&list, );
travelList(&list); cout << "----" << endl;
deleteNode(&list, );
travelList(&list);
return ;
}