Search Algorithm

Walk top-down: at each level, advance forward while the next key is still < target. When you can't advance, drop a level. After level 0, check if the next node is the target.

Average case: at each level, advance ~constant steps before dropping. Total levels: log_2(n). Total steps: O(log n).

Worst case (degenerate flips): O(n). With proper random levels, this is exceedingly rare — the probability is ~1/n.

Compare to balanced BSTs (red-black, AVL): same O(log n) but skip lists are simpler to make concurrent. RB trees require complex rotations; skip lists just relink forward pointers.