跳表skiplist

我们在学习数据结构和算法的时候都会学到链表,它是一种很基础的数据结构,具有快速插入和删除的特点,但是如果要在链表中查询一个元素,就显得很低效了。以最简单的单链表来说,如果我要查询链表中是否包含元素n,我就需要从链表头向后一个一个的判断是否有元素n。那么是否有办法能同时兼具链表快速插入删除和快速查询的特点呢?我们知道,时间复杂度和空间复杂度通常是互斥的,很多时候我们可以牺牲空间来换取时间。跳表就基于这种思路,它依然还是链表,但是链表的结点中增加了额外的指针,消耗额外的空间,减少访问元素的时间。

跳表的基本思路

首先明确一点,跳表内部是有序链表。既然是有序的,那我们是否能联想到有序数组中二分查找呢?其实跳表的思路和二分查找有些相似。

假如我们有如下链表:

skiplist-singlelist

现在要查找链表中是否存在元素9,可以怎么实现。是不是只能从head一个一个往后查询。参考二分查找的思路,我们是否可以不要挨个往后找,而是每次往后跳几个,如果发现要查询的数比我当前的数小,那么我们再退回来,再往后跳小一点,这样反复,直到找到特定的元素为止。以上面的链表为例,依然查找元素9,一开始我向后跳3个节点,发现节点元素是6,比9小,那么我再往后跳3个节点,发现节点元素是14,比我9大,那么退回6,往后跳2个节点,恰好是9,查询就结束了。当然实际的跳表实现要比这个复杂很多,比如要决定每次往后跳多少,如果元素不在链表中如何处理等。

跳表的基本实现

根据以上的思路,我们可以在链表的节点中多存几个指针,就像这样:

skiplist

跳表的结构会比单链表复杂很多,但是像插入删除查询这些操作,还是基本的指针操作,只是指针从多个变成了多个。这里有一点需要说明,当插入一个元素时,这个插入节点要存几个指针,根据具体的算法决定,但有一点必须保证,就是存的指针越多时,它出现的概率越小。这是比较显然的,比如以上面的例子来说,总不能所有节点的指针数量都是4,那就和单链表无异了。

跳表的应用

跳表的查询效率理论上与红黑树相同,都是O(nlgn),但是具体还是依赖于决定节点高度的算法。

跳表最广泛的一个应用场景就是Redis,其他应用还是leveldb等。