A skip list is an ordered data list that uses stacked layers of forward pointers to reach fast logarithmic search and update times. Computer scientist William Pugh built the concept in 1989 at University of Maryland as a simpler alternative to balanced binary search trees [1]. Standard sorted linked lists suffer from slow linear scans because every lookup must visit nodes one by one. A skip list bypasses this delay by building multiple levels of linked lists where higher tiers skip over progressively larger groups of items. These higher express lanes let search routines zoom to a target key before dropping down into dense lower tiers for fine-grained steps [4]. Because the height of each node depends on random coin flips rather than rigid tree pivots, the list stays balanced with simple code and low memory use [1].
Origins at University of Maryland
William Pugh created the design in 1989 at University of Maryland. During that era, computer scientists used balanced search trees like AVL trees or red-black trees to keep data in order with logarithmic speed, but those trees demanded complex tree pivots that made code hard to write and debug. Pugh described the core methods in report CS-TR-2222 and later in publication UMIACS-TR-89-72.1. He found that strict geometric balance was not needed in real systems if coin flips could give the same expected speed without intricate subtree fixes [1].
By choosing random heights for new items, Pugh replaced tree pivots with basic probability. In a traditional balanced tree, adding a single key can trigger cascading fixes along parent links all the way up to the root. A skip list confines pointer adjustments strictly to immediate predecessor nodes of the added item, keeping routine steps fast and local. In A Skip List Cookbook, Pugh showed that skip lists also support search fingers, splitting, and merging, and his merge method achieves better asymptotic time complexity than any previously described merge method for balanced trees. The logic is simple [1].
Paul E. Black in the NIST Dictionary of Algorithms and Data Structures classifies the insert method as a Las Vegas algorithm, meaning that the code always produces a correct sorted result, but run time varies by chance. Randomness sets pointer heights rather than key order. Because key order stays strictly sorted, lookups stay exact and dependable under all circumstances [2].
How Express Layers Organize Traversal
A skip list arranges nodes in stacked horizontal tiers. Level 1 at the base is an ordinary linked list that holds every data item in sorted order, but each tier above it forms an express lane that contains fewer items to bypass long stretches of keys. Upper nodes hold taller pointer arrays [4]. Paul E. Black notes in the NIST dictionary that higher lists skip geometrically more items, creating an express layout that speeds queries to target keys. A skip list approximates binary search in a linked list, where searching begins at the highest level to reach the right region before dropping to lower levels [2].
Traversal begins at a sentinel head node on the top level. The search routine walks forward along the top list until the key of the next node is greater than or equal to the target value. When the next node key exceeds the target, the search drops down by one level to continue forward. Repeating this horizontal step and vertical drop sequence through successive tiers guides the search path smoothly to the matching element [4].
This descent path mimics binary search inside a dynamic linked list. In a flat linked list of n items, locating a target value needs scanning one by one through O(n) entries. By jumping forward over express links, a skip list trims big blocks of distant values during early steps before checking neighboring items at the bottom layer [2].
Search Step Mathematics
The density of each level in a skip list depends on a fixed promotion chance, written as p in theoretical papers. An item in level i rises to level i+1 with odds p, where code typically picks values like 1/2 or 1/4. Under this geometric rule, the expected count of list levels that any node spans is 1/(1-p), so most nodes stay short, but a few rise into high tiers. By tuning p, designers trade lookup speed against pointer memory use to match system needs [4].
Pugh showed that picking p = 1/e gives the lowest mean search time, but p = 1/2 simplifies code by using single coin flips [1]. The expected total search steps evaluate to (1/p) log_{1/p} n, giving an expected time bound of O(log n). Tracing the search path backwards reveals that each level needs at most 1/p steps on average, and with constant p, the total cost stays strictly within O(log n) bounds. The tallest node in a list of n items rarely grows past log_{1/p} n levels [4].
Could unlucky coin flips make search slow down into a linear scan? An odd run of coin flips could build an uneven list, but the odds of bad balance drop fast as the list grows [4]. In practice, random balance behaves with steady reliability, giving solid O(log n) speed without the burden of subtree weight checks [1].
Node Insert Logic in a Skip List
Adding a new item into a skip list begins by picking the height of the new node with independent coin flips [2]. The insert routine generates a random level by tossing a virtual coin until tails appears or until the height hits a preset ceiling. Once the height is set, the routine searches down from the top level, saving the last node seen at each level in an array called the update vector. This array marks the exact links where new forward pointers must splice into the existing list [1].
With the update array filled, the code allocates memory for the new node and updates pointers up to the chosen height. At each level, the new node points to the successor node held by the update node, and the update node points to the new node. This splice mirrors ordinary linked list insertion through multiple levels at once [4].
Libraries implement these steps with custom memory pools and comparison callbacks. In the Apache Portable Runtime library, the apr_skiplist module provides functions like apr_skiplist_init, apr_skiplist_add, apr_skiplist_insert, and apr_skiplist_alloc to manage node allocations in memory pools. Programmers set maximum heights and comparator functions to keep node distribution stable on production servers [3].
Rank Lookups by Link Width
Standard skip lists find keys quickly, but finding an item by its rank position—like looking up the 500th entry—normally needs linear O(n) scans [4]. William Pugh solved this problem by presenting the indexable skiplist in report UMIACS-TR-89-72.1 [1]. The core idea stores a numerical width value on every forward pointer link in the list. By tracking how many bottom links each upper pointer skips, the list lets queries jump forward by large rank offsets while adding up step counts [4].
The width of a link counts how many bottom-level links it spans along the sequence. If an express pointer at level 3 jumps over intermediate nodes that span two and three lower segments, its stored width is five. To find the fifth element, the routine moves across a top link of width 1, drops down when the next link of width 10 is too wide, and continues through lower links of width 3 and 1 to hit the exact target. The sum of link widths along any full horizontal path stays identical on every level [4].
To find an element by index, the lookup routine moves down from the top list while keeping a sum of traversed link widths. When the next link width is less than or equal to the remaining target index, the search moves forward and subtracts that width. When the next width is too big, the search drops down one level, completing the lookup in O(log n) time [4].
Production Uses in RocksDB and Redis
High-speed databases rely heavily on skip lists. Storage engines such as LevelDB and RocksDB use skip lists for their main in-memory memtable buffers because new keys can be added without global tree balancing passes or multi-node splits. Writes stay fast. By avoiding tree pivots during heavy write bursts, these key-value stores avoid long lock pauses and deliver steady throughput for incoming data [4].
In-memory store Redis pairs skip lists with hash tables to power its sorted set type, speeding score lookups and range queries. In online chat systems, Discord uses skip lists to manage active user rosters on large servers. Operating systems also use the design; MuQSS, a CPU scheduler for the Linux kernel, uses skip lists to handle priority queues [4].
Search platform Apache Lucene traverses delta-encoded posting lists with skip lists to speed query resolution. Cyrus IMAP server includes a skiplist database format for mail indexes, and IBM DOORS provides them in its scripting tools. In Java, ConcurrentSkipListMap and ConcurrentSkipListSet support thread-safe sorted maps without coarse locks, but Qt historically used them in QMap [4].
Why Skip List Setups Excel in Parallel Tasks
Multi-core systems expose the limits of balanced search trees under heavy parallel read and write jobs [6]. When multiple processor cores insert items into a shared binary tree at once, tree balance pivots lock large parts of the tree, creating a bad bottleneck at the root. A skip list removes this root bottleneck because updates touch only local neighbor pointers, letting threads write without coarse locks. Multiple threads can update separate parts of the list in parallel without blocking each other [4].
Computer scientists designed fast parallel skip list variants to scale on multi-core servers. Dick, Fekete, and Gramoli built the Rotating skip list, combining tree pivots with skip lists to eliminate root contention while keeping good cache locality. By swapping pointer towers for algorithmic wheels, their lock-free design reached 200 Mops/second on AMD Opteron and Intel Xeon processors. Dick, Fekete, and Gramoli tested the Rotating skip list against seven rival data structures across four synchronization methods, proving that wheel rotations maintain balance without lock overhead [6].
Memory topology brings more gains for multi-core speed. Daly, Hassan, Spear, and Palmieri built NUMASK, a skip list made for Non-Uniform Memory Access architectures. By keeping index pointer traversals inside the local NUMA memory zone of the running thread, NUMASK ran 2x to 16x faster than rival code under heavy write loads on four-socket servers with up to 160 threads [7].
Distributed Graphs from Splay-Lists to SkipNet
Modern research explores dynamic skip lists that change shape based on query traffic. Aksenov, Alistarh, Drozdova, and Mohtashami created the splay-list, an adaptive parallel skip list where the height of an item grows when it is queried often. By letting hot keys rise to upper express layers while demoting cold keys to lower tiers, the splay-list delivers fast amortized speed for skewed access patterns in multi-threaded systems [8].
In distributed networks, the skip list concept forms the foundation of peer-to-peer overlay graphs. In 2003, James Aspnes and Gauri Shah created skip graphs, while Nicholas Harvey, Michael Jones, Stefan Saroiu, Marvin Theimer, and Alec Wolman independently built SkipNet. Unlike distributed hash tables that randomize keys with hash functions, skip graphs keep key order across network nodes, supporting multi-node range searches while staying resilient against node failures. Skip graphs tolerate large fractions of random node failures, allowing peer nodes to search and repair links using straightforward local message exchanges [5].
Modern systems continue to adapt skip lists for varied hardware environments. Zhang, Wu, Tan, Chen, Cheng, Cao, Gao, and Feng built S3, an in-memory skip-list index for Alibaba Cloud RocksDB that uses a neural model to pick guard entries [9]. Li, Jiao, He, and Yu designed PhaST, a log-free hierarchical skip list that cuts index height on persistent memory [10]. For web safety, Shan, Cui, Hu, Jingfeng, Wang, and Raphael applied skip list signatures to detect cross-site scripting attack vectors [11].
- REPORT Pugh, W. (1998). A Skip List Cookbook. UMIACS-TR-89-72.1, Digital Repository at the University of Maryland. [Article Link]
- DICTIONARY ENTRY Black, P. E. (2019). Skip list. Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology. [Article Link]
- WEBSITE Apache Software Foundation. (2010). Apache Portable Runtime: Skip list implementation. [Article Link]
- WEBSITE Wikipedia contributors. (n.d.). Skip list. Wikipedia, The Free Encyclopedia. [Article Link]
- WEBSITE Wikipedia contributors. (n.d.). Skip graph. Wikipedia, The Free Encyclopedia. [Article Link]
- ACADEMIC JOURNAL Dick, I., Fekete, A. D., & Gramoli, V. (2016). A skip list for multicore. Concurrency and Computation: Practice and Experience, 29(4), e3876. [Article Link]
- ACADEMIC JOURNAL Daly, H., Hassan, A., Spear, M., & Palmieri, R. (2018). NUMASK: High Performance Scalable Skip List for NUMA. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 19. [Article Link]
- ACADEMIC JOURNAL Aksenov, V., Alistarh, D., Drozdova, A., & Mohtashami, A. (2023). The splay-list: a distribution-adaptive concurrent skip-list. Distributed Computing, 36(3), 395-418. [Article Link]
- ACADEMIC JOURNAL Zhang, J., Wu, S., Tan, Z., Chen, G., Cheng, Z., Cao, W., Gao, Y., & Feng, X. (2019). S3: a scalable in-memory skip-list index for key-value store. Proceedings of the VLDB Endowment, 12(12), 2183-2194. [Article Link]
- ACADEMIC JOURNAL Li, Z., Jiao, B., He, S., & Yu, W. (2022). PhaST: Hierarchical Concurrent Log-Free Skip List for Persistent Memory. IEEE Transactions on Parallel and Distributed Systems, 33(12), 3929-3941. [Article Link]
- ACADEMIC JOURNAL Shan, C., Cui, J., Hu, C., Jingfeng, X., Wang, H., & Raphael, M. (2016). A XSS Attack Detection Method based on Skip List. International Journal of Security and Its Applications, 10(5), 95-106. [Article Link]