How to Build a Skip List in Python to Get Balanced-Tree Speed Without the Rotations

A skip list is an ordered data structure that gets you O(log n) average search, insertion, and deletion, the same ballpark as a balanced binary search tree, without a single rotation. Instead of rebalancing on every insert, it uses coin flips to decide how “tall” each new element should be. Redis uses one internally to back every sorted set. Java’s ConcurrentSkipListMap, RocksDB’s default write buffer, and Discord’s member lists use variants of the same idea, all documented on Wikipedia’s skip list page.

In this tutorial you will build a skip list from scratch in Python: first a plain ordered set, then a rank-aware version that can answer “what place is this player in?” in O(log n), and finally a small game leaderboard on top of it. Along the way you will hit two real bugs that anyone who implements this data structure runs into (they showed up the moment the code below was actually run, not as a rehearsed example), fix them, and then measure honestly where a skip list actually wins and where it does not.

What You Will Build and Why It Matters

Two everyday structures each solve half the problem of “keep values sorted and fast to work with”:

• A sorted array gives you O(log n) binary search, but inserting a new value means shifting every element after it, so insertion is O(n).
• A plain linked list gives you O(1) insertion once you know where to insert, but finding that spot means walking node by node from the head, so search is O(n) too.

A balanced binary search tree (AVL, red-black) solves this by keeping both operations at O(log n), but it needs rotation logic to stay balanced after every insert and delete, which is notoriously fiddly to implement correctly. A skip list gets the same expected time bounds a different way: it builds several linked lists on top of each other, where each higher list is a sparser “express lane” over the one below it, and it decides which elements make it into the express lanes with a coin flip instead of a deterministic rebalancing rule. William Pugh invented the structure in 1989 and formally published it the following year in Communications of the ACM. In an earlier 1989 paper on the same idea, quoted on Wikipedia’s skip list page, he summed up the appeal in one line:

Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

By the end of this tutorial you will have:

1. A from-scratch SkipList ordered set with insert, search, and delete.
2. An IndexableSkipList that adds O(log n) rank(value) and get_by_rank(k) queries by tracking how many elements each link “skips over.”
3. A working game Leaderboard built on top of it, with real, measured numbers on when it beats a plain sorted Python list and when it does not.

Prerequisites

• Python 3.10 or newer (this tutorial was built and run on Python 3.13.14). No third-party packages are required for the data structure itself; the test suite uses pytest.
• Comfort with basic linked-list concepts (nodes and pointers) and Big-O notation.
• A terminal and a text editor. Every command below was actually run to produce the output shown; nothing here is hypothetical.

Set up a scratch project:

mkdir skiplist-tutorial && cd skiplist-tutorial
python -m venv venv
venv\Scripts\activate   # on Linux/macOS: source venv/bin/activate
pip install pytest

Step 1: See Why Neither a Sorted Array nor a Linked List Is Enough

Before building anything clever, look at the baseline you are trying to beat. Here is a plain sorted linked list: values kept in order, one pointer per node, nothing fancy.

class _Node:
    __slots__ = ("value", "next")

    def __init__(self, value):
        self.value = value
        self.next = None


class SortedLinkedList:
    """A plain ordered linked list. Search and insert are both O(n)."""

    def __init__(self):
        self.head = None

    def insert(self, value):
        comparisons = 0
        prev = None
        node = self.head
        while node is not None and node.value < value:
            comparisons += 1
            prev = node
            node = node.next
        new_node = _Node(value)
        new_node.next = node
        if prev is None:
            self.head = new_node
        else:
            prev.next = new_node
        return comparisons

    def search(self, value):
        comparisons = 0
        node = self.head
        while node is not None and node.value < value:
            comparisons += 1
            node = node.next
        comparisons += 1
        found = node is not None and node.value == value
        return found, comparisons

Both insert and search count how many comparisons they make, so you can see the real cost instead of guessing at it. Insert 2,000 random values and search for some of them:

$ python demo1_naive.py
Inserted 2000 values.
Average comparisons per insert: 505.7
Average comparisons per search (found): 983.3
Average comparisons per search (miss): 938.8
n = 2000, so a linear scan averages roughly n/2 = 1000 comparisons.

That matches the theory exactly: with n = 2000 sorted values, a linear scan averages around n/2 comparisons whether you are inserting or searching, because there is no way to jump ahead. You either shift array elements (fast search, slow insert) or you walk a linked list one hop at a time (fast insert once you know where, slow search). A skip list is the fix: it keeps the linked list's cheap insertion but adds shortcuts on top so search does not have to visit every node.

Step 2: Understand the Skip List Idea

A skip list is built in layers. The bottom layer is an ordinary sorted linked list holding every element. Each layer above it is a sparser subsequence of the one below, and Wikipedia's own description of the structure captures the mental model well:

Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4).

That is exactly the metaphor behind the photo at the top of this post: a highway sign splitting into an EXPRESS lane, which skips ahead to the next major exit, and a LOCAL lane, which stops everywhere. Searching a skip list works the same way a driver would use that sign: start in the topmost, sparsest lane and race ahead as far as you can without overshooting the value you want. The moment the next element in that lane is too big (or does not exist), drop down one lane and keep going from where you are, never backtracking. Repeat until you reach lane 0, where the search either lands on the value or confirms it is not there.

Whether a given element gets promoted from layer i to layer i+1 is decided by a coin flip with probability p when it is inserted, not by any deliberate rebalancing pass. That is the whole trick: instead of a strict, deterministic invariant (which is what forces AVL and red-black trees to rotate), a skip list relies on randomization to keep the expected height around log base (1/p) of n. It will not always be perfectly balanced, but it is balanced enough, almost all of the time, and it never needs to reorganize existing nodes to stay that way.

Step 3: Build the Skip List's Skeleton

Each node needs one forward pointer per level it participates in, so forward is a list rather than a single pointer:

import random

MAX_LEVEL = 16
P = 0.5


class _Node:
    __slots__ = ("value", "forward")

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


class SkipList:
    """An ordered set of comparable values."""

    def __init__(self, p=P, max_level=MAX_LEVEL):
        self.p = p
        self.max_level = max_level
        self.head = _Node(None, max_level)
        self.level = 0
        self.size = 0

    def _random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level - 1:
            lvl += 1
        return lvl

head is a sentinel node that exists at every possible level from the start, so there is always a well-defined starting point for a search no matter how tall the list eventually grows. _random_level() is the coin flip: keep promoting with probability p until a flip fails or you hit the hard ceiling, max_level. Real implementations always cap the height like this. The geometric distribution behind the coin flips technically has no upper bound, so without a cap a single unlucky insert could in theory try to allocate an absurdly tall node; capping at 16 (which comfortably covers lists well past a million elements at p = 0.5) trades an astronomically unlikely edge case for a hard, predictable bound on memory per node.

Step 4: Write Search

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

Start at the head, at the current top level (self.level). At each level, keep moving forward while the next node's value is still less than what you are looking for; the moment it is not (either the next node is too big, or there is no next node), drop to the level below and continue from the same node. After falling all the way through to level 0, one more step forward either lands on the value or lands past it, so a single equality check settles the search.

Step 5: Write Insert, and Hit a Real Bug

Insertion needs to remember, at every level, the last node visited before the insertion point, called the "update path," because that is exactly where the new node's pointers need to be spliced in. Here is a completely natural first attempt at it:

def insert(self, value):
    update = [None] * (self.level + 1)
    x = self.head
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].value < value:
            x = x.forward[i]
        update[i] = x

    new_level = self._random_level()
    if new_level > self.level:
        self.level = new_level

    new_node = _Node(value, new_level)
    for i in range(new_level + 1):
        new_node.forward[i] = update[i].forward[i]
        update[i].forward[i] = new_node

This looks reasonable, and it will even work for a while. Run it on a handful of values, though, and it crashes:

$ python skiplist_v1_buggy.py
Traceback (most recent call last):
  File "skiplist_v1_buggy.py", line 59, in <module>
    sl.insert(v)
  File "skiplist_v1_buggy.py", line 43, in insert
    new_node.forward[i] = update[i].forward[i]
                          ~~~~~~^^^
IndexError: list index out of range

Here is what actually happened: update was built with exactly self.level + 1 entries, one per level that already existed. But _random_level() can draw a level higher than the list's current self.level, and when it does, the code raises self.level to match before ever populating update for those new, higher indices. The next loop then tries to read update[i] for an i that was never set, and Python (correctly) refuses.

The fix is to extend update for those brand-new levels before raising self.level, using the head as the predecessor (since nothing else has reached that height yet):

def _find_update_path(self, value):
    """Walk from the top level down, returning the node just before
    `value` at every level from 0 up to self.max_level."""
    update = [self.head] * (self.max_level + 1)
    x = self.head
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].value < value:
            x = x.forward[i]
        update[i] = x
    return update

def insert(self, value):
    """Insert value if it is not already present. Returns True if a
    new node was added, False if value was already in the set."""
    update = self._find_update_path(value)

    candidate = update[0].forward[0]
    if candidate is not None and candidate.value == value:
        return False  # already present; this is a set, not a multiset

    new_level = self._random_level()
    if new_level > self.level:
        # update[] only has real predecessors up to the old self.level;
        # every level above that is brand new, so head is the only
        # possible predecessor there.
        for i in range(self.level + 1, new_level + 1):
            update[i] = self.head
        self.level = new_level

    new_node = _Node(value, new_level)
    for i in range(new_level + 1):
        new_node.forward[i] = update[i].forward[i]
        update[i].forward[i] = new_node

    self.size += 1
    return True

Pre-sizing update to max_level + 1 and defaulting every slot to self.head sidesteps the whole problem: even a level that has never existed before already has a sensible predecessor waiting for it. This is also why a set, not a multiset: if update[0].forward[0] already equals value, insert is a no-op that returns False instead of adding a second copy.

Step 6: Write Delete

def delete(self, value):
    update = self._find_update_path(value)
    target = update[0].forward[0]
    if target is None or target.value != value:
        return False

    for i in range(self.level + 1):
        if update[i].forward[i] is not target:
            break
        update[i].forward[i] = target.forward[i]

    while self.level > 0 and self.head.forward[self.level] is None:
        self.level -= 1

    self.size -= 1
    return True

The loop unlinks target at every level it appears in, from the bottom up. It can stop the instant update[i].forward[i] is no longer target, because node levels are contiguous starting at 0: if a node occupies levels 0 through k, it never appears at level k + 1 or higher, so once level i is not a match, no higher level will be either. After removing the node, the final while loop shrinks self.level back down if the removed node happened to be the only thing keeping the top level populated, so the list does not carry dead height around forever.

Two small helpers round out the class, and the fuzz test in the next step needs both of them:

def to_list(self):
    out = []
    node = self.head.forward[0]
    while node is not None:
        out.append(node.value)
        node = node.forward[0]
    return out

def __len__(self):
    return self.size

Step 7: Prove Correctness With a Fuzz Test

Reading the code and convincing yourself it is right is not the same as proving it. The most reliable way to trust a hand-rolled data structure is to run a large number of random operations against it side by side with something you already trust, here, Python's own built-in set, and assert they agree after every single step:

import random
from skiplist import SkipList


def run_fuzz(seed, num_ops=20000, value_range=5000):
    random.seed(seed)
    sl = SkipList()
    ground_truth = set()

    for _ in range(num_ops):
        op = random.choice(["insert", "search", "delete"])
        value = random.randint(0, value_range)

        if op == "insert":
            expected_new = value not in ground_truth
            actual_new = sl.insert(value)
            assert actual_new == expected_new
            ground_truth.add(value)
        elif op == "search":
            assert sl.search(value) == (value in ground_truth)
        else:
            expected_deleted = value in ground_truth
            actual_deleted = sl.delete(value)
            assert actual_deleted == expected_deleted
            ground_truth.discard(value)

    assert sl.to_list() == sorted(ground_truth)
    assert len(sl) == len(ground_truth)
    return len(ground_truth)

Run it across ten different random seeds, 20,000 operations each:

$ python fuzz_check.py
seed=0: 20000 random ops OK, final set size=2356
seed=1: 20000 random ops OK, final set size=2293
seed=2: 20000 random ops OK, final set size=2312
seed=3: 20000 random ops OK, final set size=2394
seed=4: 20000 random ops OK, final set size=2347
seed=5: 20000 random ops OK, final set size=2319
seed=6: 20000 random ops OK, final set size=2251
seed=7: 20000 random ops OK, final set size=2273
seed=8: 20000 random ops OK, final set size=2328
seed=9: 20000 random ops OK, final set size=2347
All 10 fuzz runs passed: skip list matches Python's set exactly.

200,000 randomized operations, zero disagreements. That is a far stronger correctness signal than eyeballing the code, and it is the same technique you should reach for any time you hand-roll a data structure that already has a well-known, trusted equivalent to check against.

Step 8: Measure the Real Speedup

Add an instrumented search method that counts comparisons the same way the naive linked list did, plus a helper that reports the tallest node actually in the list:

def search_with_comparisons(self, value):
    """Same lookup as search(), but also returns how many node
    comparisons it took, for measuring real work done."""
    comparisons = 0
    x = self.head
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].value < value:
            comparisons += 1
            x = x.forward[i]
    x = x.forward[0]
    comparisons += 1
    found = x is not None and x.value == value
    return found, comparisons

def max_level_in_use(self):
    """The highest level any node other than head actually occupies."""
    node = self.head.forward[0]
    highest = 0
    while node is not None:
        highest = max(highest, len(node.forward) - 1)
        node = node.forward[0]
    return highest

Now build both structures with the same values and compare average comparisons per search, plus the skip list's real observed height against the log2(n) theory:

$ python bench.py
       n |  naive avg |  skiplist avg |  speedup |  real height |  log2(n)
============================================================================
     100 |       50.5 |           5.8 |     8.7x |            7 |      6.6
     500 |      241.3 |           7.3 |    32.9x |            7 |      9.0
    2000 |      966.2 |          11.3 |    85.3x |           12 |     11.0
   10000 |     4649.3 |          12.7 |   367.5x |           13 |     13.3
   50000 |    25732.6 |          15.4 |  1674.8x |           14 |     15.6

Two things stand out. First, the speedup grows with n exactly as advertised: at 50,000 elements the naive linked list needs roughly 1,675 times as many comparisons per search. Second, and just as important: nobody manually balanced this structure. The "real height" column, the tallest level any node actually reached, tracks the theoretical log2(n) closely at every size, purely as a byproduct of coin flips made independently at insert time. That is the whole promise of a skip list: tree-like balance, with no rebalancing code at all.

Step 9: Extend to Rank Queries With an Indexable Skip List

Plain search answers "is this value here?" It does not answer "what place is this value in?" or "what is the 500th-smallest value?" without an O(n) walk. Wikipedia describes the standard fix as an "indexable skiplist":

As described above, a skip list is capable of fast O(log n) insertion and removal of values from a sorted sequence, but it has only slow O(n) lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to O(log n). For every link, also store the width of the link.

The "width" of a link at level i is how many level-0 elements it skips over. If a level-2 link jumps straight from node A to node D, and B and C sit between them at level 0, that link's width is 3 (it "covers" B, C, and D). Track that number alongside each pointer, and you can answer rank queries by summing widths as you search, instead of counting nodes one at a time.

Insert With Width Tracking

This is a new, standalone module, so it needs its own copies of the imports, constants, node class, and the _random_level coin flip from Step 3; only the internals of insert are new:

import random

MAX_LEVEL = 16
P = 0.5


class _RankNode:
    __slots__ = ("value", "forward", "width")

    def __init__(self, value, level):
        self.value = value
        self.forward = [None] * (level + 1)
        self.width = [1] * (level + 1)


class IndexableSkipList:
    def __init__(self, p=P, max_level=MAX_LEVEL):
        self.p = p
        self.max_level = max_level
        self.head = _RankNode(None, max_level)
        self.level = 0
        self.size = 0

    def _random_level(self):
        lvl = 0
        while random.random() < self.p and lvl < self.max_level - 1:
            lvl += 1
        return lvl

    def insert(self, value):
        old_level = self.level
        update = [self.head] * (self.max_level + 1)
        rank_at = [0] * (self.max_level + 1)  # 1-indexed position of update[i]; head is 0

        x = self.head
        current_rank = 0
        for i in range(old_level, -1, -1):
            while x.forward[i] is not None and x.forward[i].value < value:
                current_rank += x.width[i]
                x = x.forward[i]
            update[i] = x
            rank_at[i] = current_rank

        candidate = update[0].forward[0]
        if candidate is not None and candidate.value == value:
            return False

        insertion_position = current_rank + 1  # 1-indexed position the new node will occupy

        new_level = self._random_level()
        if new_level > old_level:
            for i in range(old_level + 1, new_level + 1):
                update[i] = self.head
                rank_at[i] = 0
            self.level = new_level

        new_node = _RankNode(value, new_level)
        for i in range(new_level + 1):
            old_target = update[i].forward[i]
            if old_target is not None:
                old_target_position_before = rank_at[i] + update[i].width[i]
                old_target_position_after = old_target_position_before + 1
                new_node.width[i] = old_target_position_after - insertion_position
            else:
                new_node.width[i] = 1  # don't-care: forward[i] stays None
            new_node.forward[i] = old_target
            update[i].width[i] = insertion_position - rank_at[i]
            update[i].forward[i] = new_node

        for i in range(new_level + 1, old_level + 1):
            update[i].width[i] += 1

        self.size += 1
        return True

The general shape mirrors the plain insert. The new part is current_rank: as the search descends, every time it hops forward at level i, it adds that link's width, so by the time it reaches the insertion point, current_rank is exactly that point's 0-indexed position among existing elements.

That formula for new_node.width[i] was not right on the first attempt. Fuzzing this against a ground-truth sorted list (the same discipline as Step 7, this time checking rank and get-by-rank instead of membership) immediately turned up a mismatch:

AssertionError: [seed=0 op#23] get_by_rank(2) mismatch: got 1648, expected 1266

Tracing it back to the smallest possible repro (insert values one at a time and check that every level-0 width equals 1, since level 0 never skips anything) pinned down exactly where it broke, on only the second insert:

!! [after inserting 82 (step 1, old_level=1, new_level=1)] width[0] should be 1 but is 0 at node value=82, next=1729
  ^^ broke on inserting value=82 at step 1

The bug: old_target_position_before is computed from state that existed before the new node was inserted (using update[i].width[i], which has not been touched yet). But insertion_position is the new node's position after insertion. Mixing an old-numbering position with a new-numbering position gives a nonsense width. Inserting a node always lands strictly before its old target, so that target's position shifts by exactly one once the new node exists, which is exactly the + 1 already sitting in the code above (old_target_position_after = old_target_position_before + 1). Without it, level-0 widths that are supposed to always equal 1 come out as 0, or worse, negative, and every rank computed from that point onward is wrong. This is the single trickiest line in the whole tutorial: it is easy to write width-tracking code that looks correct, compiles, and runs, while silently corrupting ranks the moment two nodes at the same level are involved. Fuzzing against ground truth, not code review, is what caught it.

Delete and Rank Queries

Delete needs the mirror-image adjustment: merge two widths into one when the removed node is spliced out, or shrink a spanning link's width by one when the link only skips over the removed node without touching it directly.

def delete(self, value):
    update = [self.head] * (self.max_level + 1)
    x = self.head
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].value < value:
            x = x.forward[i]
        update[i] = x

    target = update[0].forward[0]
    if target is None or target.value != value:
        return False

    for i in range(self.level + 1):
        if update[i].forward[i] is target:
            # target itself occupies level i: splice it out and merge
            # the two widths into one, minus the one slot target used.
            update[i].width[i] += target.width[i] - 1
            update[i].forward[i] = target.forward[i]
        else:
            # target doesn't reach level i, but this link still skips
            # over it, so its span now covers one fewer real element.
            update[i].width[i] -= 1

    while self.level > 0 and self.head.forward[self.level] is None:
        self.level -= 1

    self.size -= 1
    return True

def rank(self, value):
    """0-indexed rank of value, or None if it is not present."""
    x = self.head
    current_rank = 0
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and x.forward[i].value < value:
            current_rank += x.width[i]
            x = x.forward[i]
    x = x.forward[0]
    if x is not None and x.value == value:
        return current_rank
    return None

def get_by_rank(self, k):
    """The value at 0-indexed rank k, or IndexError if out of range."""
    if k < 0 or k >= self.size:
        raise IndexError(f"rank {k} out of range for size {self.size}")
    target_position = k + 1  # 1-indexed
    x = self.head
    current_rank = 0
    for i in range(self.level, -1, -1):
        while x.forward[i] is not None and current_rank + x.width[i] <= target_position:
            current_rank += x.width[i]
            x = x.forward[i]
    return x.value

rank is search with a running total bolted on. get_by_rank descends the same way, but instead of comparing values it greedily accumulates widths without overshooting the target position, landing exactly on the right node once the loop finishes. This time, unlike delete on the plain skip list, the width-merge math held up on the first try; it only needed the same fuzz-against-ground-truth treatment (this time against bisect-maintained sorted list) to confirm that.

The same two small helpers from Step 6 round this class out too, and the leaderboard in the next step needs __len__ for its range queries:

def to_list(self):
    out = []
    node = self.head.forward[0]
    while node is not None:
        out.append(node.value)
        node = node.forward[0]
    return out

def __len__(self):
    return self.size

Step 10: Build a Real Leaderboard

With rank queries in hand, a live game leaderboard is mostly plumbing. Store each player as a (-score, player_id) tuple, so sorting ascending naturally puts the highest score first, and ties are broken by comparing player IDs:

from indexable_skiplist import IndexableSkipList


class Leaderboard:
    def __init__(self):
        self._skiplist = IndexableSkipList()
        self._entry_of = {}  # player_id -> the (neg_score, player_id) tuple currently stored

    @staticmethod
    def _key(score, player_id):
        return (-score, player_id)  # negate so ascending sort = highest score first

    def set_score(self, player_id, score):
        """Add a new player, or move an existing player to a new score."""
        old_entry = self._entry_of.get(player_id)
        if old_entry is not None:
            if old_entry == self._key(score, player_id):
                return  # no real change; skip the delete+insert round trip
            self._skiplist.delete(old_entry)
        new_entry = self._key(score, player_id)
        self._skiplist.insert(new_entry)
        self._entry_of[player_id] = new_entry

    def rank_of(self, player_id):
        """0-indexed rank (0 == first place), or None if unknown player."""
        entry = self._entry_of.get(player_id)
        if entry is None:
            return None
        return self._skiplist.rank(entry)

    def top(self, k):
        """The top k (player_id, score) pairs, highest score first."""
        k = min(k, len(self._skiplist))
        result = []
        for i in range(k):
            neg_score, player_id = self._skiplist.get_by_rank(i)
            result.append((player_id, -neg_score))
        return result

    def around(self, player_id, radius=2):
        """Players ranked near player_id, for a 'nearby rivals' panel."""
        r = self.rank_of(player_id)
        if r is None:
            return []
        lo = max(0, r - radius)
        hi = min(len(self._skiplist) - 1, r + radius)
        result = []
        for i in range(lo, hi + 1):
            neg_score, pid = self._skiplist.get_by_rank(i)
            result.append((pid, -neg_score))
        return result

Moving a player to a new score is a delete of the old entry followed by an insert of the new one, both O(log n). Populate it with 500 players and take it for a spin:

$ python leaderboard.py
Top 10:
  #1: player_49, score 9975
  #2: player_432, score 9937
  #3: player_266, score 9926
  #4: player_21, score 9925
  #5: player_237, score 9923
  #6: player_253, score 9901
  #7: player_335, score 9890
  #8: player_303, score 9873
  #9: player_478, score 9852
  #10: player_141, score 9814

Matches a from-scratch sort of all 500 players? True

player_250's rank: 410, score: 1836
Players ranked near player_250:
  player_176: 1837
  player_178: 1836
  player_250: 1836 (this player)
  player_404: 1821
  player_261: 1817

After boosting player_250 from 1836 to 10000, new rank: 0

Notice player_178 and player_250 both sit at score 1836, and they appear in that exact order because "player_178" sorts before "player_250" as a string. That is the tie-break rule from _key() working exactly as designed, not a coincidence.

Step 11: Know When Not to Reach for a Skip List

Big-O tells you the shape of a curve, not where it actually crosses another curve for your language and your data size. To find that out, compare the leaderboard above against the simplest possible alternative: a plain Python list kept sorted with the standard library's bisect module.

import bisect


class NaiveSortedLeaderboard:
    """Same behavior as Leaderboard, but backed by a plain sorted list."""

    def __init__(self):
        self._entries = []  # sorted list of (neg_score, player_id)
        self._entry_of = {}

    @staticmethod
    def _key(score, player_id):
        return (-score, player_id)

    def set_score(self, player_id, score):
        old_entry = self._entry_of.get(player_id)
        if old_entry is not None:
            pos = bisect.bisect_left(self._entries, old_entry)
            del self._entries[pos]  # O(n): shifts everything after pos
        new_entry = self._key(score, player_id)
        bisect.insort(self._entries, new_entry)  # O(n): shifts everything after the insert point
        self._entry_of[player_id] = new_entry

bisect finds the correct position in O(log n), but a Python list still has to physically shift every element after that position to actually insert or delete there, so a score update is O(n) even though the search step is fast. Time 4,000 random score updates against both implementations, at several player-count scales:

$ python bench_leaderboard.py
n_players=   500  4000 score updates -> skiplist:     16.9 ms   naive sorted list:      3.2 ms   (  0.2x slower)
n_players=  5000  4000 score updates -> skiplist:     21.3 ms   naive sorted list:      6.9 ms   (  0.3x slower)
n_players= 20000  4000 score updates -> skiplist:     25.4 ms   naive sorted list:     18.1 ms   (  0.7x slower)
n_players= 30000  4000 score updates -> skiplist:     28.0 ms   naive sorted list:     27.8 ms   (  1.0x slower)
n_players= 50000  4000 score updates -> skiplist:     32.1 ms   naive sorted list:     48.6 ms   (  1.5x slower)
n_players=100000  4000 score updates -> skiplist:     41.6 ms   naive sorted list:     94.5 ms   (  2.3x slower)
n_players=400000  4000 score updates -> skiplist:     59.4 ms   naive sorted list:    382.8 ms   (  6.4x slower)

Below roughly 20,000 players, the "worse" O(n) approach is actually faster in wall-clock time. Python's list insertion and deletion are implemented in C using a raw memory move, and that memmove is fast enough to outrun a pure-Python skip list's O(log n) work, which carries real per-node overhead: attribute lookups, object allocation, a Python-level loop at every level. The crossover in this environment lands right around 30,000 players, where the two are within a rounding error of each other. Past that, the skip list's better asymptotic behavior takes over for real, reaching 6.4 times faster at 400,000 players.

The honest lesson: for a leaderboard with a few thousand players, a plain sorted list and bisect is simpler code that will very likely run faster too. Reach for a skip list (or push the sorting into something like Redis, which implements exactly this data structure in C for its sorted sets) once you are working at a scale where the constant-factor overhead of your language stops dominating the asymptotic difference. Guessing which side of that line you are on is a mistake; measuring, the way this section just did, is not.

Common Mistakes and Gotchas

• Forgetting to extend the update path when a new node's level exceeds the current list level. This is the exact IndexError from Step 5. Always pre-size your update array to max_level + 1 and default every entry to the head, rather than sizing it to the list's current level.
• Not capping the coin-flip loop. A geometric distribution has no built-in ceiling. Every production skip list implementation caps the maximum level at a fixed constant sized for the largest list you realistically expect.
• Mixing pre-insertion and post-insertion positions when tracking width. This is the bug from Step 9. Any position computed from state that has not been updated yet belongs to the "before" numbering; forgetting to shift it by one when a new element lands before it will silently corrupt every rank query downstream.
• Treating a skip list as a multiset without deciding on purpose. The insert methods above return False and do nothing on a duplicate value. If you need duplicates (multiple players with the exact same key, for example), you need an explicit tie-break field, exactly like player_id does for the leaderboard here.
• Assuming Big-O wins automatically at every scale. Step 11's benchmark is the concrete evidence: the "better" algorithm loses outright below about 20,000 elements in this environment, purely on constant-factor overhead. Always measure at the scale you actually care about.
• Assuming this implementation is safe to share across threads. It is not. Every method above reads and mutates the same linked structure with no locking at all, so two threads calling insert at the same time can corrupt it. Java's own ConcurrentSkipListMap solves this properly: its documentation states that "insertion, removal, update, and access operations safely execute concurrently by multiple threads," but getting there takes lock-free compare-and-swap logic well beyond the scope of this tutorial, not just adding a mutex around the methods shown here.

How to Verify Everything Works End to End

Consolidate the plain skip list, the indexable skip list, and the leaderboard into one test file and run the full suite:

$ python -m pytest test_skiplist.py -v
============================= test session starts =============================
collected 12 items

test_skiplist.py::test_search_on_empty_list PASSED
test_skiplist.py::test_insert_and_search PASSED
test_skiplist.py::test_duplicate_insert_is_a_noop PASSED
test_skiplist.py::test_delete PASSED
test_skiplist.py::test_skiplist_fuzz_matches_python_set PASSED
test_skiplist.py::test_indexable_rank_and_get_by_rank PASSED
test_skiplist.py::test_indexable_delete_keeps_ranks_correct PASSED
test_skiplist.py::test_indexable_fuzz_against_bisect_ground_truth PASSED
test_skiplist.py::test_leaderboard_top_and_rank PASSED
test_skiplist.py::test_leaderboard_ties_break_by_player_id PASSED
test_skiplist.py::test_leaderboard_score_update_moves_the_player PASSED
test_skiplist.py::test_leaderboard_around PASSED

============================= 12 passed in 0.05s ==============================

If you followed along and wrote your own version, a clean pass here (plus the fuzz scripts from Steps 7 and 9 passing on a handful of different seeds) is a solid signal your implementation is correct, not just "looks right." The fuzz tests matter more than the unit tests: a skip list's behavior depends on random coin flips, so the small, fixed-input unit tests only prove one specific shape of the structure works; the fuzz tests are what actually exercise the full space of possible level combinations.

Next Steps

A skip list is one entry in a broader family of structures that trade a strict invariant for a probabilistic one to get simpler code. If this tutorial was useful, these are natural follow-ups already covered on this site:

• How to Build an LRU Cache From Scratch in Python, another ordered structure, this time built on a doubly linked list plus a hash map instead of coin flips.
• How to Build a Trie From Scratch in Python for Fast Prefix Search and Autocomplete, a deterministic alternative for a different problem shape: prefix matching instead of ordered ranking.
• How to Build Consistent Hashing in Python to Stop Cache Stampedes, a different problem (spreading keys across servers, not ranking ordered values) that reaches for the same trick: randomization instead of a rigid rule, this time to limit how much data moves when a server is added or removed.