AlgoScope

Skip List

Layered linked lists where higher levels skip ahead, giving expected O(log n) search.

Data structures, data structure, advanced
Level 3: Drop a level: the next key is past the target.L3L2L1L0headhead44head725445867head3712192531445867

Skip List: Search skips along the express lanes

Decision, step 2 of 4

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.

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 expected not worst case.