Skip List

A skip list is a probabilistic ordered structure: a base linked list with multiple "express lane" forwarding pointers above it. Each node is randomly promoted to higher levels, giving O(log n) expected search/insert/delete. Used in Redis sorted sets, LevelDB, and Java's ConcurrentSkipListMap.

Complexity

How it works

Insert: flip a coin to choose a level (geometric distribution — half of nodes at level 0, a quarter at level 1, etc.). Search: start at the top level, walk forward until the next key is too large, drop down a level, repeat. Each level halves the work, giving expected O(log n).

Python implementation

import random

MAX_LEVEL = 16
P = 0.5


class _Node:
    __slots__ = ("key", "forward")
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)


class SkipList:
    def __init__(self):
        self.head = _Node(None, MAX_LEVEL)
        self.level = 0

    def _random_level(self):
        lv = 0
        while random.random() < P and lv < MAX_LEVEL:
            lv += 1
        return lv

    def search(self, key):                          # O(log n) expected
        x = self.head
        for i in range(self.level, -1, -1):
            while x.forward[i] and x.forward[i].key < key:
                x = x.forward[i]
        x = x.forward[0]
        return x is not None and x.key == key

    def insert(self, key):                          # O(log n) expected
        update = [self.head] * (MAX_LEVEL + 1)
        x = self.head
        for i in range(self.level, -1, -1):
            while x.forward[i] and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        lv = self._random_level()
        if lv > self.level:
            self.level = lv
        n = _Node(key, lv)
        for i in range(lv + 1):
            n.forward[i] = update[i].forward[i]
            update[i].forward[i] = n


sl = SkipList()
for k in [3, 6, 1, 8, 2, 9, 4]:
    sl.insert(k)
print(sl.search(8))    # True
print(sl.search(7))    # False

Trade-offs

• Expected O(log n) for search, insert, delete; worst case O(n) (vanishingly rare).
• Simpler to implement than a balanced BST and easier to make concurrent (lock-free variants exist).
• Higher constant-factor memory than a red-black tree (multiple forward pointers per node).
• Used in Redis (sorted sets), LevelDB, RocksDB, Java ConcurrentSkipListMap.

← Back to Algorithms