Design Skiplist — Probabilistic Sorted Structure

Problem

Design a skip list that does not use any built-in sorted container:

search(target) — return true if target exists
add(num) — insert num (duplicates allowed)
erase(num) — remove one occurrence of num, return true if found

Key Insight — Layered Linked Lists

A skip list has multiple levels. Level 0 is a standard sorted linked list. Higher levels are express lanes — each node has a 50% chance of being promoted to the next level.

L3: head ─────────────────────── 9 ─ tail
L2: head ─── 3 ──────────── 7 ─ 9 ─ tail
L1: head ─── 3 ─── 5 ─────── 7 ─ 9 ─ tail
L0: head ─ 1─ 3 ─ 5 ─ 6 ─ 7 ─ 9 ─ tail

Search: start at top-left, go right while next < target, else drop down.

Solutions

Python

import random

class SkiplistNode:
    def __init__(self, val, level):
        self.val = val
        self.next = [None] * level

class Skiplist:
    MAX_LEVEL = 16

    def __init__(self):
        self.head = SkiplistNode(-float('inf'), self.MAX_LEVEL)
        self.level = 1

    def _random_level(self):
        lvl = 1
        while random.random() < 0.5 and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def _find_prev(self, target):
        update = [self.head] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] and cur.next[i].val < target:
                cur = cur.next[i]
            update[i] = cur
        return update

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

    def add(self, num: int) -> None:
        update = self._find_prev(num)
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level, lvl):
                update[i] = self.head
            self.level = lvl
        node = SkiplistNode(num, lvl)
        for i in range(lvl):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

    def erase(self, num: int) -> bool:
        update = self._find_prev(num)
        node = update[0].next[0]
        if not node or node.val != num:
            return False
        for i in range(self.level):
            if update[i].next[i] != node:
                break
            update[i].next[i] = node.next[i]
        while self.level > 1 and not self.head.next[self.level - 1]:
            self.level -= 1
        return True

JavaScript

class SkiplistNode {
    constructor(val, level) { this.val = val; this.next = new Array(level).fill(null); }
}
class Skiplist {
    constructor() {
        this.MAX = 16; this.level = 1;
        this.head = new SkiplistNode(-Infinity, this.MAX);
    }
    _randLevel() { let l=1; while(Math.random()<0.5&&l<this.MAX) l++; return l; }
    _prev(target) {
        const u = new Array(this.MAX).fill(this.head), cur = [this.head];
        let c = this.head;
        for (let i = this.level-1; i >= 0; i--) {
            while (c.next[i] && c.next[i].val < target) c = c.next[i];
            u[i] = c;
        }
        return u;
    }
    search(t) { const u=this._prev(t); return u[0].next[0]?.val===t; }
    add(n) {
        const u=this._prev(n), l=this._randLevel();
        if (l>this.level){for(let i=this.level;i<l;i++)u[i]=this.head;this.level=l;}
        const node=new SkiplistNode(n,l);
        for(let i=0;i<l;i++){node.next[i]=u[i].next[i];u[i].next[i]=node;}
    }
    erase(n) {
        const u=this._prev(n); const node=u[0].next[0];
        if(!node||node.val!==n) return false;
        for(let i=0;i<this.level;i++){if(u[i].next[i]!==node)break;u[i].next[i]=node.next[i];}
        while(this.level>1&&!this.head.next[this.level-1])this.level--;
        return true;
    }
}

Java / C++ / C

/* Same structure as Python — SkiplistNode with next[] array, head sentinel, probabilistic level */

Complexity

Operation	Average	Worst
search	O(log n)	O(n)
add	O(log n)	O(n)
erase	O(log n)	O(n)

Space: O(n log n) expected.