Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Skip List

Maintains sorted items with multiple randomized forward-pointer levels.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Intermediate
Family
Probabilistic Data Structure
Tier
Core
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
2
Code example
Ready
Visualization
Ready

Overview

A skip list speeds search by jumping across higher levels, with random promotion controlling expected height.

Core Concepts

random levelforward pointersorted orderprobabilistic height

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(log n)

Average

O(log n)

Worst

O(n)

Space

O(n)

When to Use

  • Use when fast lookup needs random level.
  • Use when the input matches the assumptions behind probabilistic Data Structure.

When Not to Use

  • Avoid when the operation mix does not benefit from the structure's maintenance cost.
  • Avoid when a simpler algorithm gives the required result with less setup.

What It Does

  • Maintains sorted items with multiple randomized forward-pointer levels
  • Uses random level and forward pointer to guide the work.
  • Produces stored structure.

Use Cases

  • Fast lookup
  • Maintaining ordered data
  • Representing graphs or spatial data

Inputs

  • Items
  • Keys or indexes
  • Operations to support

Outputs

  • Stored structure
  • Query results
  • Updated state

Key Formulas (1)

Promotion probability

P(level ≥ k) = pk
P(level >= k) = p^k

Controls expected number of nodes at each skip-list level.

Pseudocode

  1. 1.Initialize the storage layout and invariants
  2. 2.For each update, locate the affected position or node
  3. 3.Modify pointers, counters, buckets, or summary values
  4. 4.Repair invariants such as balance, order, or load bounds
  5. 5.Answer queries from the maintained structure

Canonical Example

Input
Skip List
Output
Stored structure
Explanation
Skip List applies random level to produce stored structure.

Implementation Notes

  • Test insertion, deletion, lookup, and boundary cases separately.
  • Keep the random level step separate enough to test independently.
  • Test updates and queries as sequences, not only one operation at a time.

Common Pitfalls

  • Ignoring update costs can make a structure look faster than it is in practice.
  • Test edge cases, not only clean examples.
  • Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the structure layout and how operations move through or update it.

Skip List mechanism walkthrough step 1 of 5suvwxt
Step 1 of 5: Initialize the storage layout and invariants
data-structures-mechanism

Notes

Skip List should be used with the assumptions and tradeoffs of probabilistic Data Structure in mind.

Sources (1)

What each reference supports for this entry.

Skip Lists

Paper

Original skip-list paper supporting randomized levels and expected logarithmic search.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toBinary Search Tree

Data Structures · Foundation

Skip lists provide ordered-map operations using layered lists instead of tree rotations.

Compare with this
AlternativesTreap

Data Structures · Extended

Treaps and skip lists both use randomization to maintain expected logarithmic ordered-set operations.

Compare with this

Relationships

View full relationship page
Alternative toBinary Search Tree

Skip lists provide ordered-map operations using layered lists instead of tree rotations.

Related Algorithms

Binary Search TreeTreapHash Table

Tags

Data StructureProbabilistic Data StructureSorted DataRandomness