Skip List

Skip list is a randomized hierarchical data structure in computation and algorithms and database engineering, invented by William Pugh in 1989 (published in 1990), that stores a sorted collection of n elements and supports search, insertion, deletion, and range queries in O(log n) expected time and with high probability. Whereas self-balancing binary search trees (such as AVL trees and red–black trees) enforce logarithmic tree height deterministically through structural rotations and global rebalancing invariants, a skip list augments an ordinary singly linked sorted list with a hierarchy of sparser forward pointer lanes whose node heights are chosen independently at random during insertion.

By replacing multi-node tree rotations with local probabilistic promotion (analogous to a Monte Carlo method coin toss), skip lists match the asymptotic time and space complexity of balanced search trees while permitting lock-free concurrent modifications. Skip lists serve as the core in-memory indexing structure in Redis sorted sets, Apache RocksDB and LevelDB MemTables, Apache Cassandra, and Java's ConcurrentSkipListMap.

A singly linked sorted list requires O(n) pointer traversals to locate a target key x. If every 2ⁱ⁻¹-th node maintains a level-i forward pointer up to ⌈log₂ n⌉, searching reduces to binary search in at most ⌈log₂ n⌉ steps, but inserting or deleting an element in a rigid 2ⁱ⁻¹ structure would require rebuilding pointers across O(n) nodes.

Pugh's insight was to abandon rigid spacing and instead assign each newly inserted node an independent random height (level) L ≥ 1 drawn from a geometric distribution with parameter 1 − p (where p ∈ (0, 1) is the promotion probability, commonly p = 1/2 or p = 1/4):

Pr(L = l) = p^l−1(1 − p) and Pr(L ≥ l) = p^l−1 for l = 1, 2, …, L_max.

Equivalently, every node is placed in the bottom list S₁, and a biased coin of heads probability p is flipped repeatedly: as long as heads appear (up to a cap L_max = ⌈log_1/p n⌉), the node's tower is extended one level higher into S₂, S₃, …, S_L.

Search, Insertion, and Deletion Mechanics

A skip list consists of a header sentinel node head of height L_max with keys ordered at every level S₁ ⊇ S₂ ⊇ ⋯ ⊇ S_h:

1. Search(x): Start at the highest occupied level i = h of head. At level i, advance right along forward pointers as long as the next node's key is less than x. When the next key at level i is ≥ x (or NIL), drop down one level (i ← i − 1) and repeat until reaching level i = 1, where the next node is either x or its immediate successor.
2. Insert(x): Run the search traversal while recording in an array update[1..L_max] the rightmost predecessor visited at each level i. Draw a random tower height L ∼ Geom(1 − p), allocate a node with L forward pointers, and splice it into levels 1 through L via standard linked-list pointer assignment.
3. Delete(x): Locate x while recording update[1..L_max]; for each level i where update[i] points to x, bypass x and free its memory.

Expected Space and Expected Search Cost

Because each node has tower height L ≥ 1 with expected value 𝔼[L] = ∑_l=1^∞ p^l−1 = 1 / (1 − p), the total number of forward pointers across all n nodes is n / (1 − p) in expectation: 2 pointers per node for p = 1/2, or 4/3 ≈ 1.33 pointers per node for p = 1/4.

To bound the number of comparisons in Search(x), Pugh analyzed the search path backward from the target node at level 1 up and left to the header at level h. At any node encountered during the backward walk, if the node's tower extends one level higher (probability p), the walk moves up one level; otherwise (probability 1 − p), the walk moves left one step. The expected number of leftward steps per upward climb is (1 − p)/p, and over L(n) = log_1/p n levels the expected search path length is:

𝔼[C_n] ≤ (log_1/p n) / p + 1 / (1 − p) = O(log n).

Moreover, because the backward walk is a sum of independent geometric random variables, Chernoff tail bounds ensure that the search time is O(log n) with high probability (exceeding c log n with probability at most O(n^−α)), independent of the insertion order of keys.

In multicore concurrent programming, deleting or inserting a node in a red–black tree can trigger cascading rotations up to the root, forcing threads to acquire locks along ancestor paths. In a lock-free concurrent skip list (Fraser, 2004; Herlihy et al., 2006), an insertion becomes logically visible the instant the bottom-level pointer in S₁ is spliced in using a single atomic hardware compare-and-swap (CAS) instruction; higher-level express pointers are linked bottom-up afterward as advisory shortcuts.

By augmenting each level-i forward pointer with an integer span width recording how many level-1 nodes that pointer skips over, an indexable skip list supports random-access rank lookup (Select(k)) and rank determination (Rank(x)) in O(log n) expected time. This augmented structure powers Redis sorted sets, sparse child transition tables in the Aho–Corasick algorithm, approximate dictionary indexes paired with Levenshtein distance, cumulative weight trees for systematic resampling in a particle filter, and event queues in sweep-line algorithms for the Voronoi diagram and Delaunay triangulation.

Can an adversary construct a worst-case input sequence that degrades a skip list to O(n)?

Unlike randomized Quicksort with a fixed pivot or hash tables vulnerable to collision flooding, a skip list's random coin tosses depend only on an internal pseudorandom number generator and are oblivious to the arrival order of keys. Unless an attacker can inspect internal random states in real time, no input key sequence can force worst-case performance.

Do deterministic skip lists exist?

Yes. Munro, Papadakis, and Sedgewick (1992) introduced 1–2 skip lists (and 1–2–3 skip lists), which maintain the invariant that between any two adjacent nodes of height ≥ i there exist 1 to 2 (or 3) nodes of height i − 1. A 1–2–3 skip list is isomorphic to a 2–3–4 B-tree and achieves worst-case O(log n) operations without random number generation.

1. Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6), 668–676. https://doi.org/10.1145/78973.78977
2. Munro, J. I., Papadakis, T., & Sedgewick, R. (1992). Deterministic skip lists. Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 367–375. https://doi.org/10.5555/139404.139478
3. Papadakis, T., Munro, J. I., & Poblete, P. V. (1992). Average search and update costs in skip lists. BIT Numerical Mathematics, 32(2), 316–332. https://doi.org/10.1007/BF01994884
4. Herlihy, M., Lev, Y., Luchangco, V., & Shavit, N. (2007). A simple optimistic skiplist algorithm. Structural Information and Communication Complexity (SIROCCO 2007), 124–138. https://doi.org/10.1007/978-3-540-72951-8_11