A Basic Skip List Implementation

skiplist.py

#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]