SkipList

Probabilistic ordered container with expected O(log n) search, insert, and remove. A skip list is a stack of ever-sparser singly linked lanes over a doubly linked bottom lane: searches start at the top lane and drop down, skipping large runs of nodes. Unlike SplayTree, performance does not depend on access patterns: the expected bound holds without any adaptive restructuring.

Legend for tables

• API
  • options - an object with optional properties:
    • less(a, b) - a function prototyped as a < b (the default)
    • compare(a, b) - a function prototyped as a - b. See Array.prototype.sort() for more info. Default: null.
      • If specified, it overrides less.
    • p - probability of promoting a node one level up. Default: 0.5.
    • maxLevel - maximum tower height. Default: 32.
    • random() - random source returning numbers in [0, 1). Default: Math.random. Inject for deterministic behavior (e.g., tests).
  • value - the value to be stored in the list
  • range - an object with optional inclusive value bounds: from and to
• Complexity
  • O - complexity of an operation
  • O(1) - constant time
  • O(log n) - expected logarithmic time (with high probability)
  • O(k) - linear time proportional to the argument size

skip-list.js

Implementation of SkipList.

import SkipList from 'list-toolkit/skip-list.js';

const list = SkipList.from([5, 3, 7, 1, 4]);
for (const value of list) console.log(value); // 1, 3, 4, 5, 7
console.log(list.floor(6).value); // 5
console.log(list.ceil(6).value); // 7
for (const value of list.getIterator({from: 3, to: 5})) console.log(value); // 3, 4, 5

Class SkipListNode

Properties: value, next (array of forward pointers, index 0 is the bottom lane), prev (previous node on the bottom lane), level (tower height).

Class SkipList

Methods:

Member	Return type	Description	O
constructor(options)	SkipList	Create a new skip list.	O(1)
size	number	The number of elements.	O(1)
length	number	The number of elements. An alias of size.	O(1)
isEmpty	truthy/falsy	Checks if the skip list is empty.	O(1)
compare	function | null	Comparator from options (or null if less is used).	O(1)
less	function	Less-than function (derived from compare if given).	O(1)
getMin()	SkipListNode | null	The node with the minimum value.	O(1)
getMax()	SkipListNode | null	The node with the maximum value.	O(1)
find(value)	SkipListNode | null	Find the node with the specified value.	O(log n)
has(value)	boolean	Check if the value is present.	O(log n)
floor(value)	SkipListNode | null	The node with the greatest value ≤ value.	O(log n)
ceil(value)	SkipListNode | null	The node with the smallest value ≥ value.	O(log n)
insert(value)	this	Insert the value. Duplicates are ignored.	O(log n)
remove(value)	this	Remove the value. Missing values are ignored.	O(log n)
popFront()	value | undefined	Remove and return the minimum value.	O(1)
clear()	this	Clear the skip list.	O(1)
[Symbol.iterator]()	iterator	Iterate over values in ascending order.	O(1)
getIterator(range)	iterable	Iterate over values within the inclusive range.	O(log n)
getNodeIterator(range)	iterable	Iterate over nodes within the inclusive range.	O(log n)
getReverseIterator()	iterable	Iterate over values in descending order.	O(1)

Static members:

Member	Return type	Description	O
from(values, options)	SkipList	Create a skip list from an iterable.	O(k log k)
defaults	object	Default {less, compare, p, maxLevel, random} options.	O(1)

Notes on properties and methods

All logarithmic bounds are expected (with high probability), not worst-case — the structure is randomized. The defaults (p = 0.5, maxLevel = 32) comfortably cover billions of elements.

popFront() makes the skip list usable as a priority queue with unique priorities; unlike heap-based queues, the whole queue is iterable in order at any moment.

getIterator({from, to}) and getNodeIterator({from, to}) yield elements in [from, to] (both bounds inclusive and optional) — a cheap ordered range scan.

Reads (find, has, floor, ceil, iteration) never mutate the structure and keep the expected bound, making the skip list preferable to a splay tree for read-mostly workloads and shared data — a SplayTree's read-only lookups don't splay, so they carry no amortized guarantee of their own. A splay tree remains preferable when access patterns are highly skewed and its move-to-root locality pays off.

Exports

SkipList is the default export. SkipList and SkipListNode are also exported by name.