What you're seeing
A skip list keeps its keys in a sorted linked list, then builds express lanes over it: every element is on level 0, and each is independently promoted to level 1 with probability ½, to level 2 with probability ¼, and so on. The top lanes are sparse and skip over long stretches; the bottom lane has everything. To search, start at the top-left and move right as long as the next key is still smaller than the target; when the next key would overshoot, drop down one lane and continue. You glide across most of the list on the express lanes and only descend to the slow lane near the answer — the same divide-and-conquer reach as a balanced tree, achieved with nothing but coin flips.
The rule
insert(key): add to level 0; while coin flip is heads: promote up one level
search(key):
node = top-left sentinel
for level from top down to 0:
while next[node][level].key < key: node = next[node][level]
return next[node][0].key == key
The guarantee
Skip lists trade the worst-case guarantee of a balanced tree for an expected one that holds with overwhelming probability — and they get it for free from randomness, with no rotations or rebalancing. Two facts (this entry checks both empirically): the expected height of a single tower is 1/(1−p) = 2 levels for p = ½ (a geometric distribution), so the structure uses only O(n) space; and the expected cost of a search is O(log n). The search bound comes from walking the path backward: going up a level happens with probability ½ at each step and there are about log₂ n levels, so the expected number of steps per level is constant and the total is Θ(log n). Crucially, correctness never depends on the coins — the level-0 list is always a correct sorted list, so search is always exact; the randomness only governs speed, and a pathological run is astronomically unlikely.
The cost
All operations are O(log n) expected. The headline advantage over balanced BSTs (red-black, AVL) isn't asymptotic — it's simplicity: there are no rotations, no rebalancing cases, and insert/delete are short and local, which also makes concurrent (lock-free) skip lists far easier to build correctly than concurrent balanced trees. The price is that the bounds are probabilistic rather than guaranteed, and there's some pointer overhead.
In the wild
Skip lists are a production data structure, not just a teaching toy. Redis uses them for its sorted sets (ZSET), Java's ConcurrentSkipListMap/Set are lock-free ordered maps, Apache Lucene uses skip lists to jump through postings lists, and LSM-tree databases (LevelDB, RocksDB, HBase) use them for the in-memory memtable because concurrent inserts are easy. Anywhere you want an ordered map with simple code and good concurrency, the skip list is a favorite.
Try this
Hit New levels repeatedly with the same keys: the towers re-randomize but the search always succeeds — correctness doesn't care about the coins, only speed does. Search for a value that isn't present and watch the path land in the gap where it would be inserted. Add more Keys and the number of lanes grows like log₂ n, not linearly — the express network deepens just enough.
References
- Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees." Communications of the ACM 33(6):668–676, 1990. The original.
- Morin, P. Open Data Structures, §4 (Skiplists). opendatastructures.org — a free, rigorous treatment with the height and search-cost analysis.
- Herlihy & Shavit. The Art of Multiprocessor Programming — lock-free skip lists. Morgan Kaufmann.