// computers › Tree-Based
A linked list with extra 'express lane' layers that let you skip ahead quickly.
start top-left; move right while next <= target, else drop down a level; repeat
Picture taking the express line to get near your stop quickly, then switching to the local line for the exact station. A skip list has exactly these layers: sparse express lanes on top that skip over many nodes, and the full local line at the bottom with every element. A search rides the express lanes to get close fast, then drops to finer lanes for the exact spot - giving balanced-tree speed using simple linked lists plus a bit of randomness.
It stacks express lanes over a sorted linked list. The bottom lane links every node; each higher lane links only some nodes, spaced further apart. A search starts on the top, sparsest lane and races right until the next node would overshoot the target, then drops to a denser lane and repeats. Each drop roughly halves the remaining distance, so the search takes about log(n) steps - the same as a balanced tree, but achieved with simple linked lists and no rotations.
Each node, when inserted, flips a coin repeatedly: it is promoted to the next express lane with probability one half, stopping at the first tails. This randomness gives, on average, half as many nodes on each higher lane - exactly the geometric thinning that makes search O(log n) expected. The beauty is that no rebalancing is ever needed: randomness keeps the structure balanced on average, which is far simpler to implement correctly than the rotation logic of AVL or red-black trees. (This demo uses fixed levels just for a tidy picture.)
They offer the same O(log n) expected performance for search, insert, and delete, and both keep data ordered. The skip list's advantage is simplicity: linked-list operations with coin flips are much easier to get right than tree rotations, and they are friendlier to concurrent (lock-free) implementations. The trade-off is that the skip list's guarantee is probabilistic - astronomically unlikely to be slow, but not impossible - whereas an AVL tree guarantees O(log n) absolutely.
Each node needs forward pointers for every lane it appears on. Since half the nodes appear on level one, a quarter on level two, and so on, the total number of extra pointers sums to about n - so the overhead is linear, O(n), with a small constant. Most nodes carry just one or two pointers; only a few tall nodes carry several. This is comparable to a tree's child pointers, so memory use is reasonable for the speed gained.
Redis uses skip lists to implement its sorted sets (the ZSET type), where elements are kept ordered by score and must support fast range queries and rank lookups - the skip list's ordered express lanes make those operations efficient and the implementation tractable. They also appear in some database and key-value engines, and in concurrent data structures (such as Java's ConcurrentSkipListMap) where their lock-free friendliness is valuable. Wherever ordered data needs tree-like speed with simpler, concurrency-friendly code, skip lists are a strong choice.