EN 
Українська
Polski
Español
Deutsch
日本語
Italiano
Português (BR)
Français
العربية
Nederlands
中文
한국어
हिन्दी
Türkçe
Tiếng Việt
Русский
Bahasa Indonesia
فارسی
বাংলা
ไทย
Filipino
Kiswahili
اردو
Bahasa Melayu
தமிழ்
עברית
Ελληνικά
ਪੰਜਾਬੀ
አማርኛ
မြန်မာဘာသာ
ខ្មែរ
ქართული
नेपाली
Монгол хэл
Հայերեն
සිංහල
ລາວ
Čeština
Română
Magyar
Български
Svenska
Dansk
Suomi
Norsk
Slovenčina
Hrvatski
Српски
Slovenščina
Lietuvių
Latviešu
Eesti
Íslenska
Shqip
Македонски
Bosanski
Malti
Azərbaycanca
Қазақша
O'zbekcha
Тоҷикӣ
Кыргызча⏭️ Skip List — Probabilistic Balanced Search
A skip list stacks express lanes over a sorted linked list: each node is promoted with probability ½, giving expected O(log n) search by skipping ahead on high levels then dropping down.
About Skip List
A skip list, introduced by William Pugh in 1990, is a probabilistic data structure that maintains a sorted sequence of elements across multiple linked-list layers. The bottom layer is a complete sorted list; each higher layer acts as an "express lane" by retaining only a random subset of the layer below, with each element independently promoted with probability p (typically 0.5). Search, insertion, and deletion all achieve expected O(log n) time — matching a balanced BST — without the deterministic rebalancing overhead of AVL or red-black trees.
This simulation lets you insert and delete integer keys while watching each node's tower grow to a random height. The highlighted traversal path during search shows how the algorithm descends through express lanes before dropping to the next layer, illustrating why the average number of comparisons is approximately log1/p n.
Frequently Asked Questions
How does a skip list achieve O(log n) search without deterministic balancing?
Each node's height is drawn independently from a geometric distribution with success probability p, so the expected number of nodes at level k is n·pk. A search starts at the highest level, advances as far as possible, then drops down — the expected total comparisons is log1/p n + 1/p, which is O(log n). Randomness effectively balances the structure in expectation without any explicit rotations.
What is the worst-case time complexity of a skip list?
The worst-case time is O(n) — for instance if every node happens to be promoted to every level — but this occurs with exponentially small probability. In practice, skip lists are used where probabilistic guarantees are acceptable (e.g., Redis's sorted sets use a skip list internally), since worst-case guarantees from balanced trees are rarely needed in those contexts.
How much memory does a skip list use compared to a balanced BST?
With promotion probability p = 0.5, the expected total number of pointers across all levels is 2n (each node contributes one pointer per level, expected height 1/(1−p) = 2). A standard red-black tree node also stores two child pointers plus a parent pointer and a colour bit, so the memory usage is comparable; skip lists often have slightly higher constant factors due to the variable-length tower allocations.
How does skip list insertion maintain sorted order?
Insertion first searches for the position where the new key belongs (recording the rightmost node visited at each level in an update array), then generates a random height h for the new node, and finally splices it into each level from 0 to h−1 by updating the forward pointers recorded during the search. This is analogous to insertion into a linked list but repeated for each active level.
What value of promotion probability p gives the best performance?
p = 0.5 balances expected search time and space: lowering p reduces memory but increases expected comparisons per level; raising p increases memory. Pugh's original analysis showed p = 0.25 gives nearly the same expected time with 25% fewer pointers, and Redis uses p = 0.25 for its skip list implementation. The optimal choice depends on the read/write ratio and memory constraints of the application.
How does a skip list compare to a binary search tree for concurrent use?
Skip lists are often preferred in concurrent settings because lock-free and wait-free variants are much simpler to implement than concurrent balanced BSTs. Lock-free skip lists (e.g., the Harris-Fraser-Shavit algorithm) require only atomic compare-and-swap on individual pointers, whereas concurrent AVL or red-black trees must lock or carefully version entire rotation chains. Java's ConcurrentSkipListMap uses this approach.
Is there a deterministic version of a skip list?
Yes. Deterministic skip lists (also called 1–2 skip lists or B-skip lists) enforce exact structural rules rather than relying on randomisation, guaranteeing O(log n) worst-case time. However, they require more complex insertion and deletion logic that is closer to a B-tree than the elegant coin-flip simplicity that makes probabilistic skip lists popular.
What real-world systems use skip lists?
Redis uses a skip list to back its Sorted Set data type, enabling O(log n) rank queries and range scans by score. Apache Cassandra previously used skip lists for its Memtable in-memory store. LevelDB and RocksDB use a variant for their in-memory write buffer. The Java standard library's ConcurrentSkipListMap and ConcurrentSkipListSet are also backed by a skip list.
How are skip lists deleted from?
Deletion locates the node and, for each level where it appears, updates the forward pointer of the predecessor to skip over it. After unlinking, the tower of the deleted node can be freed. If the deletion reduces the effective height of the list (i.e., the top levels become empty), the maximum level counter is decremented. The expected time is O(log n), matching search.
Can a skip list support range queries efficiently?
Yes — this is one of skip lists' practical advantages over hash tables. After a O(log n) search to find the start of the range, the bottom-level linked list provides O(k) traversal to collect all k elements in the range. Redis exploits this for ZRANGEBYSCORE and ZRANGEBYLEX commands, which are central to leaderboard and time-series use cases.
A skip list stacks express lanes over a sorted linked list: each node is promoted with probability ½, giving expected O(log n) search by skipping ahead on high levels then dropping down.
3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install