Skip to interview prep
Apexed

111. What is a skip list and how does it achieve O(log n) expected search?

HardLinked lists

Technical
Show model answer

A skip list is a sorted linked list with extra layers of "express" lists. Every node is in level 0; each node is also promoted to the next level up with probability 1/2 (by coin flip at insertion time). Search starts at the top level of the head node, moves right while the next key is smaller than the target, and drops down a level when it cannot move further.

With high probability there are O(log n) levels and the expected number of steps per level is constant, so search, insert and delete take O(log n) expected time, with O(n) expected space. The worst case is O(n), but it is extremely unlikely. Skip lists are simpler to implement than balanced trees and support lock-friendly concurrent versions, which is why they appear in systems such as Redis sorted sets and some LSM-tree memtables.

What is a skip list and how does it achieve O(log n) expected search — Data structures & algorithms interview question — Apexed