本文內容框架：
§1 Skip List 介紹
§2 Skip List 定義以及構造步驟
§3 Skip List 完整實現
§4 Skip List 概率分析
§5 小結
§1 Skip List 介紹
Skip List是一種隨機化的數據結構，基于并聯的鏈表，其效率可比擬于二叉查找樹（對于大多數操作需要O(log n)平均時間）。基本上，跳躍列表是對有序的鏈表增加上附加的前進鏈接，增加是以隨機化的方式進行的，所以在列表中的查找可以快速的跳過部分列表(因此得名)。所有操作都以對數隨機化的時間進行。Skip List可以很好解決有序鏈表查找特定值的困難。
§2 Skip List 定義以及構造步驟
Skip List定義
像下面這樣（初中物理經常這樣用，這里我也盜用下）：
一個跳表，應該具有以下特征：
- 一個跳表應該有幾個層（level）組成；
- 跳表的第一層包含所有的元素；
- 每一層都是一個有序的鏈表；
- 如果元素x出現在第i層，則所有比i小的層都包含x；
- 第i層的元素通過一個down指針指向下一層擁有相同值的元素；
- 在每一層中，-1和1兩個元素都出現(分別表示INT_MIN和INT_MAX)；
- Top指針指向最高層的第一個元素。
構建有序鏈表
的一個跳躍表如下：
Skip List構造步驟：
1、給定一個有序的鏈表。
2、選擇連表中最大和最小的元素，然后從其他元素中按照一定算法（隨機）隨即選出一些元素，將這些元素組成有序鏈表。這個新的鏈表稱為一層，原鏈表稱為其下一層。
3、為剛選出的每個元素添加一個指針域，這個指針指向下一層中值同自己相等的元素。Top指針指向該層首元素
4、重復2、3步，直到不再能選擇出除最大最小元素以外的元素。
一、查找
目的：在跳躍表中查找一個元素x
在跳躍表中查找一個元素x，按照如下幾個步驟進行：
1. 從最上層的鏈（Sh）的開頭開始
2. 假設當前位置為p，它向右指向的節點為q（p與q不一定相鄰），且q的值為y。將y與x作比較
(1) x=y 輸出查詢成功及相關信息
(2) x>y 從p向右移動到q的位置
(3) x<y 從p向下移動一格
3. 如果當前位置在最底層的鏈中（S0），且還要往下移動的話，則輸出查詢失敗
二、插入
目的：向跳躍表中插入一個元素x
首先明確，向跳躍表中插入一個元素，相當于在表中插入一列從S0中某一位置出發向上的連續一段元素。有兩個參數需要確定，即插入列的位置以及它的“高度”。
關于插入的位置，我們先利用跳躍表的查找功能，找到比x小的最大的數y。根據跳躍表中所有鏈均是遞增序列的原則，x必然就插在y的后面。
而插入列的“高度”較前者來說顯得更加重要，也更加難以確定。由于它的不確定性，使得不同的決策可能會導致截然不同的算法效率。為了使插入數據之后，保持該數據結構進行各種操作均為O(logn)復雜度的性質，我們引入隨機化算法（Randomized Algorithms）。
我們定義一個隨機決策模塊，它的大致內容如下：
產生一個0到1的隨機數r r ← random()
如果r小于一個常數p，則執行方案A， if r<p then do A
否則，執行方案B else do B
初始時列高為1。插入元素時，不停地執行隨機決策模塊。如果要求執行的是A操作，則將列的高度加1，并且繼續反復執行隨機決策模塊。直到第i次，模塊要求執行的是B操作，我們結束決策，并向跳躍表中插入一個高度為i的列。
我們來看一個例子：
假設當前我們要插入元素“40”，且在執行了隨機決策模塊后得到高度為4
步驟一：找到表中比40小的最大的數，確定插入位置
步驟二：插入高度為4的列，并維護跳躍表的結構
三、刪除
目的：從跳躍表中刪除一個元素x
刪除操作分為以下三個步驟：
在跳躍表中查找到這個元素的位置，如果未找到，則退出
將該元素所在整列從表中刪除
將多余的“空鏈”刪除
§3 Skip List 完整實現
下面來定義跳表的數據結構（基于C）
首先是每個節點的數據結構
typedef struct nodeStructure
{
int key;
int value;
struct nodeStructure *forward[1];
}nodeStructure;
跳表的結構如下
typedef struct skiplist
{
int level;
nodeStructure *header;
}skiplist;
下面是跳表的基本操作首先是節點的創建
nodeStructure* createNode(int level,int key,int value)
{
nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*));
ns->key=key;
ns->value=value;
return ns;
}
列表的初始化
列表的初始化需要初始化頭部，并使頭部每層（根據事先定義的MAX_LEVEL）指向末尾（NULL）。
skiplist* createSkiplist()
{
skiplist *sl=(skiplist *)malloc(sizeof(skiplist));
sl->level=0;
sl->header=createNode(MAX_LEVEL-1,0,0);
for(int i=0;i<MAX_LEVEL;i++)
{
sl->header->forward[i]=NULL;
}
return sl;
}
插入元素
插入元素的時候元素所占有的層數完全是隨機的，通過隨機算法產生
int randomLevel()
{
int k=1;
while (rand()%2)
k++;
k=(k<MAX_LEVEL)?k:MAX_LEVEL;
return k;
}
跳表的插入需要三個步驟，第一步需要查找到在每層待插入位置，然后需要隨機產生一個層數，最后就是從高層至下插入，插入時算法和普通鏈表的插入完全相同。
bool insert(skiplist *sl,int key,int value)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p, *q = NULL;
p=sl->header;
int k=sl->level;
//從最高層往下查找需要插入的位置
//填充update
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<key))
{
p=q;
}
update[i]=p;
}
//不能插入相同的key
if(q&&q->key==key)
{
return false;
}
//產生一個隨機層數K
//新建一個待插入節點q
//一層一層插入
k=randomLevel();
//更新跳表的level
if(k>(sl->level))
{
for(int i=sl->level; i < k; i++){
update[i] = sl->header;
}
sl->level=k;
}
q=createNode(k,key,value);
//逐層更新節點的指針，和普通列表插入一樣
for(int i=0;i<k;i++)
{
q->forward[i]=update[i]->forward[i];
update[i]->forward[i]=q;
}
return true;
}
刪除節點
刪除節點操作和插入差不多，找到每層需要刪除的位置，刪除時和操作普通鏈表完全一樣。不過需要注意的是，如果該節點的level是最大的，則需要更新跳表的level。
bool deleteSL(skiplist *sl,int key)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p,*q=NULL;
p=sl->header;
//從最高層開始搜
int k=sl->level;
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<key))
{
p=q;
}
update[i]=p;
}
if(q&&q->key==key)
{
//逐層刪除，和普通列表刪除一樣
for(int i=0; i<sl->level; i++){
if(update[i]->forward[i]==q){
update[i]->forward[i]=q->forward[i];
}
}
free(q);
//如果刪除的是最大層的節點，那么需要重新維護跳表的
for(int i=sl->level-1; i >= 0; i--){
if(sl->header->forward[i]==NULL){
sl->level--;
}
}
return true;
}
else
return false;
}
查找
跳表的優點就是查找比普通鏈表快，當然查找操作已經包含在在插入和刪除過程，實現起來比較簡單。
nt search(skiplist *sl,int key)
{
nodeStructure *p,*q=NULL;
p=sl->header;
//從最高層開始搜
int k=sl->level;
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<=key))
{
if(q->key==key)
{
return q->value;
}
p=q;
}
}
return NULL;
}
完整代碼如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX_LEVEL 10 //最大層數
//節點
typedef struct nodeStructure
{
int key;
int value;
struct nodeStructure *forward[1];
}nodeStructure;
//跳表
typedef struct skiplist
{
int level;
nodeStructure *header;
}skiplist;
//創建節點
nodeStructure* createNode(int level,int key,int value)
{
nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*));
ns->key=key;
ns->value=value;
return ns;
}
//初始化跳表
skiplist* createSkiplist()
{
skiplist *sl=(skiplist *)malloc(sizeof(skiplist));
sl->level=0;
sl->header=createNode(MAX_LEVEL-1,0,0);
for(int i=0;i<MAX_LEVEL;i++)
{
sl->header->forward[i]=NULL;
}
return sl;
}
//隨機產生層數
int randomLevel()
{
int k=1;
while (rand()%2)
k++;
k=(k<MAX_LEVEL)?k:MAX_LEVEL;
return k;
}
//插入節點
bool insert(skiplist *sl,int key,int value)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p, *q = NULL;
p=sl->header;
int k=sl->level;
//從最高層往下查找需要插入的位置
//填充update
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<key))
{
p=q;
}
update[i]=p;
}
//不能插入相同的key
if(q&&q->key==key)
{
return false;
}
//產生一個隨機層數K
//新建一個待插入節點q
//一層一層插入
k=randomLevel();
//更新跳表的level
if(k>(sl->level))
{
for(int i=sl->level; i < k; i++){
update[i] = sl->header;
}
sl->level=k;
}
q=createNode(k,key,value);
//逐層更新節點的指針，和普通列表插入一樣
for(int i=0;i<k;i++)
{
q->forward[i]=update[i]->forward[i];
update[i]->forward[i]=q;
}
return true;
}
//搜索指定key的value
int search(skiplist *sl,int key)
{
nodeStructure *p,*q=NULL;
p=sl->header;
//從最高層開始搜
int k=sl->level;
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<=key))
{
if(q->key == key)
{
return q->value;
}
p=q;
}
}
return NULL;
}
//刪除指定的key
bool deleteSL(skiplist *sl,int key)
{
nodeStructure *update[MAX_LEVEL];
nodeStructure *p,*q=NULL;
p=sl->header;
//從最高層開始搜
int k=sl->level;
for(int i=k-1; i >= 0; i--){
while((q=p->forward[i])&&(q->key<key))
{
p=q;
}
update[i]=p;
}
if(q&&q->key==key)
{
//逐層刪除，和普通列表刪除一樣
for(int i=0; i<sl->level; i++){
if(update[i]->forward[i]==q){
update[i]->forward[i]=q->forward[i];
}
}
free(q);
//如果刪除的是最大層的節點，那么需要重新維護跳表的
for(int i=sl->level - 1; i >= 0; i--){
if(sl->header->forward[i]==NULL){
sl->level--;
}
}
return true;
}
else
return false;
}
void printSL(skiplist *sl)
{
//從最高層開始打印
nodeStructure *p,*q=NULL;
//從最高層開始搜
int k=sl->level;
for(int i=k-1; i >= 0; i--)
{
p=sl->header;
while(q=p->forward[i])
{
printf("%d -> ",p->value);
p=q;
}
printf("\n");
}
printf("\n");
}
int main()
{
skiplist *sl=createSkiplist();
for(int i=1;i<=19;i++)
{
insert(sl,i,i*2);
}
printSL(sl);
//搜索
int i=search(sl,4);
printf("i=%d\n",i);
//刪除
bool b=deleteSL(sl,4);
if(b)
printf("刪除成功\n");
printSL(sl);
system("pause");
return 0;
}
§4 Skip List 概率分析
§5 小結
本篇博文已經詳細講解了Skip List數據結構的所有內容，應該可以有一個深入的了解。如果你有任何建議或者批評和補充，請留言指出，不勝感激，更多參考請移步互聯網。
參考：
①Skip List: http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_skl.htm
②Songeliu: http://www.spongeliu.com/63.html
③Shi Kai Lun ： http://yilee.info/skip-list.html
④Michael T. Goodrich Roberto Tamassia Algorithm Design Foundations, Analysis, and Internet Examples
⑤http://epaperpress.com/sortsearch/skl.html
轉自：http://dsqiu.iteye.com/blog/1705530