Skip List
Layered linked lists where higher levels skip ahead, giving expected O(log n) search.
Decision · step 2 of 4Skip List: Search skips along the express lanes
Level 3 at the head: the next key on this lane is nothing, the end of the lane. It is not below 44, so drop to level 2 and keep looking from here.
What you will see
Several rows of nodes; search drops down a level when the next node is too large.
Cost
| search | O(log n) expected |
|---|---|
| insert | O(log n) expected |
| delete | O(log n) expected |
| Space | O(n) expected |
Randomized level assignment; bounds are expectednot worst case.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.