跳跃表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但原理相当简单，只要你能熟练操作链表，就能轻松实现一个跳跃表。
skip_list
从图中可以看到， 跳跃表主要由以下部分构成：
表头(head)：负责维护跳跃表的节点指针。
跳跃表节点：保存着元素值，以及多个层。
层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
表尾：全部由 NULL 组成，表示跳跃表的末尾。
跳跃表有如下特点：
每个跳跃表由很多层结构组成。
每一层都是一个有序链表，且第一个节点是头节点。
最底层的有序链表包含所有节点。
每个节点可能有多个指针，这与节点所包含的层数有关。
跳跃表的查找、插入、删除的时间复杂度均为O(log N)。
代码实现：
import random
MAX_DEPTH = 5
class SkipNode:
def __init__(self, height = 0, elem = None):
self.elem = elem
self.next = [None]*height
def __repr__(self):
return str(self.elem)
class SkipList:
def __init__(self):
self.head = SkipNode()
def updateList(self, elem):
update = [None] * len(self.head.next)
x = self.head
for i in reversed(range(len(self.head.next))):
while x.next[i] != None and \
x.next[i].elem < elem:
x = x.next[i]
update[i] = x
return update
def find(self, elem, update=None):
if update == None:
update = self.updateList(elem)
if len(update) > 0:
candidate = update[0].next[0]
if candidate != None and candidate.elem == elem:
return candidate
return None
def insert(self, elem):
node = SkipNode(self.randomHeight(), elem)
while len(self.head.next) < len(node.next):
self.head.next.append(None)
update = self.updateList(elem)
if self.find(elem, update) == None:
for i in range(len(node.next)):
node.next[i] = update[i].next[i]
update[i].next[i] = node
def randomHeight(self):
k = 1
while random.randint(0, 1):
k = k + 1
if k == MAX_DEPTH:
break
return k
def remove(self, elem):
update = self.updateList(elem)
x = self.find(elem, update)
if x != None:
for i in range(len(x.next)):
update[i].next[i] = x.next[i]
if self.head.next[i] == None:
self.head.next = self.head.next[:i]
return
def traversal(self):
for i in reversed(range(len(self.head.next))):
x = self.head
line = []
while x.next[i] != None:
line.append(str(x.next[i].elem))
x = x.next[i]
print('line{}: '.format(i+1) + '->'.join(line))
主要方法updateList的作用是，从跳跃表的最顶层开始依次向下查找，找到该层级中比给定元素elem小的最大一个元素，将该元素保存起来，重复以上步骤知道到达最底层。它返回一个列表update，update[0]表示第一层最后一个比elem小的元素，以此类推。该方法可以使得插入删除操作变得更加简单。
在向跳跃表中插入新的结点时候，我们需要生成该结点的层数。使用抛硬币的思想随机生成层数，如果是正面(random.randint(0, 1) == 1)则层数加一，直到抛出反面为止。其中的 MAX_DEPTH 是防止如果运气太好，层数就会太高，而太高的层数往往并不会提供额外的性能。