跳跃链表(SkipList/LeapList)

链表(SkipList/LeapList)"/>

跳跃链表(SkipList/LeapList)

跳跃链表(LeapList/SkipList)

文章目录

• 跳跃链表(LeapList/SkipList)
• 前言
• 一、跳跃链表是什么？
• 二、跳跃链表的定义
• • 1.链表结构的定义
  • 2.跳跃链表的定义
• 三、跳跃链表具体操作的实现
• • 1.查询操作
  • 2.插入操作
  • 3.删除操作的实现
  • 4.销毁节点
  • 5.打印节点值

前言

想必我们在数据结构中已经对单链表有了一定的了解。此处我们介绍的跳跃链表是对单链表的一种进阶，考虑到一个单链表结构如下：

对该有序单链表的查询，删除，插入等操作的时间复杂度均为O(n)。此时我们引入跳跃链表可以大大加快链表的查询速度，跳跃链表结构如下所示：

一、跳跃链表是什么？

根据前言中的介绍，我们可以简单的理解为：跳跃链表就是一个具有多层的单链表，是一种用空间换时间的链表结构。下面将具体阐述单链表的定义及具体操作的实现。

二、跳跃链表的定义

1.链表结构的定义

链表节点的定义如下：

struct node{int key; // 用来存储节点的值struct node** forward; // struct node* forward[]
};

关于上述节点中的forward属性，可以理解为struct node* forward[]更好理解。因为跳跃链表是一个多层单链表组成的结构，传统的单链表节点定义中有一个next指针，而跳跃链表有多层，所以这里用forward数组存储当前节点对应每一层的next指针。

2.跳跃链表的定义

跳跃链表的定义：

struct leapList {double p;  // 概率值int maxHeight;  // 整个链表的最高层数int currentHeight;  // 当前所使用的的最高层数struct node* head;  // 头节点
};

上述为跳跃链表的结构定义，主要对double p; 概率值这个属性进行阐述，该属性的作用主要是针对insert操作，当插入一个节点时，将考虑是不是要将其插入到更高层的上面，使用一个随机函数获取概率，然后与指定概率值p 进行比较，根据结果来确定是否插入到更高层，
如下图：假设现在要插入88，首先在最下层，87后，89前面的位置进行插入，但是插入完之后要不要在第二层，也就是67与90之间插入呢?此时这个概率值p就发挥了作用。

三、跳跃链表具体操作的实现

1.查询操作

跳跃链表在查找某个值时，首先会在最上面一层进行查找，然后如果未找到，再进入到下一层，如果到了底层还没有找到，那就返回NOT_FOUND：
如下图所示，当查找89节点时，现在最上面那一层进行查找，将89与67进行比较，67<89于是与145进行比较，89<145, 所以节点会落在这个区间之内，于是转到下一层查找，下一层90>89，继续进入到下一层,87<89然后继续比较87后面的元素，89==89，此时则找到该节点存储在该链表中，总共比较了5次，如果普通单链表要查询7次，当数据量比较大时，这种查询的优势将会更明显。

查询操作的实现:

/* Value indicating the item is not found. */
#define NOTFOUND (-1)/* Queries the leap list for the given key and places the result in the solution structure. */
int findKey(int key, struct leapList *list){int found = NOTFOUND;int element = key;int requiredAccesses = 0;  // 用来记录查询操作所需要的时间struct node* pmove = list->head;struct node* temporary = NULL;for(int i=list->currentHeight-1;i>=0;i--){while(pmove->forward[i]!=NULL){if(pmove->forward[i]==temporary){break;}else{requiredAccesses++;temporary = pmove->forward[i];if(temporary->key<key){pmove = pmove->forward[i];}else if(temporary->key==key){found = i;break;}else{break;}}}if(found!=NOTFOUND){break;}}return found;
}

2.插入操作

前面在链表的定义部分已经对属性值p进行了阐述：
当插入一个节点时，将考虑是不是要将其插入到更高层的上面，使用一个随机函数获取概率，然后与指定概率值p 进行比较，根据结果来确定是否插入到更高层，
如下图：假设现在要插入88，首先在最下层，87后，89前面的位置进行插入，但是插入完之后要不要在第二层，也就是67与90之间插入呢?根据概率值p进行决定，是否插入到较高层，假设现在将88插入到第一层之后，根据与概率值判断，计算的概率值<p,要插入到第二层，插入完之后再进行概率判断，直至currentHeight=MaxHeight或者计算的概率值>=p将不再插入到最高层。

插入操作的实现：
update[]数组用来记录每一层的前一个节点，即prev指针，插入节点之后要对prev的next指针进行更新

void insertKey(int key, struct leapList *list){// update[]:record the nodes which will be modifystruct node* *update = malloc(sizeof(struct node*)*list->maxHeight);for(int i=0;i<list->maxHeight;i++){update[i] = NULL;}// find the nodes which will be modifystruct node* pmove = list->head;for(int i=list->currentHeight-1;i>=0;--i){while(pmove->forward[i]!=NULL && pmove->forward[i]->key<key){pmove = pmove->forward[i];}update[i] = pmove;}// insert the dataint newHeight = 1;  // new level// 计算要插入的层数while(newHeight < list->maxHeight && (double) rand() / RAND_MAX < list->p){newHeight++;}if(newHeight>list->currentHeight){for(int i=list->currentHeight;i<newHeight;i++){update[i] = list->head;}list->currentHeight = newHeight;}struct node* newNode = malloc(sizeof(struct node));newNode->forward = malloc(sizeof(struct node)*list->maxHeight);for(int i=0;i<list->maxHeight;++i){newNode->forward[i] = NULL;}newNode->key = key;for(int i=0;i<newHeight;i++){newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}free(update);
}

3.删除操作的实现

删除操作也需要一个update[]数组来记录要删除节点每层的前一个指针

void deleteKey(int key, struct leapList *list){struct node* *update = malloc(sizeof(struct node*)*list->maxHeight);for(int i=0;i<list->maxHeight;i++){update[i] = NULL;}struct node* pmove = list->head;for(int i=list->currentHeight-1;i>=0;i--){while(pmove->forward[i]!=NULL&&pmove->forward[i]->key<key){pmove = pmove->forward[i];}update[i] = pmove;}pmove = pmove->forward[0];if(pmove==NULL){free(update);return;}if(pmove->key==key){for(int i=0;i<list->currentHeight;i++){if(update[i]->forward[i]!=pmove) break;update[i]->forward[i] = pmove->forward[i];}// 删除结点之后可能会出现当前的最高层没有节点，那么就将当前的层数-1while(list->currentHeight>1&& list->head->forward[list->currentHeight-1]==NULL){--list->currentHeight;}free(pmove);pmove=NULL;}free(update);
}

4.销毁节点

对当前链表已经申请的内存进行释放

void freeList(struct leapList *list){struct node* head = list->head;struct node** forward = head->forward;struct node* pmove = forward[0];while(pmove!=NULL){struct node* del = pmove;pmove = pmove->forward[0];free(del);del = NULL;}
}

5.打印节点值

level代表要打印的层

void printLevel(struct leapList *list, int level){if(!list){printf("\n");return;}/* IMPLEMENT (Part B): loop over list at given level, printing out each value. *//* Note: while additional next elements, print a space after the key. If no additional next elements, print a new line and then return. */struct node* pmove = list->head->forward[level];while(pmove!=NULL){printf("%d",pmove->key);pmove = pmove->forward[level];if(pmove!=NULL){printf(" ");}}printf("\n");return;
}