# 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.

```text id="s4l9k2"
Node {
  value
  next[0..h]  // level 0 is the base list
}
```

A header node holds the top level.

```text id="v2q6p8"
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.

```text id="g7n3c1"
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.

```text id="b9x5u7"
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.

```text id="q3h8y4"
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.

```text id="h2k7w1"
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`:

| Operation |     Time |      Space |
| --------- | -------: | ---------: |
| Search    | O(log n) |       O(1) |
| Insert    | O(log n) | O(1) extra |
| Delete    | O(log n) | O(1) extra |

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

| Aspect         | Skip List                  | Balanced Tree          |
| -------------- | -------------------------- | ---------------------- |
| Balancing      | Randomized                 | Deterministic          |
| Implementation | Simple                     | Complex                |
| Rotations      | None                       | Required               |
| Performance    | Expected O(log n)          | Worst-case O(log n)    |
| Memory         | Multiple pointers per node | Typically two pointers |

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

## Example Walk

Suppose levels:

```text id="p8m4c6"
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.