Why does a skip-list insert cost no more than the search that precedes it?

## The search already knows the answer The cheapest way to see why skip-list insertion is inexpensive is to look at what the search leaves behind. ``` x = head for level = top downto 0: while x.next[level] != null and x.next[level].key < target: x = x.next[level] predecessor[level] = x // last node before target at this level // predecessor[0].next[0] is the first key >= target ``` The loop moves right while the next key is strictly smaller than the target, and otherwise drops one level. The invariant it maintains is: **`x.key < target`, and every key strictly between `x` and `target` lies below the current level.** So at the instant the loop leaves level *k*, `x` is the rightmost node on level *k* whose key is less than the target — its predecessor at that level. Capturing `x` into `predecessor[level]` costs one array store and nothing else. A plain lookup ignores that array and just inspects `predecessor[0].next[0]`. An insert uses the whole array. ## Splicing the new node in Insertion is then: 1. Draw a height *h* for the new node by repeated coin flips. 2. If *h* exceeds the current top level, treat the head sentinel as the predecessor on those new levels. 3. For each level *i* from 0 to *h*−1: set `new.next[i] = predecessor[i].next[i]`, then `predecessor[i].next[i] = new`. That is the entire structural change. Every touched pointer belongs either to the new node or to one of *h* predecessor nodes. Nothing else in the structure is read, moved, or rewritten. Because heights are geometric with parameter p, the expected height is 1/(1−p) — two at p = 1/2 — so the splice is **expected O(1) pointer writes**, and the search's expected O(log n) dominates the total. Deletion is the mirror image and uses the same recorded predecessors: for each level where `predecessor[i].next[i]` is the victim, skip it. ## Why there is nothing to rebalance This is the property that distinguishes a skip list from balanced search trees. A balanced tree maintains a structural invariant — a bound on height, or on the relationship between sibling subtrees — and an insertion that breaks it must be repaired by restructuring on the path back to the root. That restructuring is where the complexity of implementing balanced trees lives, and where their concurrent versions get hard: a repair can touch nodes far from the insertion point, potentially up to the root. A skip list maintains **no such invariant**. Its only shape requirement is the one randomness already satisfies in expectation, and a single insert cannot violate a rule that does not exist. So the modification is local by construction: a bounded, small set of neighbouring pointers, all of them adjacent to the insertion point. Two consequences follow directly: - **Implementation size.** The insert path is a search plus a loop of two-line splices, with no case analysis over structural configurations. It is dramatically smaller than a balanced-tree insert, and small code is code you can review. - **Concurrency.** Since a writer touches only a few adjacent pointers, fine-grained locking (lock just the predecessors involved) and lock-free designs (compare-and-swap each level's forward pointer, bottom level first, with logically-deleted marks for removal) are tractable. That is why skip lists appear as the ordered structure in concurrent settings far more often than their sequential performance alone would justify. ## The boundary cases worth naming - **Strict `<` matters.** If the walk used `<=`, it would step *past* a node with a key equal to the target, and the predecessor array would point one node too far right — inserting an equal key on the wrong side, or making a delete miss its victim. Off-by-one at this comparison is the classic skip-list bug. - **Growing the top.** When a drawn height exceeds the current maximum, the head sentinel must be extended and used as the predecessor on the new levels; forgetting this leaves the tall part of the new tower unreachable from the head, so the key is present but invisible above level 0. - **A head sentinel earns its keep here.** With a head node that has a forward pointer at every level, no insertion is ever a special "insert before everything" case; the predecessor at each level is always a real node. - **Bottom-level truth.** Every key is on level 0, so a search that has descended correctly can never miss a key regardless of what the upper levels look like — an important safety property when levels are being modified concurrently. ## The line to say out loud "The descent already computes the predecessor at every level; record it, and the insert is a constant number of pointer writes on top of the search — nothing to rebalance, because there is no invariant to break."