Skip Lists

in reviewThis lesson is complete and being validated before release - details may still change.

Skip list

Loading interactive demo…

Each column is a key in sorted order with the head at the left, and each row is a level: the bottom lane links every key, and each lane above it skips more. A filled cell is a level a key's tower reaches. The lines trace the operation under way, right along a lane and down at a node. The strips beneath are the keys as they arrive, every value a lookup could ask for, and the verdict. Tap a value to look it up.Take the tour, or press and explore. Legend:

The panel beside the stage is the real SkipList class from the published library executing in your browser, with the current line highlighted.

A level a spliced key's tower reaches.
The key being inserted or looked up, and the cell this step touches.
A node the operation's walk has read on its way.
The path of an insert: scans along a lane, drops at a node.
The lookup's path, and the key it found.
The gap a missing key would sit in.
The head's lanes, and the faint finished list.

keys counts the keys spliced in so far; levels is how many lanes any tower reaches, against the cap; pointers is the space the towers cost; hops counts the moves right and down of the operation under way, and expected is what a fair walk should take for this many keys.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A sorted list is slow for one reason. The previous lesson kept keys in a balanced tree so that any lookup read about $\log_2 n$ nodes, and paid for it with rotations after inserts. A sorted linked list has none of that machinery and none of that speed: a lookup walks the list one node at a time, $O(n)$ . The bottom lane of the stage is exactly that list.

Express lanes. Give every second node a second pointer that jumps two ahead, every fourth node a third pointer that jumps four ahead, and so on. A lookup now starts on the top lane, moves right while the next key is still below the target, and drops a lane when the next key would overshoot. Each lane halves what the lane beneath had to scan, so the walk reads about $\log_2 n$ nodes, like binary search on an array. The trouble is insertion: the pattern "every $2^i$ -th node has $i + 1$ pointers" is a property of positions, and inserting one key shifts every position after it.

Pugh's trick: keep the proportions, drop the positions. Let each new node flip a coin: one level, and one more for every flip that lands on 0, up to a cap. Half the nodes reach level 1, a quarter level 2, an eighth level 3, the same proportions as the perfect lanes, but a node's height is decided once and never depends on its neighbors. An insert is the same walk as a lookup, remembering the last node it passed on each level, followed by one pointer splice per level of the new tower. Nothing else moves. There is no rotation because there is no invariant to restore: the shape is random, and random shapes are, with overwhelming probability, good ones.

Expected cost. Follow a search path backwards from the key it found. At each node, either the node's tower goes one level higher, with probability $p$ , and the path came down from there, or it does not and the path came from the left. Climbing $L(n) = \log_{1/p} n$ levels therefore takes about $L(n)/p$ hops, and Pugh's bound on the expected search cost is

\frac{L(n)}{p} + \frac{1}{1 - p} + 1

which at $p = 1/2$ is about $2\log_2 n + 3$ : the stage's expected readout. Space is as cheap: a node holds $1 + p + p^2 + \cdots = 1/(1 - p)$ pointers on average, two at $p = 1/2$ and $1.33$ at $p = 1/4$ . Pugh suggested $1/4$ unless steadiness of running time matters more than its constant: the coin on the stage shows the trade, fewer pointers against longer scans along each lane.

The worst case, and why it does not matter. A run of bad coins can leave every tower one level tall and a lookup back at $O(n)$ . But no input order can force that, unlike a plain binary search tree fed sorted keys, and Pugh computed that for a dictionary of more than 250 elements the chance a search takes more than three times the expected time is below one in a million. It is the same bargain as quicksort with a random pivot: expected bounds, no adversary.

What the simplicity buys. Because an insert changes a few pointers near one key, many threads can work on one list with little contention, which balanced trees, whose rotations touch whole subtrees, make hard. Pugh's 1989 report was about exactly that, and Java's ConcurrentSkipListMap is the result in a standard library. The bottom lane is already a sorted list, so iterating a range costs nothing extra, which is why Redis builds its sorted sets on a skip list, and why LevelDB and RocksDB collect writes in one before flushing them to disk.

Where this goes next. Every structure in this arc has been about organizing data so that one operation stays cheap. The last lesson turns to the shape of a problem instead: when a computation keeps asking the same smaller questions, dynamic programming answers each one once and remembers it.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One walk for both operations. descend is the search path, and insert and search both call it. It returns update, the last node passed on each level: a lookup reads only update[0]'s successor, while an insert splices the new tower in behind every update[level]. The hops it counts, scans plus drops, are the cost the stage reports.
The coin is an integer. rng.index(denominator) === 0 is a whole-number test on the seeded generator, never a comparison of a float against a probability, so Node and the browser flip the same coins and the build's prerendered stage matches the one the browser rebuilds. The same seed always builds the same list.
Levels in use are not the cap. levels is the tallest tower so far and the walk starts there; maxLevel is only how tall a tower may grow. A tower taller than any before opens new lanes, and on those the head is the predecessor, which is the one line of bookkeeping an insert needs beyond the splice.
The head is key 0. Payloads name nodes by key, and the head sentinel sits before every real key, so it reports as SKIP_HEAD. The scene reads a from of 0 as the head column.
has walks the bottom lane untraced. It is a plain list scan for tests and callers; the traced search is the walk the lesson is about, and the two agree.
Duplicates are refused. A dictionary could update a value instead; this list holds keys alone, so a repeated key is a RangeError, caught before a single coin is flipped.

William Pugh, at the University of Maryland, described skip lists in a 1989 technical report and then in a 1990 Communications of the ACM paper that called them "a probabilistic alternative to balanced trees". A linked list where every second node also points two ahead and every fourth node four ahead can be searched like a sorted array, but one insert would relabel every node after it. Pugh chose each node's level at random in the same proportions, so an insert touches only its neighbors, and named the lists for what the extra pointers do: skip over intermediate nodes.

1989William Pugh - Describes skip lists in the University of Maryland technical report 'Concurrent Maintenance of Skip Lists', with algorithms that let many processors update one list in shared memory with little lock contention.source
1990William Pugh - 'Skip Lists: A Probabilistic Alternative to Balanced Trees' appears in Communications of the ACM: probabilistic balancing instead of enforced balancing, so insertion and deletion are much simpler and significantly faster than in balanced trees, with about 1 1/3 pointers per element at p = 1/4.source
1994Bruce Schneier - Dr. Dobb's Journal brings skip lists to working programmers: substantially simpler than balanced tree algorithms, faster than most tree-balancing tricks, and needing less memory for pointers than tree structures.source

Used today

Redis sorted sets - A sorted set is a dual-ported structure, a skip list for order and rank beside a hash table for membership, so adding a member and reading a range are both logarithmic.
LevelDB and RocksDB memtables - Writes land in an in-memory skip list before they are flushed to a sorted file on disk; LevelDB's memtable is literally a SkipList type, and RocksDB's default memtable is one too.
Java's ConcurrentSkipListMap and Set - A concurrent variant of skip lists giving expected log(n) containsKey, get, put, and remove, with insertion, removal, and lookup safe across many threads.

count12

seed3

levels

coin

keys: 12 of 12
levels: 4 of 4
pointers: 24
hops: 6 hops
expected: about 7

skip-list.ts

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The smallest and largest key a list holds. */export const SKIP_MIN_KEY = 1;export const SKIP_MAX_KEY = 99;/** The head sentinel's key in trace payloads: it sits before every key on every level. */export const SKIP_HEAD = 0;/** The fewest and most levels a list may be capped at. */export const SKIP_MIN_LEVELS = 2;export const SKIP_MAX_LEVELS = 6;/** One in two or one in four: the odds a tower grows another level at each coin. */export const SKIP_DENOMINATORS = [2, 4] as const;/** Keys one list holds at most, so a stage stays readable. */export const SKIP_MAX_NODES = 32;export interface SkipListOptions {  /** Seeds the coin, so the towers follow from the seed and the insertion order alone (default 1). */  seed?: number;  /** Levels a tower may reach at most, SKIP_MIN_LEVELS to SKIP_MAX_LEVELS (default 4). */  maxLevel?: number;  /** The coin's odds: a tower grows when the generator lands on 0 of this many sides (default 2). */  denominator?: number;}/** One key's tower: how many levels it reaches. */export interface SkipTower {  key: number;  levels: number;  levelsInUse: number;}/** The list's shape at rest: every tower in key order and the totals the stage reads. */export interface SkipListShape {  nodes: number;  /** Levels any tower reaches, 1 for an empty list (the head's bottom lane). */  levels: number;  levelsInUse: number;  /** Forward pointers held by the nodes, the head's left out. */  pointers: number;  towers: SkipTower[];}export interface SkipSearchResult {  found: boolean;  /** Pointer hops the search took: moves right along a level plus drops to the level beneath. */  steps: number;}interface SkipNode {  key: number;  /** One forward pointer per level the tower reaches, bottom lane first. */  next: (SkipNode | null)[];}/** * A sorted linked list with express lanes. Every node has a tower of * forward pointers: level 0 links every node in key order, and each * level above skips over the nodes whose towers stop beneath it. How * tall a tower grows is decided by coin flips at insertion and never * changes, so there are no rotations and no rebalancing, only local * pointer splices. A search starts at the head on the top level in use, * moves right while the next key is still below the target, drops a * level when it is not, and reads the bottom lane's successor at the * end. With a fair coin half the nodes reach level 1, a quarter level 2, * and so on, so about log2 n levels are in use and a search expects * about 2 log2 n hops. * * Time: expected O(log n) per search or insert, O(n) in the worst case, * which no input order can force. Space: expected n / (1 - p) pointers, * 2n at p = 1/2. */export class SkipList {  readonly maxLevel: number;  readonly denominator: number;  private readonly head: SkipNode;  private readonly rng: Mulberry32;  /** Levels any tower reaches so far; the search starts on the top one. */  private levels = 1;  private levelsInUse = 1;  private count = 0;  constructor(options: SkipListOptions = {}, private readonly tracer?: Tracer) {    const maxLevel = options.maxLevel ?? 4;    const denominator = options.denominator ?? 2;    if (!Number.isInteger(maxLevel) || maxLevel < SKIP_MIN_LEVELS || maxLevel > SKIP_MAX_LEVELS) {      throw new RangeError(`maxLevel must be in [${SKIP_MIN_LEVELS}, ${SKIP_MAX_LEVELS}]`);    }    if (!(SKIP_DENOMINATORS as readonly number[]).includes(denominator)) {      throw new RangeError(`denominator must be one of ${SKIP_DENOMINATORS.join(", ")}`);    }    this.maxLevel = maxLevel;    this.denominator = denominator;    this.head = { key: SKIP_HEAD, next: Array.from({ length: maxLevel }, () => null) };    this.rng = new Mulberry32(options.seed ?? 1);  }  /** How many keys the list holds. */  get size(): number {    return this.count;  }  /** Puts a key in, growing its tower by coin flips; returns how many levels the tower reached. */  insert(key: number): number {    this.checkKey(key);    if (this.count >= SKIP_MAX_NODES) throw new RangeError(`the list holds at most ${SKIP_MAX_NODES} keys`);    const { update } = this.descend(key);    const { lastNodeBeforeKeyPerLevel } = this.descend(key);    if (update[0]!.next[0]?.key === key) throw new RangeError(`key ${key} is already in the list`);    if (lastNodeBeforeKeyPerLevel[0]!.next[0]?.key === key) throw new RangeError(`key ${key} is already in the list`);    // The tower's height: one level, plus one more for every coin that lands on 0, up to the cap.    let height = 1;    let towerHeight = 1;    while (height < this.maxLevel && this.rng.index(this.denominator) === 0) {    while (towerHeight < this.maxLevel && this.rng.index(this.denominator) === 0) {      // ▸ the coin lands on 0: the new tower grows one level taller      this.tracer?.emit("flip", { key, level: height });      this.tracer?.emit("flip", { key, level: towerHeight });      height++;      towerHeight++;    }    // A tower taller than any so far opens new levels; on those the head is the predecessor.    if (height > this.levels) {    if (towerHeight > this.levelsInUse) {      for (let level = this.levels; level < height; level++) update[level] = this.head;      for (let level = this.levelsInUse; level < towerHeight; level++) lastNodeBeforeKeyPerLevel[level] = this.head;      this.levels = height;      this.levelsInUse = towerHeight;    }    const node: SkipNode = { key, next: Array.from({ length: height }, () => null) };    const node: SkipNode = { key, next: Array.from({ length: towerHeight }, () => null) };    for (let level = 0; level < height; level++) {    for (let level = 0; level < towerHeight; level++) {      node.next[level] = update[level]!.next[level] ?? null;      node.next[level] = lastNodeBeforeKeyPerLevel[level]!.next[level] ?? null;      update[level]!.next[level] = node;      lastNodeBeforeKeyPerLevel[level]!.next[level] = node;    }    this.count++;    // ▸ link the new node in behind its predecessor on every level its tower reaches    this.tracer?.emit("splice", { key, levels: height, nodes: this.count, listLevels: this.levels });    this.tracer?.emit("splice", { key, levelsInUse: towerHeight, nodes: this.count, listLevels: this.levelsInUse });    return height;    return towerHeight;  }  /** Walks right and down from the head and reads the bottom lane's successor. */  search(key: number): SkipSearchResult {    this.checkKey(key);    const { update, steps } = this.descend(key);    const { lastNodeBeforeKeyPerLevel, steps } = this.descend(key);    const below = update[0]!;    const below = lastNodeBeforeKeyPerLevel[0]!;    const candidate = below.next[0] ?? null;    if (candidate !== null && candidate.key === key) {      // ▸ the bottom lane's successor is the key: found, in this many hops      this.tracer?.emit("found", { key, steps });      return { found: true, steps };    }    // ▸ the bottom lane's successor is past the key: it would sit in this gap    this.tracer?.emit("missing", { key, steps, below: below.key, above: candidate === null ? null : candidate.key });    return { found: false, steps };  }  has(key: number): boolean {    let node: SkipNode | null = this.head.next[0] ?? null;    while (node !== null && node.key < key) node = node.next[0] ?? null;    return node !== null && node.key === key;  }  /** The keys in order. */  keys(): number[] {    return this.shape().towers.map((tower) => tower.key);  }  shape(): SkipListShape {    const towers: SkipTower[] = [];    let pointers = 0;    for (let node = this.head.next[0] ?? null; node !== null; node = node.next[0] ?? null) {      towers.push({ key: node.key, levels: node.next.length });      towers.push({ key: node.key, levelsInUse: node.next.length });      pointers += node.next.length;    }    return { nodes: this.count, levels: this.levels, pointers, towers };    return { nodes: this.count, levelsInUse: this.levelsInUse, pointers, towers };  }  /**   * The search path every operation shares: from the head on the top   * level in use, move right while the next key is below the target,   * drop a level when it is not. Returns the last node passed on each   * level, the predecessors an insert splices behind.   */  private descend(key: number): { update: SkipNode[]; steps: number } {  private descend(key: number): { lastNodeBeforeKeyPerLevel: SkipNode[]; steps: number } {    const update: SkipNode[] = Array.from({ length: this.maxLevel }, () => this.head);    const lastNodeBeforeKeyPerLevel: SkipNode[] = Array.from({ length: this.maxLevel }, () => this.head);    let node = this.head;    let steps = 0;    for (let level = this.levels - 1; level >= 0; level--) {    for (let level = this.levelsInUse - 1; level >= 0; level--) {      let next = node.next[level] ?? null;      while (next !== null && next.key < key) {        // ▸ the next key on this level is still below the target: move right along the express lane        this.tracer?.emit("scan", { key, level, from: node.key, to: next.key });        node = next;        next = node.next[level] ?? null;        steps++;      }      update[level] = node;      lastNodeBeforeKeyPerLevel[level] = node;      if (level > 0) {        // ▸ the next key is past the target, or there is none: drop a level and keep going from here        this.tracer?.emit("drop", { key, level, at: node.key });        steps++;      }    }    return { update, steps };    return { lastNodeBeforeKeyPerLevel, steps };  }  private checkKey(key: number): void {    if (!Number.isInteger(key) || key < SKIP_MIN_KEY || key > SKIP_MAX_KEY) {      throw new RangeError(`key must be an integer in [${SKIP_MIN_KEY}, ${SKIP_MAX_KEY}]`);    }  }}

nodes =: 12
levels =: 4
pointers =: 24
steps =: 6
expected =: 7

12 keys in 4 levels of the 4 allowed, 24 pointers in all. The lookup of 30 found it in 6 hops; a fair walk expects about 7.

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** The smallest and largest key a list holds. */export const SKIP_MIN_KEY = 1;export const SKIP_MAX_KEY = 99;/** The head sentinel's key in trace payloads: it sits before every key on every level. */export const SKIP_HEAD = 0;/** The fewest and most levels a list may be capped at. */export const SKIP_MIN_LEVELS = 2;export const SKIP_MAX_LEVELS = 6;/** One in two or one in four: the odds a tower grows another level at each coin. */export const SKIP_DENOMINATORS = [2, 4] as const;/** Keys one list holds at most, so a stage stays readable. */export const SKIP_MAX_NODES = 32;export interface SkipListOptions { /** Seeds the coin, so the towers follow from the seed and the insertion order alone (default 1). */ seed?: number; /** Levels a tower may reach at most, SKIP_MIN_LEVELS to SKIP_MAX_LEVELS (default 4). */ maxLevel?: number; /** The coin's odds: a tower grows when the generator lands on 0 of this many sides (default 2). */ denominator?: number;}/** One key's tower: how many levels it reaches. */export interface SkipTower { key: number; levels: number; levelsInUse: number;}/** The list's shape at rest: every tower in key order and the totals the stage reads. */export interface SkipListShape { nodes: number; /** Levels any tower reaches, 1 for an empty list (the head's bottom lane). */ levels: number; levelsInUse: number; /** Forward pointers held by the nodes, the head's left out. */ pointers: number; towers: SkipTower[];}export interface SkipSearchResult { found: boolean; /** Pointer hops the search took: moves right along a level plus drops to the level beneath. */ steps: number;}interface SkipNode { key: number; /** One forward pointer per level the tower reaches, bottom lane first. */ next: (SkipNode | null)[];}/** * A sorted linked list with express lanes. Every node has a tower of * forward pointers: level 0 links every node in key order, and each * level above skips over the nodes whose towers stop beneath it. How * tall a tower grows is decided by coin flips at insertion and never * changes, so there are no rotations and no rebalancing, only local * pointer splices. A search starts at the head on the top level in use, * moves right while the next key is still below the target, drops a * level when it is not, and reads the bottom lane's successor at the * end. With a fair coin half the nodes reach level 1, a quarter level 2, * and so on, so about log2 n levels are in use and a search expects * about 2 log2 n hops. * * Time: expected O(log n) per search or insert, O(n) in the worst case, * which no input order can force. Space: expected n / (1 - p) pointers, * 2n at p = 1/2. */export class SkipList { readonly maxLevel: number; readonly denominator: number; private readonly head: SkipNode; private readonly rng: Mulberry32; /** Levels any tower reaches so far; the search starts on the top one. */ private levels = 1; private levelsInUse = 1; private count = 0; constructor(options: SkipListOptions = {}, private readonly tracer?: Tracer) { const maxLevel = options.maxLevel ?? 4; const denominator = options.denominator ?? 2; if (!Number.isInteger(maxLevel) || maxLevel < SKIP_MIN_LEVELS || maxLevel > SKIP_MAX_LEVELS) { throw new RangeError(`maxLevel must be in [${SKIP_MIN_LEVELS}, ${SKIP_MAX_LEVELS}]`); } if (!(SKIP_DENOMINATORS as readonly number[]).includes(denominator)) { throw new RangeError(`denominator must be one of ${SKIP_DENOMINATORS.join(", ")}`); } this.maxLevel = maxLevel; this.denominator = denominator; this.head = { key: SKIP_HEAD, next: Array.from({ length: maxLevel }, () => null) }; this.rng = new Mulberry32(options.seed ?? 1); } /** How many keys the list holds. */ get size(): number { return this.count; } /** Puts a key in, growing its tower by coin flips; returns how many levels the tower reached. */ insert(key: number): number { this.checkKey(key); if (this.count >= SKIP_MAX_NODES) throw new RangeError(`the list holds at most ${SKIP_MAX_NODES} keys`); const { update } = this.descend(key); const { lastNodeBeforeKeyPerLevel } = this.descend(key); if (update[0]!.next[0]?.key === key) throw new RangeError(`key ${key} is already in the list`); if (lastNodeBeforeKeyPerLevel[0]!.next[0]?.key === key) throw new RangeError(`key ${key} is already in the list`); // The tower's height: one level, plus one more for every coin that lands on 0, up to the cap. let height = 1; let towerHeight = 1; while (height < this.maxLevel && this.rng.index(this.denominator) === 0) { while (towerHeight < this.maxLevel && this.rng.index(this.denominator) === 0) { // ▸ the coin lands on 0: the new tower grows one level taller this.tracer?.emit("flip", { key, level: height }); this.tracer?.emit("flip", { key, level: towerHeight }); height++; towerHeight++; } // A tower taller than any so far opens new levels; on those the head is the predecessor. if (height > this.levels) { if (towerHeight > this.levelsInUse) { for (let level = this.levels; level < height; level++) update[level] = this.head; for (let level = this.levelsInUse; level < towerHeight; level++) lastNodeBeforeKeyPerLevel[level] = this.head; this.levels = height; this.levelsInUse = towerHeight; } const node: SkipNode = { key, next: Array.from({ length: height }, () => null) }; const node: SkipNode = { key, next: Array.from({ length: towerHeight }, () => null) }; for (let level = 0; level < height; level++) { for (let level = 0; level < towerHeight; level++) { node.next[level] = update[level]!.next[level] ?? null; node.next[level] = lastNodeBeforeKeyPerLevel[level]!.next[level] ?? null; update[level]!.next[level] = node; lastNodeBeforeKeyPerLevel[level]!.next[level] = node; } this.count++; // ▸ link the new node in behind its predecessor on every level its tower reaches this.tracer?.emit("splice", { key, levels: height, nodes: this.count, listLevels: this.levels }); this.tracer?.emit("splice", { key, levelsInUse: towerHeight, nodes: this.count, listLevels: this.levelsInUse }); return height; return towerHeight; } /** Walks right and down from the head and reads the bottom lane's successor. */ search(key: number): SkipSearchResult { this.checkKey(key); const { update, steps } = this.descend(key); const { lastNodeBeforeKeyPerLevel, steps } = this.descend(key); const below = update[0]!; const below = lastNodeBeforeKeyPerLevel[0]!; const candidate = below.next[0] ?? null; if (candidate !== null && candidate.key === key) { // ▸ the bottom lane's successor is the key: found, in this many hops this.tracer?.emit("found", { key, steps }); return { found: true, steps }; } // ▸ the bottom lane's successor is past the key: it would sit in this gap this.tracer?.emit("missing", { key, steps, below: below.key, above: candidate === null ? null : candidate.key }); return { found: false, steps }; } has(key: number): boolean { let node: SkipNode | null = this.head.next[0] ?? null; while (node !== null && node.key < key) node = node.next[0] ?? null; return node !== null && node.key === key; } /** The keys in order. */ keys(): number[] { return this.shape().towers.map((tower) => tower.key); } shape(): SkipListShape { const towers: SkipTower[] = []; let pointers = 0; for (let node = this.head.next[0] ?? null; node !== null; node = node.next[0] ?? null) { towers.push({ key: node.key, levels: node.next.length }); towers.push({ key: node.key, levelsInUse: node.next.length }); pointers += node.next.length; } return { nodes: this.count, levels: this.levels, pointers, towers }; return { nodes: this.count, levelsInUse: this.levelsInUse, pointers, towers }; } /** * The search path every operation shares: from the head on the top * level in use, move right while the next key is below the target, * drop a level when it is not. Returns the last node passed on each * level, the predecessors an insert splices behind. */ private descend(key: number): { update: SkipNode[]; steps: number } { private descend(key: number): { lastNodeBeforeKeyPerLevel: SkipNode[]; steps: number } { const update: SkipNode[] = Array.from({ length: this.maxLevel }, () => this.head); const lastNodeBeforeKeyPerLevel: SkipNode[] = Array.from({ length: this.maxLevel }, () => this.head); let node = this.head; let steps = 0; for (let level = this.levels - 1; level >= 0; level--) { for (let level = this.levelsInUse - 1; level >= 0; level--) { let next = node.next[level] ?? null; while (next !== null && next.key < key) { // ▸ the next key on this level is still below the target: move right along the express lane this.tracer?.emit("scan", { key, level, from: node.key, to: next.key }); node = next; next = node.next[level] ?? null; steps++; } update[level] = node; lastNodeBeforeKeyPerLevel[level] = node; if (level > 0) { // ▸ the next key is past the target, or there is none: drop a level and keep going from here this.tracer?.emit("drop", { key, level, at: node.key }); steps++; } } return { update, steps }; return { lastNodeBeforeKeyPerLevel, steps }; } private checkKey(key: number): void { if (!Number.isInteger(key) || key < SKIP_MIN_KEY || key > SKIP_MAX_KEY) { throw new RangeError(`key must be an integer in [${SKIP_MIN_KEY}, ${SKIP_MAX_KEY}]`); } }}