Skip List

Introduced in CS240.

The motivation of skip lists to to imitate binary search in an ordered Linked List.

• With an ordered array, we can directly do binary search, but we cannot do binary search directly on a linked list

One node per layer

So the stack stores one node per layer.

Examples