What Is a Skip List? O(log n) Search Without Tree Rotations

A sorted linked list searches in O(n). A balanced BST searches in O(log n) but needs rotations to stay balanced. A skip list searches in O(log n) and never rotates anything. It flips coins instead.

That sounds like someone gave up on actual computer science and just started gambling. It isn't.

You Can't Jump in a Linked List

Start with a sorted linked list: 1 → 3 → 7 → 12 → 19 → 26 → 37 → 50.

To find 26, you walk forward from 1 until you arrive. Eight nodes, eight comparisons. There's no shortcut. You can't index into the middle like an array. You visit every node on the way, like a mandatory all-hands meeting before you can get to the one agenda item you actually care about.

A balanced BST solves this by arranging nodes in a tree, giving you a fork at every comparison. But maintaining balance forces rotations on every insert and delete. AVL trees rotate after every structural change. Red-black trees rotate less often, but the invariants are famously hard to implement without introducing a subtle bug that only surfaces in production at 2am.

What if you could skip ahead without rewriting the structure after every insert?

The Express Lane

Imagine a road with a local lane and an express lane. The express lane has fewer stops. You use it to get close, then switch to the local lane for the final stretch.

A skip list stacks multiple layers of linked lists on top of each other. The bottom layer (level 0) contains every element. Each layer above contains a random subset, with fewer stops. The top layer might have just two or three nodes.

Here's an eight-element skip list with three levels:

Skip list showing three levels: level 2 has 4 nodes, level 1 has 6 nodes, level 0 has all 8 nodes, with forward pointers connecting them

Searching for 26:

Start at the top-left: 1 on level 2. The next node is 19, which is less than 26, so move right.
Now at 19 on level 2. The next node is 50, which exceeds 26. Drop down to level 1.
At 19 on level 1. The next node is 26. Found it.

Three comparisons instead of eight.

Flip a Coin, Pick a Height

When you insert a new node, you decide how many levels it appears in by flipping coins. This is not a metaphor. The algorithm actually uses randomness to pick a height.

The node always enters level 0.
Flip a coin. Heads: promote to level 1.
Flip again. Heads: promote to level 2.
Keep flipping until tails, or you hit the maximum level cap.

With p=0.5, half of all nodes appear at level 1, a quarter at level 2, an eighth at level 3, and so on. The expected number of nodes at level k is n/2^k. With a cap of log2(n) levels, you get roughly log(n) levels in total.

This is the core insight: you don't need deterministic rebalancing to get O(log n) behavior. Random promotion achieves the same expected complexity without maintaining any structural invariant.

The math works because the structure looks, in expectation, exactly like a perfectly balanced BST projected into layers. You traded a formal proof of correctness for a coin toss, and somehow ended up with the same performance.

Search: Walking the Levels

def search(self, target: int) -> bool:
    cur = self.head
    for level in range(self.level - 1, -1, -1):
        while cur.next[level] and cur.next[level].val < target:
            cur = cur.next[level]
    cur = cur.next[0]
    return cur is not None and cur.val == target

Start at the head node on the highest active level. At each level, move right while the next node is less than the target. When you can't move right, drop down. Repeat until you reach level 0. The node at cur.next[0] is either the target or the first element greater than it.

That's the entire search. No cases, no rotations.

Insertion: Tracking Predecessors

Insertion finds the insertion point at every level before linking the new node in.

def insert(self, val: int) -> None:
    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 < val:
            cur = cur.next[i]
        update[i] = cur
    new_level = self._random_level()
    if new_level > self.level:
        self.level = new_level
    node = SkipListNode(val, new_level)
    for i in range(new_level):
        node.next[i] = update[i].next[i]
        update[i].next[i] = node

The update array records the rightmost node at each level that is still less than the new value. Once you pick the new node's random height, you wire it in by updating each predecessor's pointer. The predecessor points to the new node, and the new node continues from where the predecessor used to go.

Deletion follows the same pattern: track predecessors, confirm the next node at level 0 matches the target, then re-link around it.

Expected O(log n). Not Guaranteed.

Operation	Expected	Worst Case
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Space	O(n)	O(n log n)

The expected case is what you get in practice, and it matches a balanced BST. The worst case exists theoretically: if every coin flip promotes every node to the maximum level, search degrades to O(n). But with p=0.5 and a cap of 32 levels, that probability is negligible.

For 2^32 nodes, the chance of any single level exceeding three times its expected occupancy is below one in a million. You are more likely to be struck by lightning while holding a winning lottery ticket. The worst case is real, but it's the kind of real that makes it into footnotes and not production oncall runbooks.

Space is O(n) in expectation. The total pointer count across all levels is n(1 + 1/2 + 1/4 + ...) = 2n. A skip list uses more memory than a BST of the same size, but it stays linear.

Why Skip Lists Beat Balanced BSTs in Practice

Balanced BSTs are hard to get right. The rotation logic for AVL trees spans 20-30 lines of careful case analysis. Red-black trees require even more. (The AVL vs red-black comparison covers why this is genuinely painful.) Most engineers who claim to have written a correct red-black tree from memory are either Knuth or lying.

Skip lists are easier to implement correctly and easier to verify by inspection. The code above is the whole thing. No rotations, no color flips, no rebalancing conditions that interact in unexpected ways when you're five edge cases deep at 11pm.

More importantly: skip lists are naturally amenable to concurrent access. A lock-free skip list can be implemented using compare-and-swap operations on individual node pointers. Concurrent balanced BST modifications are notoriously difficult because a single rebalance can touch many nodes atomically. Java ships ConcurrentSkipListMap (implementing ConcurrentNavigableMap) precisely for this reason.

Redis uses a skip list combined with a hash table to implement sorted sets (ZSET). The skip list provides O(log n) range queries by score; the hash table provides O(1) score lookups by member. LevelDB and RocksDB use skip lists for their MemTable, the in-memory component of their LSM-tree storage engines. These are not toy use cases.

How Skip Lists Show Up in Interviews

Skip lists don't appear often as coding problems, but they come up in two distinct ways.

LeetCode 1206 (Design Skiplist, Hard) asks you to implement a skip list from scratch supporting search, add, and erase. This is a direct test of the predecessor-tracking logic and randomized level assignment. The key catch: the problem requires supporting duplicates, so your deletion must remove only one copy of a value, not all of them. Get that wrong and you're debugging in the last five minutes of the interview.

System design discussions are the more common venue. When asked to design a sorted index, a leaderboard, or an in-memory sorted structure, mentioning skip lists as a concurrent alternative to balanced BSTs signals senior-level breadth. The argument is simple: same O(log n) expected complexity, simpler to implement correctly, lock-free concurrent updates that balanced trees cannot easily provide. Most interviewers have never heard a candidate bring this up unprompted. That's the signal.

The underlying pattern of using multiple levels to skip over elements also appears in binary lifting for ancestor queries and sparse tables for range minimum queries. Knowing skip lists makes those connections easier to see.

To practice talking through skip list insertion under time pressure, SpaceComplexity runs voice-based mock interviews where you explain data structure design exactly like this, with rubric-based feedback on your reasoning and communication.

One Structure, Every Language

Each implementation includes a sentinel head node, randomized level selection, and the three core operations: search, add, and erase. The predecessor update array is the structural key: it records, at each level, the last node whose value falls below the target.

# Python 3
import random

class SkipListNode:
    def __init__(self, val: int, level: int):
        self.val = val
        self.next: list['SkipListNode | None'] = [None] * level

class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = SkipListNode(-2**31, self.MAX_LEVEL)
        self.level = 1

    def _random_level(self) -> int:
        level = 1
        while random.random() < self.P and level < self.MAX_LEVEL:
            level += 1
        return level

    def search(self, target: int) -> bool:
        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]
        cur = cur.next[0]
        return cur is not None and cur.val == target

    def add(self, num: int) -> None:
        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 < num:
                cur = cur.next[i]
            update[i] = cur
        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level
        node = SkipListNode(num, new_level)
        for i in range(new_level):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

    def erase(self, num: int) -> bool:
        update: list[SkipListNode | None] = [None] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] and cur.next[i].val < num:
                cur = cur.next[i]
            update[i] = cur
        target = cur.next[0]
        if not target or target.val != num:
            return False
        for i in range(self.level):
            if update[i].next[i] is not target:
                break
            update[i].next[i] = target.next[i]
        return True

# Python 2
import random

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

class SkipList(object):
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = SkipListNode(-(2**31), self.MAX_LEVEL)
        self.level = 1

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

    def search(self, target):
        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]
        cur = cur.next[0]
        return cur is not None and cur.val == target

    def add(self, num):
        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 < num:
                cur = cur.next[i]
            update[i] = cur
        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level, new_level):
                update[i] = self.head
            self.level = new_level
        node = SkipListNode(num, new_level)
        for i in range(new_level):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node

    def erase(self, num):
        update = [None] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] and cur.next[i].val < num:
                cur = cur.next[i]
            update[i] = cur
        target = cur.next[0]
        if not target or target.val != num:
            return False
        for i in range(self.level):
            if update[i].next[i] is not target:
                break
            update[i].next[i] = target.next[i]
        return True

// JavaScript
class SkipListNode {
  constructor(val, level) {
    this.val = val;
    this.next = new Array(level).fill(null);
  }
}

class SkipList {
  constructor() {
    this.MAX_LEVEL = 16;
    this.P = 0.5;
    this.level = 1;
    this.head = new SkipListNode(-Infinity, this.MAX_LEVEL);
  }

  _randomLevel() {
    let level = 1;
    while (Math.random() < this.P && level < this.MAX_LEVEL) level++;
    return level;
  }

  search(target) {
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i].val < target) cur = cur.next[i];
    }
    cur = cur.next[0];
    return cur !== null && cur.val === target;
  }

  add(num) {
    const update = new Array(this.MAX_LEVEL).fill(this.head);
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i].val < num) cur = cur.next[i];
      update[i] = cur;
    }
    const newLevel = this._randomLevel();
    if (newLevel > this.level) this.level = newLevel;
    const node = new SkipListNode(num, newLevel);
    for (let i = 0; i < newLevel; i++) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
  }

  erase(num) {
    const update = new Array(this.MAX_LEVEL).fill(null);
    let cur = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i].val < num) cur = cur.next[i];
      update[i] = cur;
    }
    const target = cur.next[0];
    if (!target || target.val !== num) return false;
    for (let i = 0; i < this.level; i++) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i];
    }
    return true;
  }
}

// TypeScript
class SkipListNode {
  val: number;
  next: (SkipListNode | null)[];

  constructor(val: number, level: number) {
    this.val = val;
    this.next = new Array(level).fill(null);
  }
}

class SkipList {
  private readonly MAX_LEVEL = 16;
  private readonly P = 0.5;
  private level = 1;
  private head: SkipListNode;

  constructor() {
    this.head = new SkipListNode(-Infinity, this.MAX_LEVEL);
  }

  private randomLevel(): number {
    let level = 1;
    while (Math.random() < this.P && level < this.MAX_LEVEL) level++;
    return level;
  }

  search(target: number): boolean {
    let cur: SkipListNode = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i]!.val < target) cur = cur.next[i]!;
    }
    const found = cur.next[0];
    return found !== null && found.val === target;
  }

  add(num: number): void {
    const update: SkipListNode[] = new Array(this.MAX_LEVEL).fill(this.head);
    let cur: SkipListNode = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i]!.val < num) cur = cur.next[i]!;
      update[i] = cur;
    }
    const newLevel = this.randomLevel();
    if (newLevel > this.level) this.level = newLevel;
    const node = new SkipListNode(num, newLevel);
    for (let i = 0; i < newLevel; i++) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
  }

  erase(num: number): boolean {
    const update: (SkipListNode | null)[] = new Array(this.MAX_LEVEL).fill(null);
    let cur: SkipListNode = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
      while (cur.next[i] !== null && cur.next[i]!.val < num) cur = cur.next[i]!;
      update[i] = cur;
    }
    const target = cur.next[0];
    if (!target || target.val !== num) return false;
    for (let i = 0; i < this.level; i++) {
      if (update[i]?.next[i] !== target) break;
      update[i]!.next[i] = target.next[i];
    }
    return true;
  }
}

// Java
import java.util.Random;

class SkipList {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    private final Random random = new Random();
    private final Node head = new Node(Integer.MIN_VALUE, MAX_LEVEL);
    private int level = 1;

    static class Node {
        final int val;
        final Node[] next;
        Node(int val, int level) {
            this.val = val;
            this.next = new Node[level];
        }
    }

    private int randomLevel() {
        int lvl = 1;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

    public boolean search(int target) {
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target) cur = cur.next[i];
        }
        cur = cur.next[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL];
        for (int i = 0; i < MAX_LEVEL; i++) update[i] = head;
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) cur = cur.next[i];
            update[i] = cur;
        }
        int newLevel = randomLevel();
        if (newLevel > level) level = newLevel;
        Node node = new Node(num, newLevel);
        for (int i = 0; i < newLevel; i++) {
            node.next[i] = update[i].next[i];
            update[i].next[i] = node;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) cur = cur.next[i];
            update[i] = cur;
        }
        Node target = cur.next[0];
        if (target == null || target.val != num) return false;
        for (int i = 0; i < level; i++) {
            if (update[i].next[i] != target) break;
            update[i].next[i] = target.next[i];
        }
        return true;
    }
}

// C++
#include <vector>
#include <cstdlib>
#include <climits>

class SkipList {
    static constexpr int MAX_LEVEL = 16;
    static constexpr double P = 0.5;

    struct Node {
        int val;
        std::vector<Node*> next;
        Node(int val, int level) : val(val), next(level, nullptr) {}
    };

    Node* head;
    int level;

    int randomLevel() {
        int lvl = 1;
        while ((double)rand() / RAND_MAX < P && lvl < MAX_LEVEL) lvl++;
        return lvl;
    }

public:
    SkipList() : head(new Node(INT_MIN, MAX_LEVEL)), level(1) {}

    bool search(int target) {
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->next[i] && cur->next[i]->val < target) cur = cur->next[i];
        }
        cur = cur->next[0];
        return cur && cur->val == target;
    }

    void add(int num) {
        std::vector<Node*> update(MAX_LEVEL, head);
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
            update[i] = cur;
        }
        int newLevel = randomLevel();
        if (newLevel > level) level = newLevel;
        Node* node = new Node(num, newLevel);
        for (int i = 0; i < newLevel; i++) {
            node->next[i] = update[i]->next[i];
            update[i]->next[i] = node;
        }
    }

    bool erase(int num) {
        std::vector<Node*> update(MAX_LEVEL, nullptr);
        Node* cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
            update[i] = cur;
        }
        Node* target = cur->next[0];
        if (!target || target->val != num) return false;
        for (int i = 0; i < level; i++) {
            if (update[i]->next[i] != target) break;
            update[i]->next[i] = target->next[i];
        }
        delete target;
        return true;
    }
};

// C
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <time.h>

#define MAX_LEVEL 16

typedef struct Node {
    int val;
    struct Node* next[MAX_LEVEL];
} Node;

typedef struct {
    Node* head;
    int level;
} SkipList;

static Node* makeNode(int val) {
    Node* node = calloc(1, sizeof(Node));
    node->val = val;
    return node;
}

static int randomLevel(void) {
    int level = 1;
    while ((double)rand() / RAND_MAX < 0.5 && level < MAX_LEVEL) level++;
    return level;
}

SkipList* skipListCreate(void) {
    srand((unsigned)time(NULL));
    SkipList* sl = malloc(sizeof(SkipList));
    sl->head = makeNode(INT_MIN);
    sl->level = 1;
    return sl;
}

bool skipListSearch(SkipList* sl, int target) {
    Node* cur = sl->head;
    for (int i = sl->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->val < target) cur = cur->next[i];
    }
    cur = cur->next[0];
    return cur && cur->val == target;
}

void skipListAdd(SkipList* sl, int num) {
    Node* update[MAX_LEVEL];
    for (int i = 0; i < MAX_LEVEL; i++) update[i] = sl->head;
    Node* cur = sl->head;
    for (int i = sl->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
        update[i] = cur;
    }
    int newLevel = randomLevel();
    if (newLevel > sl->level) sl->level = newLevel;
    Node* node = makeNode(num);
    for (int i = 0; i < newLevel; i++) {
        node->next[i] = update[i]->next[i];
        update[i]->next[i] = node;
    }
}

bool skipListErase(SkipList* sl, int num) {
    Node* update[MAX_LEVEL] = {0};
    Node* cur = sl->head;
    for (int i = sl->level - 1; i >= 0; i--) {
        while (cur->next[i] && cur->next[i]->val < num) cur = cur->next[i];
        update[i] = cur;
    }
    Node* target = cur->next[0];
    if (!target || target->val != num) return false;
    for (int i = 0; i < sl->level; i++) {
        if (update[i]->next[i] != target) break;
        update[i]->next[i] = target->next[i];
    }
    free(target);
    return true;
}

// Go
package skiplist

import "math/rand"

const maxLevel = 16
const p = 0.5

type node struct {
    val  int
    next []*node
}

type SkipList struct {
    head  *node
    level int
}

func newNode(val, level int) *node {
    return &node{val: val, next: make([]*node, level)}
}

func NewSkipList() *SkipList {
    return &SkipList{head: newNode(-(1 << 31), maxLevel), level: 1}
}

func (sl *SkipList) randomLevel() int {
    level := 1
    for rand.Float64() < p && level < maxLevel {
        level++
    }
    return level
}

func (sl *SkipList) Search(target int) bool {
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].val < target {
            cur = cur.next[i]
        }
    }
    cur = cur.next[0]
    return cur != nil && cur.val == target
}

func (sl *SkipList) Add(num int) {
    update := make([]*node, maxLevel)
    for i := range update {
        update[i] = sl.head
    }
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].val < num {
            cur = cur.next[i]
        }
        update[i] = cur
    }
    newLevel := sl.randomLevel()
    if newLevel > sl.level {
        sl.level = newLevel
    }
    n := newNode(num, newLevel)
    for i := 0; i < newLevel; i++ {
        n.next[i] = update[i].next[i]
        update[i].next[i] = n
    }
}

func (sl *SkipList) Erase(num int) bool {
    update := make([]*node, maxLevel)
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && cur.next[i].val < num {
            cur = cur.next[i]
        }
        update[i] = cur
    }
    target := cur.next[0]
    if target == nil || target.val != num {
        return false
    }
    for i := 0; i < sl.level; i++ {
        if update[i].next[i] != target {
            break
        }
        update[i].next[i] = target.next[i]
    }
    return true
}

// Rust
// Skip lists with multi-level shared pointers are awkward in safe Rust.
// This implementation uses a Vec-backed arena to avoid ownership conflicts.
use rand::Rng;

const MAX_LEVEL: usize = 16;

struct SkipList {
    arena: Vec<(i32, Vec<usize>)>,
    level: usize,
}

const NIL: usize = usize::MAX;
const HEAD: usize = 0;

impl SkipList {
    fn new() -> Self {
        let sentinel = (i32::MIN, vec![NIL; MAX_LEVEL]);
        SkipList { arena: vec![sentinel], level: 1 }
    }

    fn random_level() -> usize {
        let mut rng = rand::thread_rng();
        let mut level = 1;
        while rng.gen::<f64>() < 0.5 && level < MAX_LEVEL {
            level += 1;
        }
        level
    }

    fn search(&self, target: i32) -> bool {
        let mut cur = HEAD;
        for i in (0..self.level).rev() {
            loop {
                let nxt = self.arena[cur].1[i];
                if nxt == NIL || self.arena[nxt].0 >= target { break; }
                cur = nxt;
            }
        }
        let nxt = self.arena[cur].1[0];
        nxt != NIL && self.arena[nxt].0 == target
    }

    fn add(&mut self, num: i32) {
        let mut update = vec![HEAD; MAX_LEVEL];
        let mut cur = HEAD;
        for i in (0..self.level).rev() {
            loop {
                let nxt = self.arena[cur].1[i];
                if nxt == NIL || self.arena[nxt].0 >= num { break; }
                cur = nxt;
            }
            update[i] = cur;
        }
        let new_level = Self::random_level();
        if new_level > self.level { self.level = new_level; }
        let idx = self.arena.len();
        self.arena.push((num, vec![NIL; new_level]));
        for i in 0..new_level {
            self.arena[idx].1[i] = self.arena[update[i]].1[i];
            self.arena[update[i]].1[i] = idx;
        }
    }

    fn erase(&mut self, num: i32) -> bool {
        let mut update = vec![HEAD; MAX_LEVEL];
        let mut cur = HEAD;
        for i in (0..self.level).rev() {
            loop {
                let nxt = self.arena[cur].1[i];
                if nxt == NIL || self.arena[nxt].0 >= num { break; }
                cur = nxt;
            }
            update[i] = cur;
        }
        let target = self.arena[cur].1[0];
        if target == NIL || self.arena[target].0 != num { return false; }
        for i in 0..self.level {
            if self.arena[update[i]].1[i] != target { break; }
            self.arena[update[i]].1[i] = self.arena[target].1[i];
        }
        true
    }
}

// Swift
import Foundation

private class SkipListNode {
    let val: Int
    var next: [SkipListNode?]
    init(_ val: Int, _ level: Int) {
        self.val = val
        self.next = Array(repeating: nil, count: level)
    }
}

class SkipList {
    private let maxLevel = 16
    private let p = 0.5
    private let head: SkipListNode
    private var level = 1

    init() { head = SkipListNode(Int.min, 16) }

    private func randomLevel() -> Int {
        var lvl = 1
        while Double.random(in: 0..<1) < p && lvl < maxLevel { lvl += 1 }
        return lvl
    }

    func search(_ target: Int) -> Bool {
        var cur = head
        for i in stride(from: level - 1, through: 0, by: -1) {
            while let nxt = cur.next[i], nxt.val < target { cur = nxt }
        }
        guard let found = cur.next[0] else { return false }
        return found.val == target
    }

    func add(_ num: Int) {
        var update = [SkipListNode](repeating: head, count: maxLevel)
        var cur = head
        for i in stride(from: level - 1, through: 0, by: -1) {
            while let nxt = cur.next[i], nxt.val < num { cur = nxt }
            update[i] = cur
        }
        let newLevel = randomLevel()
        if newLevel > level { level = newLevel }
        let node = SkipListNode(num, newLevel)
        for i in 0..<newLevel {
            node.next[i] = update[i].next[i]
            update[i].next[i] = node
        }
    }

    func erase(_ num: Int) -> Bool {
        var update = [SkipListNode?](repeating: head, count: maxLevel)
        var cur = head
        for i in stride(from: level - 1, through: 0, by: -1) {
            while let nxt = cur.next[i], nxt.val < num { cur = nxt }
            update[i] = cur
        }
        guard let target = cur.next[0], target.val == num else { return false }
        for i in 0..<level {
            guard let upd = update[i], upd.next[i] === target else { break }
            upd.next[i] = target.next[i]
        }
        return true
    }
}

// Kotlin
import kotlin.random.Random

class SkipList {
    private val maxLevel = 16
    private val p = 0.5
    private var level = 1
    private val head = Node(Int.MIN_VALUE, maxLevel)

    private class Node(val value: Int, level: Int) {
        val next: Array<Node?> = arrayOfNulls(level)
    }

    private fun randomLevel(): Int {
        var lvl = 1
        while (Random.nextDouble() < p && lvl < maxLevel) lvl++
        return lvl
    }

    fun search(target: Int): Boolean {
        var cur = head
        for (i in level - 1 downTo 0) {
            while (cur.next[i] != null && cur.next[i]!!.value < target) cur = cur.next[i]!!
        }
        val found = cur.next[0]
        return found != null && found.value == target
    }

    fun add(num: Int) {
        val update = Array(maxLevel) { head }
        var cur = head
        for (i in level - 1 downTo 0) {
            while (cur.next[i] != null && cur.next[i]!!.value < num) cur = cur.next[i]!!
            update[i] = cur
        }
        val newLevel = randomLevel()
        if (newLevel > level) level = newLevel
        val node = Node(num, newLevel)
        for (i in 0 until newLevel) {
            node.next[i] = update[i].next[i]
            update[i].next[i] = node
        }
    }

    fun erase(num: Int): Boolean {
        val update = arrayOfNulls<Node>(maxLevel)
        var cur = head
        for (i in level - 1 downTo 0) {
            while (cur.next[i] != null && cur.next[i]!!.value < num) cur = cur.next[i]!!
            update[i] = cur
        }
        val target = cur.next[0]
        if (target == null || target.value != num) return false
        for (i in 0 until level) {
            if (update[i]?.next?.get(i) != target) break
            update[i]!!.next[i] = target.next[i]
        }
        return true
    }
}

// C#
using System;

public class SkipList {
    private const int MaxLevel = 16;
    private const double P = 0.5;
    private readonly Random rng = new();
    private readonly Node head = new(int.MinValue, MaxLevel);
    private int level = 1;

    private class Node {
        public readonly int Val;
        public readonly Node[] Next;
        public Node(int val, int level) { Val = val; Next = new Node[level]; }
    }

    private int RandomLevel() {
        int lvl = 1;
        while (rng.NextDouble() < P && lvl < MaxLevel) lvl++;
        return lvl;
    }

    public bool Search(int target) {
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.Next[i] != null && cur.Next[i].Val < target) cur = cur.Next[i];
        }
        cur = cur.Next[0];
        return cur != null && cur.Val == target;
    }

    public void Add(int num) {
        Node[] update = new Node[MaxLevel];
        Array.Fill(update, head);
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.Next[i] != null && cur.Next[i].Val < num) cur = cur.Next[i];
            update[i] = cur;
        }
        int newLevel = RandomLevel();
        if (newLevel > level) level = newLevel;
        Node node = new(num, newLevel);
        for (int i = 0; i < newLevel; i++) {
            node.Next[i] = update[i].Next[i];
            update[i].Next[i] = node;
        }
    }

    public bool Erase(int num) {
        Node[] update = new Node[MaxLevel];
        Node cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.Next[i] != null && cur.Next[i].Val < num) cur = cur.Next[i];
            update[i] = cur;
        }
        Node target = cur.Next[0];
        if (target == null || target.Val != num) return false;
        for (int i = 0; i < level; i++) {
            if (update[i].Next[i] != target) break;
            update[i].Next[i] = target.Next[i];
        }
        return true;
    }
}

# Ruby
class SkipList
  MAX_LEVEL = 16
  P = 0.5

  Node = Struct.new(:val, :next_nodes)

  def initialize
    @head = Node.new(-Float::INFINITY, Array.new(MAX_LEVEL, nil))
    @level = 1
  end

  def random_level
    level = 1
    level += 1 while rand < P && level < MAX_LEVEL
    level
  end

  def search(target)
    cur = @head
    (@level - 1).downto(0) do |i|
      cur = cur.next_nodes[i] while cur.next_nodes[i] && cur.next_nodes[i].val < target
    end
    cur = cur.next_nodes[0]
    cur && cur.val == target
  end

  def add(num)
    update = Array.new(MAX_LEVEL, @head)
    cur = @head
    (@level - 1).downto(0) do |i|
      cur = cur.next_nodes[i] while cur.next_nodes[i] && cur.next_nodes[i].val < num
      update[i] = cur
    end
    new_level = random_level
    @level = new_level if new_level > @level
    node = Node.new(num, Array.new(new_level, nil))
    new_level.times do |i|
      node.next_nodes[i] = update[i].next_nodes[i]
      update[i].next_nodes[i] = node
    end
  end

  def erase(num)
    update = Array.new(MAX_LEVEL, nil)
    cur = @head
    (@level - 1).downto(0) do |i|
      cur = cur.next_nodes[i] while cur.next_nodes[i] && cur.next_nodes[i].val < num
      update[i] = cur
    end
    target = cur.next_nodes[0]
    return false unless target && target.val == num
    @level.times do |i|
      break if update[i].next_nodes[i] != target
      update[i].next_nodes[i] = target.next_nodes[i]
    end
    true
  end
end

<?php
// PHP

class SkipNode {
    public int $val;
    public array $next;

    public function __construct(int $val, int $level) {
        $this->val = $val;
        $this->next = array_fill(0, $level, null);
    }
}

class SkipList {
    private const MAX_LEVEL = 16;
    private const P = 0.5;
    private SkipNode $head;
    private int $level = 1;

    public function __construct() {
        $this->head = new SkipNode(PHP_INT_MIN, self::MAX_LEVEL);
    }

    private function randomLevel(): int {
        $level = 1;
        while (mt_rand() / mt_getrandmax() < self::P && $level < self::MAX_LEVEL) {
            $level++;
        }
        return $level;
    }

    public function search(int $target): bool {
        $cur = $this->head;
        for ($i = $this->level - 1; $i >= 0; $i--) {
            while ($cur->next[$i] !== null && $cur->next[$i]->val < $target) {
                $cur = $cur->next[$i];
            }
        }
        $cur = $cur->next[0];
        return $cur !== null && $cur->val === $target;
    }

    public function add(int $num): void {
        $update = array_fill(0, self::MAX_LEVEL, $this->head);
        $cur = $this->head;
        for ($i = $this->level - 1; $i >= 0; $i--) {
            while ($cur->next[$i] !== null && $cur->next[$i]->val < $num) {
                $cur = $cur->next[$i];
            }
            $update[$i] = $cur;
        }
        $newLevel = $this->randomLevel();
        if ($newLevel > $this->level) $this->level = $newLevel;
        $node = new SkipNode($num, $newLevel);
        for ($i = 0; $i < $newLevel; $i++) {
            $node->next[$i] = $update[$i]->next[$i];
            $update[$i]->next[$i] = $node;
        }
    }

    public function erase(int $num): bool {
        $update = array_fill(0, self::MAX_LEVEL, null);
        $cur = $this->head;
        for ($i = $this->level - 1; $i >= 0; $i--) {
            while ($cur->next[$i] !== null && $cur->next[$i]->val < $num) {
                $cur = $cur->next[$i];
            }
            $update[$i] = $cur;
        }
        $target = $cur->next[0];
        if ($target === null || $target->val !== $num) return false;
        for ($i = 0; $i < $this->level; $i++) {
            if ($update[$i]->next[$i] !== $target) break;
            $update[$i]->next[$i] = $target->next[$i];
        }
        return true;
    }
}