Skip List Structure

Each node is:

A node "exists" at every level from 0 up to its level. A node at level 3 has 4 forward pointers (0, 1, 2, 3).

The skip list itself:

The HEAD is a sentinel with the maximum possible levels. Every search starts at the topmost level of HEAD.

Insertion fills forward links at each level the new node participates in. Search descends levels at each "next is too big" decision point.

Memory: each level adds one pointer per node at that level. Total pointers ≈ 2N (geometric series). For 1M entries: ~16 MB of overhead beyond the data.