Skip to content

Instantly share code, notes, and snippets.

@felix021 felix021/skiplist.py
Created Sep 18, 2018

Embed
What would you like to do?
A Basic Skip List Implementation
#coding:utf-8
import random
class Node(object):
def __init__(self, height, key=None):
self.key = key
self.next = [None] * height
def height(self):
return len(self.next)
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():
self.head.next.append(None) #保证头节点的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()):
node.next[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 x.next[level] is not None and x.next[level].key < key:
x = x.next[level]
update[level] = x
return update
def dump(self):
for i in range(self.head.height()):
sys.stdout.write('[H]')
x = self.head.next[0]
y = self.head.next[i]
while x is not None:
s = ' -> %s' % x.key
if x is y:
y = y.next[i]
else:
s = '-' * len(s)
x = x.next[0]
sys.stdout.write(s)
print ' -> <nil>'
print
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相等,则无需插入。
else:
return None
def remove(self, key):
update = self.getUpdateList(key)
for i, node in enumerate(update):
if node.next[i] is not None and node.next[i].key == key:
node.next[i] = node.next[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.