3.15 Skip Lists

A skip list augments a sorted linked list with multiple levels of forward pointers. Higher levels “skip” over many nodes, enabling fast search, insertion, and deletion. The structure is probabilistic: node heights are assigned randomly, which yields expected logarithmic performance without rotations or strict balancing.

Structure

Each node stores a value and an array of forward pointers.

Node {
  value
  next[0..h]  // level 0 is the base list
}

A header node holds the top level.

head.next[0..maxLevel]
level = 0

Level 0 is a standard sorted singly linked list. Higher levels contain a subset of nodes that provide shortcuts.

Level Generation

Assign a height to each new node by flipping a biased coin.

random_level():
  lvl = 0
  while rand() < p and lvl < maxLevel:
    lvl += 1
  return lvl

Common choice: p = 0.5. Expected height is O(log n).

Search

Search proceeds from the top level, moving forward while possible, then dropping down.

cur = head

for i from level down to 0:
  while cur.next[i] != null and cur.next[i].value < target:
    cur = cur.next[i]

cur = cur.next[0]

if cur != null and cur.value == target:
  return cur
else:
  return null

At each level, the algorithm advances as far as possible without overshooting the target.

Insertion

Insertion first records predecessors at each level, then rewires pointers.

update[0..maxLevel]

cur = head

for i from level down to 0:
  while cur.next[i] != null and cur.next[i].value < value:
    cur = cur.next[i]
  update[i] = cur

lvl = random_level()

if lvl > level:
  for i in level+1..lvl:
    update[i] = head
  level = lvl

new = Node(value, lvl)

for i in 0..lvl:
  new.next[i] = update[i].next[i]
  update[i].next[i] = new

The array update stores the last node visited at each level before the insertion point.

Deletion

Deletion also uses the update array.

update[0..maxLevel]

cur = head

for i from level down to 0:
  while cur.next[i] != null and cur.next[i].value < value:
    cur = cur.next[i]
  update[i] = cur

cur = cur.next[0]

if cur != null and cur.value == value:
  for i in 0..level:
    if update[i].next[i] != cur:
      break
    update[i].next[i] = cur.next[i]

  while level > 0 and head.next[level] == null:
    level -= 1

The height of the structure shrinks if the top levels become empty.

Complexity

Expected bounds with probability parameter p:

Worst-case time is O(n), but occurs with very low probability.

Invariants

1. Each level is a sorted linked list.
2. Level i+1 is a subsequence of level i.
3. The head node spans all levels.
4. Forward pointers maintain increasing order.

These invariants ensure that search paths descend monotonically.

Comparison with Balanced Trees

Skip lists trade strict guarantees for simpler code and good average behavior.

Example Walk

Suppose levels:

Level 2: head -> 10 -> 30
Level 1: head -> 10 -> 20 -> 30 -> 40
Level 0: head -> 5 -> 10 -> 15 -> 20 -> 25 -> 30 -> 40

Searching for 25:

• Start at level 2: move to 10, then stop
• Drop to level 1: move to 20, then stop
• Drop to level 0: move to 25

The path length is logarithmic in expectation.

Common Failure Modes

• Incorrect update array leading to broken links
• Forgetting to update higher levels after insertion
• Not shrinking the top level after deletions
• Using inconsistent comparison rules
• Memory overhead from too large maxLevel

Tuning Parameters

• p = 0.5 gives balanced performance
• maxLevel ≈ log₂(n) is typical
• Larger p increases density and memory usage
• Smaller p reduces pointers but increases search time

Use Cases

Skip lists are useful when:

• you want ordered maps or sets with simple code
• concurrent or lock-free variants are needed
• balanced trees are too complex to maintain

They appear in databases, in-memory indexes, and systems where predictable average performance is sufficient.

Key Insight

A skip list simulates multiple resolutions of a linked list. Higher levels provide coarse navigation, and lower levels provide precision. Randomization replaces strict balancing, but preserves logarithmic behavior in expectation while keeping pointer manipulation straightforward.