# Skip list in Python

I've made an attempt at writing a skip list in Python. I'm using NumPy to generate geometric random variables, but since that's a bit of a heavy dependency to drag around I could easily implement that myself.

I based my implementation on the basic (none of the improvements such as capping node height etc.) algorithm here.

What do you think needs improvement?

import numpy as np

class SkipList:

def __init__(self, p=0.5):
"""
Create a Skiplist object.

>>>> l = Skiplist()                                  # An empty skip list
>>>> l = Skiplist.from_iter(zip(range(5), range(5))) # A skip list from an iterable

"""
self.p = p

self.max_height = 1

self.__length = 0

def from_iter(it, p=0.5):
"""
Create a SkipList from an iterable of (Key, Value) tuples
"""
s = SkipList(p=p)
for k, v in it:
s.insert(k, v)

return s

def __getitem__(self, key):
for level in range(self.max_height - 1, -1, -1):
while curr.forward[level] and curr.forward[level].key < key:
curr = curr.forward[level]

res = curr.forward
if res and res.key == key:
return res.value
else:

def __setitem__(self, key, value):
"""
If the key is already present, the current value will be overwritten with the new value.
"""
new_node = None
update = [None for _ in range(self.max_height)]
for level in range(self.max_height - 1, -1, -1):
while curr.forward[level] and curr.forward[level].key < key:
curr = curr.forward[level]

update[level] = curr

if curr.forward and curr.forward.key == key:
curr.forward.value = value
else:
height = np.random.geometric(self.p)
new_forward = [n.forward[l] for l, n in enumerate(update[:height])]

if height > self.max_height:
new_forward += [None for _ in range(self.max_height, height)]
self.head.forward += [None for _ in range(self.max_height, height)]
update += [self.head for l in range(self.max_height, height)]
self.max_height = height

new_node = SkipList.Node(key=key, value=value, forward=new_forward)

for l, n in enumerate(update[:height]):
n.forward[l] = new_node

self.__length += 1

def __delitem__(self, key):
update = [None for _ in range(self.max_height)]
for level in range(self.max_height - 1, -1, -1):
while curr.forward[level] and curr.forward[level].key < key:
curr = curr.forward[level]

update[level] = curr

del_node = curr.forward
if del_node and del_node.key == key:
for l, f in enumerate(del_node.forward):
update[l].forward[l] = f
self.__length -= 1
else:

def items(self):
"""
Generator in the style of dict.items
"""
while curr:
yield (curr.key, curr.value)
curr = curr.forward

def __contains__(self, key):
try:
self[key]
except KeyError:
return False

return True

def __iter__(self):
while curr:
yield curr.key
curr = curr.forward

def __len__(self):
return self.__length

def __eq__(self, other):
if len(self) != len(other):
return False

for (k1, v1), (k2, v2) in zip(self.items(), other.items()):
if not (k1 == k2 and v1 == v2):
return False

return True

class Node:
def __init__(self, key=None, value=None, forward=None):
if forward is None:
forward = [None]

self.key = key
self.value = value
self.forward = forward


Remove repetition

You have almost identical code:

def items(self):
"""
Generator in the style of dict.items
"""
while curr:
yield (curr.key, curr.value)
curr = curr.forward

def __iter__(self):
while curr:
yield curr.key
curr = curr.forward


You may avoid the repetition writing:

def __iter__(self):
for key, _ in self.items():
yield key


The nested loops:

    for level in range(self.max_height - 1, -1, -1):
while curr.forward[level] and curr.forward[level].key < key:
curr = curr.forward[level]


Are repeated identical 3 times, extract them into a function.

Use the all built-in

You do not need a manual for loop in __eq__:

def __eq__(self, other):
if len(self) != len(other):
return False

return all(self_pair == other_pair
for self_pair, other_pair in zip(self.items(), other.items())


all and avoiding tuple unpacking is closer to how you would describe the function in English (all pairs should be equal)

You may also use and instead of a separate if

def __eq__(self, other):
return len(self) == len(other) and \
all(self_pair == other_pair
for self_pair, other_pair in zip(self.items(), other.items())


It makes the code even nearer to English (The length should be equal and all pairs should be equal)

• Thanks! I've made the changes. One thing I'm unsure about is that the function I created to replace the repated loop code builds the update list even when it's not necessary (i.e. for getitem). – Davis Yoshida Jan 31 '16 at 3:56