Skip List

This is an extension topic beyond most interviews; it pays off when you are asked to "design a skiplist", or when a system-design discussion turns to how ordered sets such as Redis sorted sets are built.

Intuition

Searching a sorted linked list is O(n) because you can only step one node at a time. A skip list adds express lanes on top of it:

• Level 0 is the full sorted list.
• Each node also appears on level 1 with probability p (usually 1/2), on level 2 with probability p^2, and so on. A node that appears on level i is linked to the next node that also reaches level i.
• A head sentinel reaches every level.

To search for x, start at the highest level of the head, move right while the next value is smaller than x, then drop down a level and repeat. At level 0, the next node is either x or proof that x is absent. Each level skips over about 1/p nodes before dropping, and there are about log base 1/p of n levels, so a search takes O(log n) expected time.

Insert runs the same descent but records, on every level, the last node before the insertion point (the update array). It then draws a random height for the new node and splices it into that many levels, one pointer swap per level. Delete records predecessors the same way and unlinks the node from every level it occupies. There is no rebalancing at all: randomness keeps the structure balanced in expectation, independent of the input order.

Why real systems like it: the code is much shorter than a red-black tree, range scans are just walks along level 0, and it adapts well to concurrency (Java's ConcurrentSkipListMap), which is why skip lists back Redis sorted sets and the in-memory tables of LevelDB/RocksDB.

When to use it in interviews / OAs

• "Design a skiplist" with search, add and erase (duplicates allowed) and no built-in ordered library.
• System design: explaining how a leaderboard or sorted set supports insert, delete, rank and range queries in O(log n), or why a database memtable is a skip list.
• Ordered sets in Python without libraries: possible, but a sorted list with bisect is usually simpler in an interview, and sortedcontainers is the practical choice where it is available.

Template

The core implementation. _predecessors is the heart of it: one descent that serves search, insert and delete.

import random


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

    def __init__(self, val: int | None, level: int) -> None:
        self.val = val
        self.next: list[_Node | None] = [None] * level  # next[i] = successor on level i


class Skiplist:
    MAX_LEVEL = 32  # Plenty for any n that fits in memory when P = 1/2.
    P = 0.5

    def __init__(self) -> None:
        self.head = _Node(None, self.MAX_LEVEL)  # Sentinel before every real node.
        self.level = 1  # Number of levels currently in use.

    def _random_level(self) -> int:
        lvl = 1
        while lvl < self.MAX_LEVEL and random.random() < self.P:  # Promote with probability P per level.
            lvl += 1
        return lvl

    def _predecessors(self, target: int) -> list[_Node]:
        # update[i] = last node on level i whose value is < target.
        update = [self.head] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] is not None and cur.next[i].val < target:
                cur = cur.next[i]  # Move right along the express lane.
            update[i] = cur  # Then drop down one level.
        return update

    def search(self, target: int) -> bool:
        node = self._predecessors(target)[0].next[0]
        return node is not None and node.val == target

    def add(self, num: int) -> None:  # Duplicates are allowed.
        update = self._predecessors(num)
        lvl = self._random_level()
        self.level = max(self.level, lvl)  # Levels above the old top use head as predecessor.
        node = _Node(num, lvl)
        for i in range(lvl):  # Splice into each of its levels.
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

    def erase(self, num: int) -> bool:  # Removes one copy; False if absent.
        update = self._predecessors(num)
        node = update[0].next[0]
        if node is None or node.val != num:
            return False
        for i in range(len(node.next)):
            update[i].next[i] = node.next[i]
        while self.level > 1 and self.head.next[self.level - 1] is None:
            self.level -= 1  # Drop empty top levels.
        return True


sl = Skiplist()
for x in (30, 10, 20, 20):
    sl.add(x)
assert sl.search(20) and not sl.search(25)
assert sl.erase(20) and sl.search(20)  # One copy of 20 is still there.
assert sl.erase(20) and not sl.search(20) and not sl.erase(99)

Design choices to mention:

• P = 1/2 with MAX_LEVEL = 32 is a safe default. P = 1/4 uses fewer pointers (about 1.33 per node instead of 2) at the price of slightly longer searches.
• head holds None as its value, but the code never compares it: comparisons always look at cur.next[i].val.
• Supporting rank or "k-th element" queries requires storing, for every forward pointer, how many level-0 nodes it skips (its span). Redis sorted sets do exactly that.

Complexity

Operation	Expected	Worst case
search, insert, delete	O(log n)	O(n), with vanishing probability
range scan of k items	O(log n + k)
space	O(n), about n / (1 - p) pointers	O(n * MAX_LEVEL)

The expectation is over the coin flips, not over the input, so no adversarial insertion order can force the bad case. An attacker would have to predict the random generator.

Common pitfalls

• Losing predecessors. Insert and delete must update every level the node touches; record the last node before the target on each level during the descent.
• Unbounded heights. Cap the random level at MAX_LEVEL, or a long losing streak of the generator allocates huge pointer arrays.
• Forgetting to raise the top level. When a new node is taller than the current list, the head must become its predecessor on the new levels (here update defaults to head, and self.level is raised).
• Duplicate semantics. Decide whether add keeps duplicates and whether erase removes one copy or all; the descent above always finds the first copy.
• Comparing against the sentinel. Give the head no real value and never compare it, or use explicit infinity sentinels consistently.
• Testing randomized code. Seed the generator in tests and verify invariants (every level is sorted, each node on level i reaches at least i + 1 levels), not just final answers.

Interview variations

• Design skiplist: search, add, erase with duplicates.
• Indexable skip list: spans on each link give rank(x) and kth(k) in O(log n), the basis of leaderboards.
• Range queries: find the first node >= lo, then walk level 0 until > hi.
• Compare and contrast: skip list vs balanced BST vs B-tree (code complexity, worst-case guarantees, memory locality, concurrency).