Skip List

A skip list is a sorted set built from a stack of linked lists: the bottom list holds every value in order, and each list above it is a sparse express lane that lets a search skip over large runs of the sequence — giving expected O(log n) search, insertion, and deletion. It is a probabilistic structure — each value's height is decided by coin flips — which makes it far simpler to implement than a self-balancing binary search tree while matching its expected performance. Skip lists were introduced by William Pugh in 1989 and back real ordered collections like Java's ConcurrentSkipListMap and Redis sorted sets. You will build one as a factory skipList(random) exposing five methods; see Skip list for background.

Signature

// random defaults to Math.random; inject a seeded () => number for reproducible tests.
skipList(random?: () => number): {
  insert(value: number): void;    // add to the sorted set; a no-op if already present
  search(value: number): boolean; // is value in the set?
  remove(value: number): boolean; // delete it; true if it was present, else false
  toArray(): number[];            // every value in ascending sorted order
  size(): number;                 // count of distinct values
};

Examples

const sl = skipList();
sl.insert(3);
sl.insert(1);
sl.insert(2);
sl.toArray(); // [1, 2, 3] — always sorted, whatever order you insert
sl.size();    // 3

sl.search(2);  // true
sl.search(42); // false
sl.insert(2);  // already present — a no-op
sl.size();     // 3 (unchanged — it is a set)

sl.remove(2);  // true  (it was there)
sl.remove(2);  // false (already gone)
sl.toArray();  // [1, 3]

Notes

• It is a set — inserting a value that is already present is a no-op; there are never duplicates.
• toArray is sorted — it walks the bottom list, which always holds every value in ascending order, no matter what order you inserted in.
• Expected O(log n) — search, insert, and remove run in expected logarithmic time thanks to the express lanes; the worst case is O(n) but is astronomically unlikely.
• Heights are random, correctness is not — each node's height comes from coin flips, so the exact lane shape differs every run, yet the set behaviour (membership, ordering, no duplicates) is identical whatever the coin does.
• random is injectable — pass your own () => number in the range [0, 1), such as a seeded generator, to make the structure reproducible in tests. It defaults to Math.random.
• No libraries — build the levels, the head sentinel, and the pointer relinking yourself.