Skip to content

Instantly share code, notes, and snippets.

@felix021 felix021/
Created Sep 18, 2018

What would you like to do?
A Basic Skip List Implementation
import random
class Node(object):
def __init__(self, height, key=None):
self.key = key = [None] * height
def height(self):
return len(
class SkipList(object):
def __init__(self):
self.head = Node(0, None) #头节点高度为0,不需要key
def randomHeight(self, p = 0.5):
height = 1
while random.uniform(0, 1) < p and self.head.height() >= height:
height += 1
return height
def insert(self, key):
node = Node(self.randomHeight(), key)
while node.height() > self.head.height(): #保证头节点的next数组覆盖所有层次的链表
update = self.getUpdateList(key)
if update[0].next[0] is not None and update[0].next[0].key == key:
return # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
for level in range(node.height()):[level] = update[level].next[level]
update[level].next[level] = node
def getUpdateList(self, key):
update = [None] * self.head.height()
x = self.head
for level in reversed(range(len(update))):
while[level] is not None and[level].key < key:
x =[level]
update[level] = x
return update
def dump(self):
for i in range(self.head.height()):
x =[0]
y =[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y =[i]
s = '-' * len(s)
x =[0]
print ' -> <nil>'
def find(self, key):
update = self.getUpdateList(key)
if len(update) == 0:
return None
next0 = update[0].next[0]
if next0 is not None and next0.key == key:
return next0 # 0层总是包含所有元素;如果 update[0] 的下一个节点与key相等,则无需插入。
return None
def remove(self, key):
update = self.getUpdateList(key)
for i, node in enumerate(update):
if[i] is not None and[i].key == key:[i] =[i].next[i]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.