Why does a skip list search faster than a sorted linked list holding the same keys?
answer
- Sorted is not the same as indexable
- What does binary search need to probe?
- Extra levels above the same chain
- Move right until overshoot, then drop
- Each level halves the nodes below
basics
~20 sA sorted linked list must be walked one node at a time, so lookup is O(n). A skip list stacks sparse express levels above that list, so a search gallops far, drops down, and skips most nodes — expected O(log n).
solid answer
~40 sSortedness alone does not buy you binary search: binary search needs random access to jump straight to a midpoint, and a linked list only offers `next` hops, so reaching the middle already costs O(n). A skip list keeps that sorted list as its bottom level and builds sparse extra levels above it, where each higher level holds a random subset of the keys below. A search starts at the leftmost node of the top level and moves right while the next key is still smaller than the target; when the next key would overshoot, it drops down one level and repeats. High levels cover long distances in few hops, and each drop halves the remaining span on average, giving expected O(log n) comparisons instead of O(n).
go deeper
Be ready to say why sortedness alone does not enable binary search, and to sketch a two- or three-level skip list showing that level 0 holds every key.
Explain the search rule precisely — move right while the next key is smaller, otherwise drop a level — and connect the halving of nodes per level to the expected O(log n) count.
An interviewer expects you to name what the express lanes actually cost: extra forward pointers per key, worse cache behaviour than contiguous storage, and an expected rather than worst-case bound.
Own the framing of why an ordered structure is on the table at all: point lookups alone favour hashing, and skip lists earn their place only when ordered iteration, range scans or predecessor queries are part of the requirement.
## The problem a skip list solves A sorted linked list is a chain of nodes, each holding a key and a reference to the next node, with keys in increasing order. Sorted order makes some things nice — you can stop a scan early, and iterating in key order is trivial — but it does **not** make lookup fast. Searching still means starting at the head and following `next` until you find the key or pass it: O(n) comparisons and, worse, O(n) pointer dereferences that jump around memory. The instinct is "it's sorted, so binary search it." That instinct is wrong, and the reason is worth saying out loud in an interview: **binary search requires random access, not just sortedness.** Binary search works by inspecting the midpoint of the remaining range in constant time. In a chain of nodes there is no way to reach the midpoint except by walking to it, which costs exactly what you were trying to avoid. Binary search needs a sorted *and* index-addressable domain (or, more generally, a monotone predicate you can probe at an arbitrary point in O(1)). ## The skip list idea: express lanes A skip list keeps the sorted chain — call it **level 0** — and adds levels above it. Level 1 contains a subset of level 0's keys; level 2 a subset of level 1's; and so on. Every key appears at level 0; a key that appears at level *k* also appears at every level below *k*. Picture a node as a small tower of forward pointers, one per level it reaches. The standard mental model is a train network. Level 0 is the local line stopping at every station. Level 1 is a limited-stop service; level 2 an express. To travel far, you ride the express until the next express stop would take you past your destination, then transfer down to a slower line, and repeat. You end up on the local line only for the last short stretch. ## How one search runs 1. Start at the head sentinel on the **top** level. 2. While the next node on this level has a key **strictly less than** the target, move right to it. 3. Otherwise, drop down one level and go back to step 2. 4. After dropping off level 0, the node immediately to the right is the first key greater than or equal to the target — either it is the target, or the target is absent. Every step either moves right (skipping over everything between the two nodes) or moves down (one of a small number of levels). If the levels are built so that roughly every other node is promoted, the number of nodes on level *k* is about n/2^k, the top level is around log₂ n, and the expected number of right-steps per level is a small constant. Total expected work: **O(log n)**. ## What the levels are not Three confusions come up constantly: - **The upper levels are not copies of the data.** They are additional forward pointers on the same nodes (or, in some layouts, small tower nodes referring to the same payload). The key set of the list is exactly level 0's key set. - **The top level is not a summary you search first and then "look up" in the bottom.** The search is one continuous walk that moves right and down through a single structure; there is no second lookup phase. - **A skip list is not an index built by a rebuild pass.** Levels are established when keys are inserted, and each key's height is chosen at insert time. ## What it costs The extra levels cost memory: with each key promoted to the next level with probability p, the expected number of forward pointers per key is 1/(1−p) — about two at p = 1/2. That is comparable to, or lighter than, many node-based ordered structures, but it is real overhead on top of the bare sorted chain. The bound is also **expected**, not guaranteed. The level structure comes from random promotion, so an unlucky draw can leave the list flatter than intended, and in the pathological limit — every key at height 1 — a skip list degenerates back into exactly the sorted linked list it started as, with O(n) search. Interviewers probe this; "skip lists guarantee O(log n)" is a marked wrong answer. What you keep, compared to array-backed sorted storage, is cheap splicing: once you have located the position, inserting or removing a key rewires a handful of pointers instead of shifting a block of elements. That combination — ordered iteration along level 0, expected-logarithmic point lookup, and pointer-local updates — is why skip lists show up as the backing structure for ordered indexes in real storage systems.
- If the list is already sorted, why not just binary search it?Binary search needs to inspect the midpoint of the remaining range in constant time. A chain of nodes offers only `next` hops, so reaching the midpoint costs O(n) — you have already paid for a linear scan before the first comparison narrows anything. Binary search needs a sorted *and* randomly addressable domain; a skip list buys back the jumping ability with extra pointers instead of contiguity.
- Which level holds the complete set of keys, and why does that matter?Level 0 holds every key, in sorted order. That matters for two reasons: correctness — a search always finishes on level 0, so it can never miss a key that was skipped higher up — and iteration, since scanning level 0 from the head yields all keys in order at O(1) per key, which is what makes range scans cheap.
- Does a skip list give you O(1) lookup like a hash-based structure?No. It is expected O(log n) for a point lookup, which is worse than a hash structure's expected O(1). What it gives instead is order: sorted iteration, predecessor and successor queries, and range scans, none of which a hash structure supports without sorting the whole key set.
Level 0 is the local train stopping at every station; the levels above are limited-stop and express services on the same track. You ride the fastest line that does not overshoot, then transfer down.
saying these in an interview costs you the question
- Says any sorted list can be binary searched
- Thinks the top level stores every key
- Believes upper levels duplicate the stored values
- Claims lookup is O(1) because of the express lanes
- Says the levels are rebuilt by a background pass