Skip List

Imagine a subway system. The local train stops everywhere. But there's also an express train that skips most stops and only hits the major ones. And maybe a super-express that skips even more. You ride the express as far as you can, then switch to local for the last bit.

A skip list works exactly like that. At the bottom is a normal sorted linked list — every element in order. Above it are express lanes: sparser linked lists that skip over many elements, letting you jump farther with each step.

This gives \(O(\log n)\) average search — the same as a balanced BST — without any of the complex rotation logic. The structure is maintained using randomness instead.

Skip List: Insert & Search

import random

class Node:
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)

class SkipList:
    MAX = 4
    def __init__(self):
        self.head = Node(-float('inf'), self.MAX)
        self.level = 0
    def _rand_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.MAX: lvl += 1
        return lvl
    def insert(self, val):
        update = [None] * (self.MAX + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < val:
                cur = cur.forward[i]
            update[i] = cur
        lvl = self._rand_level()
        if lvl > self.level:
            for i in range(self.level+1, lvl+1): update[i] = self.head
            self.level = lvl
        n = Node(val, lvl)
        for i in range(lvl + 1):
            n.forward[i] = update[i].forward[i]
            update[i].forward[i] = n
    def search(self, val):
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < val:
                cur = cur.forward[i]
        cur = cur.forward[0]
        return cur and cur.val == val

sl = SkipList()
for v in [3, 6, 7, 9, 12]:
    sl.insert(v)
print(sl.search(7))   # True
print(sl.search(5))   # False

Output

True
False

Building the levels — coin flips

When you insert a new element, it always goes into the bottom level. Then you flip a coin. Heads? Also insert it into level 1. Flip again. Heads again? Also insert into level 2. Keep flipping until tails. On average, half the elements appear in level 1, a quarter in level 2, and so on. This naturally creates the logarithmic structure.

Searching

Start at the top-left (highest level). Move right as long as the next value is less than or equal to your target. When you can't move right, drop down one level. Repeat until you reach the bottom level. You've either found the target or confirmed it's absent.

Each level halves the remaining candidates on average
Total levels ≈ \(\log_2(n)\), so total steps ≈ \(O(\log n)\)

Insertion and deletion

For insertion: search to find where the element belongs at each level, then link it in. For deletion: find the element at each level and unlink it. Both mirror the search pattern and take \(O(\log n)\) average.

Why not just use a BST?

Balanced BSTs (AVL, Red-Black) guarantee \(O(\log n)\) worst-case but require complex rotations to stay balanced. Skip lists achieve the same average performance with simpler code. They're also easier to make concurrent — multiple threads can insert/delete without as much locking.

Complexity

SearchDrop through express lanes, expected log n hops

Fast (avg)\(O(\log n)\)

InsertSearch + link at each level; coin flip decides height

Fast (avg)\(O(\log n)\)

DeleteSearch + unlink at each level it appears in

Fast (avg)\(O(\log n)\)

SpaceExpected 2n pointers total due to geometric distribution

Linear (expected)\(O(n)\)

Skip List Range Query

import random

class Node:
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)

class SkipList:
    MAX = 4
    def __init__(self):
        self.head = Node(-float('inf'), self.MAX)
        self.level = 0
    def _rand_level(self):
        lvl = 0
        while random.random() < 0.5 and lvl < self.MAX: lvl += 1
        return lvl
    def insert(self, val):
        update = [self.head] * (self.MAX + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < val: cur = cur.forward[i]
            update[i] = cur
        lvl = self._rand_level()
        if lvl > self.level: self.level = lvl
        n = Node(val, lvl)
        for i in range(lvl+1): n.forward[i]=update[i].forward[i]; update[i].forward[i]=n
    def range_query(self, lo, hi):
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < lo: cur = cur.forward[i]
        cur = cur.forward[0]
        result = []
        while cur and cur.val <= hi: result.append(cur.val); cur = cur.forward[0]
        return result

sl = SkipList()
for v in [2, 5, 8, 11, 14, 17]: sl.insert(v)
print(sl.range_query(5, 14))  # [5, 8, 11, 14]

Output

[5, 8, 11, 14]

Skip List: Insert & Search

Building the levels — coin flips

Searching

Insertion and deletion

Why not just use a BST?

Complexity

Skip List Range Query

Quick check