# Skip List
A sorted linked list plus express lanes. Searches ride the fast lanes down, and coin flips on insert keep the lanes balanced.
**Time:** O(log n)
**Space:** O(n)
**Difficulty:** HARD
*[Interactive widget: skip-list-visualizer (Skip List Visualizer) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/skip-list
---
A sorted array searches in `O(log n)` but inserts in `O(n)`, because every value right of the gap slides over\. A sorted linked list inserts in `O(1)` once you know the gap, but finding the gap costs the `O(n)` walk\. A skip list refuses to choose\. It keeps the linked list and buys back the speed with express lanes: extra linked lists stacked on top, each one skipping further than the one below\.

The figure above holds nine values in three lanes\. Level 0 is the full sorted list, level 1 keeps about half of the values, and level 2 about a quarter, so a search can ride a fast lane past whole stretches and drop down only when it gets close\. Press play and watch the list search for `17`: three hops right, two drops down, found\. Then read on\.

## Express lanes over a sorted list

Every value sits in a tower one, two, or three levels tall, and each level of a tower links to the next tower that reaches it\. Level 0 links everything, so the structure is always one walk away from a plain linked list\. The lanes above are pure shortcut\. In the figure, 5 of the 9 values reach level 1, and 2 of those reach level 2\. The hop from `6` to `19` on level 2 alone clears four values\.

The head tower on the left anchors every lane and gives each search its starting point at the top\. Nothing here knows an index, and no pointer ever points backward\. That is the whole structure: a sorted list, plus lanes that skip\.

## Search rides the lanes down

The rule fits in one line: move right while the next value is smaller than the target, and drop a level when it is not\. The sweep never steps on the target itself, only on smaller values\. So when it cannot move right at level 0, the next node is either the target or proof of its absence\. The search for `17` runs exactly these steps:

1. Level 2: `6 < 17`, so ride the top lane to `6`\. The next node on this lane is `19`, past `17`\. Drop to level 1\.
2. Level 1: `9 < 17`, so move to `9`\. The next node is `17` itself, and the sweep does not step on the target\. Drop to level 0\.
3. Level 0: `12 < 17`, so move to `12`\. The next node is `17`\. Found\.

Run `20` in the figure and the same sweep ends differently\. It stops at `19` with `21` ahead, and `20` is declared absent\. Notice what the search computed for free on the way: the exact gap where `20` belongs\. A skip list search always ends at the insertion point, which is why insert and delete are the same sweep with a tail attached\. If the rule feels familiar, it should: never overshoot, then look closer is [binary search](/algorithms/binary-search) turned into a data structure\.

## Insert splices, then flips a coin

Insert runs the search first, and the search hands it two answers\. One is the gap\. The other is the trail of drop points, the nodes where the sweep turned down, marked with a diamond in the figure\. Those are exactly the nodes a taller new tower would hang its pointers on, so the attach points come for free\. In the code below they live in an array called `update`\.

The figure below inserts `20`\. The sweep ends between `19` and `21`, and `20` splices into level 0\. The value is in the list at that moment; everything after is about the tower\. A coin flip settles each lane above\. Heads for level 1: `20` climbs, linked between `19` and `25`\. Tails for level 2: stop\. The tower stands two levels tall\.

*[Interactive widget: skip-list-visualizer — open the HTML page]*

No flip is coordinated with the rest of the list\. Each tower's height is its own run of luck, and that is what makes the structure cheap to maintain\. Try `8` and watch it climb to the top lane, then `4`, which never leaves the bottom\. **Reset** brings back the original nine\.

## Why coin flips are enough

Independent flips sound too loose to balance anything, and yet the averages are tight\. Each node climbs past level 1 with probability `1/2`, past level 2 with probability `1/4`, and so on, so a node's expected height is `1 + 1/2 + 1/4 + … = 2` pointers\. The whole list needs about `2n` pointers for `n` values\. Memory stays linear\.

Height concentrates the same way\. A lane survives to level `k` only if some node's flips carried it there, and past level `log₂ n` the expected number of towers on a lane drops below one\. So the top lane sits near `log₂ n`, each lane expects about two visited nodes per level, and a search totals roughly `2 · log₂ n` comparisons\. Expected `O(log n)`, bought with no rotations and no rebalancing passes\. A balanced tree buys the same bound by rewiring ancestors on every insert\. The skip list never touches a node outside the sweep path, and that locality is what makes it friendly to concurrent access later\.

The flips also break the link between input order and shape\. Feed a plain binary search tree sorted input and it degenerates into a chain\. Feed a skip list the same input and the expected shape is unchanged, because the heights never looked at the values\. There is no worst\-case input, only unlucky deals, and those are exponentially rare\. The figure below deals fresh towers so you can watch this hold: redeal a few times, then drag `p` down to `0.25` and watch the lanes thin out\. Lower `p` means fewer pointers per node and more steps per lane, a space\-for\-time dial\. Redis sets it to `1/4`\.

*[Interactive widget: skip-list-levels — open the HTML page]*

## Delete unhooks the tower

Delete is the same sweep followed by unhooking\. The search finds the node, the drop points again mark where pointers need rewiring, and each lane that carried the node hops one pointer past it, from the top of its tower down to level 0\. Try deleting `9` in either figure: level 1's lane from `6` lands on `17`, and level 0 closes `7` to `12`\. Deleting `6` costs three unhooks, one per level it reached\. Deleting an absent value costs the sweep and nothing else: the bottom\-level check finds no match, and no pointer moves\.

## The code is one sweep, three times

Search, insert, and delete share a single loop: from the top lane down, walk right while the next key is smaller, and remember where you stopped\. Search returns the bottom\-level candidate\. Insert records the stops in `update`, splices, then flips\. Delete records the stops and unhooks\. The whole structure fits in one class:

```python
import random

class Node:
	def __init__(self, key, levels):
		self.key = key
		self.forward = [None] * levels  # forward[i]: next node at level i

class SkipList:
	def __init__(self, max_level=16, p=0.5):
		self.max_level = max_level
		self.p = p
		self.head = Node(None, max_level)
		self.level = 0  # highest lane in use

	def _sweep(self, key):
		# Right while smaller, then down. update[i] is where level i stopped.
		update = [None] * self.max_level
		x = self.head
		for i in range(self.level, -1, -1):
			while x.forward[i] and x.forward[i].key < key:
				x = x.forward[i]
			update[i] = x
		return x.forward[0], update

	def search(self, key):
		node, _ = self._sweep(key)
		return node is not None and node.key == key

	def insert(self, key):
		node, update = self._sweep(key)
		if node is not None and node.key == key:
			return  # already in
		height = 1
		while height < self.max_level and random.random() < self.p:
			height += 1
		if height > self.level + 1:  # new top lanes attach at the head
			for i in range(self.level + 1, height):
				update[i] = self.head
			self.level = height - 1
		node = Node(key, height)
		for i in range(height):
			node.forward[i] = update[i].forward[i]
			update[i].forward[i] = node

	def delete(self, key):
		node, update = self._sweep(key)
		if node is None or node.key != key:
			return
		for i in range(len(node.forward)):
			update[i].forward[i] = node.forward[i]
		while self.level > 0 and self.head.forward[self.level] is None:
			self.level -= 1
```

The implementation panel below carries the same class in Python and JavaScript\. Production skip lists cap the height and pick `p` once, exactly as shown; the demo figure caps towers at three levels so every lane stays visible\.

## What it costs

All three operations are the same sweep with a different tail:

| Operation | Cost | Why |
| --- | --- | --- |
| `search` | `O(log n)` expected | About log₂ n lanes, about two visited nodes per lane\. |
| `insert` | `O(log n)` expected | One sweep, then one splice per level the tower reaches\. |
| `delete` | `O(log n)` expected | One sweep, then one unhook per level the tower reached\. |

Space is `O(n)`: about `2n` pointers at `p = 1/2`, plus the values themselves\. The guarantees hold in expectation, not per operation\. A single search can take a longer path; the average cannot\.

## Where it earns its keep

A skip list shows up wherever sorted data must stay fast under writes:

- **Sorted sets in Redis\. **A ZSET pairs a hash map for score lookups with a skip list for rank and range queries, with `p = 1/4` for tighter memory\.
- **Storage engines\. **LevelDB and RocksDB stage fresh writes in an in\-memory skip list, the memtable, before flushing sorted runs to disk\.
- **Concurrent maps\. **Java's ConcurrentSkipListMap is the standard ordered concurrent map\. Splices are local pointer swaps, so lanes can change without locking the whole structure\. A rebalancing tree has no equivalent luxury\.
- **Range scans\. **A range query is one search plus a level\-0 walk, and the walk touches exactly the answer\.

The practice problems below start with the direct build, Design Skiplist, and continue with ordered\-set problems where the same shape fits\. Keep the sweep in your head and each one reads as the same loop with different bookkeeping\.

## Code examples

### Skip list ordered set (CPP)

```cpp
#include <cstddef>
#include <random>
#include <stdexcept>
#include <vector>

template <typename K, typename V>
class SkipList {
public:
    explicit SkipList(int maxLevel = 16, double p = 0.5)
        : maxLevel_(maxLevel), p_(p), rng_(std::random_device{}()), dist_(0.0, 1.0) {
        if (maxLevel < 1) throw std::invalid_argument("maxLevel must be >= 1");
        head_ = new Node(K{}, V{}, maxLevel);
    }

    ~SkipList() {
        Node* x = head_;
        while (x) { Node* next = x->forward[0]; delete x; x = next; }
    }

    SkipList(const SkipList&) = delete;
    SkipList& operator=(const SkipList&) = delete;

    // Returns nullptr on a miss.
    const V* search(const K& key) const {
        Node* x = head_;
        for (int i = level_ - 1; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
        }
        x = x->forward[0];
        return (x && x->key == key) ? &x->value : nullptr;
    }

    void insert(const K& key, V value) {
        std::vector<Node*> update(maxLevel_, head_);
        Node* x = findPredecessors(key, update);

        Node* existing = update[0]->forward[0];
        if (existing && existing->key == key) {
            existing->value = std::move(value);
            return;
        }

        int lvl = randomLevel();
        if (lvl > level_) level_ = lvl;   // new levels: update already holds head_

        Node* node = new Node(key, std::move(value), lvl);
        for (int i = 0; i < lvl; ++i) {
            node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = node;
        }
        ++size_;
    }

    bool remove(const K& key) {
        std::vector<Node*> update(maxLevel_, head_);
        findPredecessors(key, update);

        Node* target = update[0]->forward[0];
        if (!target || target->key != key) return false;

        for (int i = 0; i < level_; ++i) {
            if (update[i]->forward[i] != target) break;   // target isn't this tall
            update[i]->forward[i] = target->forward[i];
        }
        delete target;

        while (level_ > 1 && head_->forward[level_ - 1] == nullptr) --level_;
        --size_;
        return true;
    }

    std::size_t size() const { return size_; }

private:
    struct Node {
        K key;
        V value;
        std::vector<Node*> forward;
        Node(const K& k, V v, int level)
            : key(k), value(std::move(v)), forward(level, nullptr) {}
    };

    int randomLevel() {
        int lvl = 1;
        while (dist_(rng_) < p_ && lvl < maxLevel_) ++lvl;
        return lvl;
    }

    Node* findPredecessors(const K& key, std::vector<Node*>& update) const {
        Node* x = head_;
        for (int i = level_ - 1; i >= 0; --i) {
            while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
            update[i] = x;   // dropping down: remember where we left this level
        }
        return x;
    }

    int maxLevel_;
    double p_;
    int level_ = 1;              // highest level in use
    std::size_t size_ = 0;
    Node* head_ = nullptr;       // sentinel

    mutable std::mt19937 rng_;
    mutable std::uniform_real_distribution<double> dist_;
};
```

### Skip list ordered set (Python)

```python
import random

class Node:
    """One tower in the list: a key and one forward pointer per level."""

    __slots__ = ("key", "forward")

    def __init__(self, key: int | None, levels: int) -> None:
        self.key = key
        self.forward: list["Node | None"] = [None] * levels

class SkipList:
    """Ordered set with expected O(log n) search, insert, and delete."""

    def __init__(self, max_level: int = 16, p: float = 0.5) -> None:
        self.max_level = max_level
        self.p = p
        self.head = Node(None, max_level)
        self.level = 0  # highest lane in use

    def _sweep(self, key: int) -> tuple["Node | None", list[Node]]:
        """Right while smaller, then down. update[i] is where level i stopped."""
        update = [self.head] * self.max_level
        x = self.head
        for i in range(self.level, -1, -1):
            while x.forward[i] is not None and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        return x.forward[0], update

    def search(self, key: int) -> bool:
        node, _ = self._sweep(key)
        return node is not None and node.key == key

    def insert(self, key: int) -> None:
        node, update = self._sweep(key)
        if node is not None and node.key == key:
            return  # already in
        height = 1
        while height < self.max_level and random.random() < self.p:
            height += 1
        if height > self.level + 1:  # new top lanes attach at the head
            for i in range(self.level + 1, height):
                update[i] = self.head
            self.level = height - 1
        node = Node(key, height)
        for i in range(height):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

    def delete(self, key: int) -> None:
        node, update = self._sweep(key)
        if node is None or node.key != key:
            return
        for i in range(len(node.forward)):
            update[i].forward[i] = node.forward[i]
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1

```

### Skip list ordered set (JavaScript)

```javascript
class Node {
  /** One tower in the list: a key and one forward pointer per level. */
  constructor(key, levels) {
    this.key = key;
    this.forward = new Array(levels).fill(null); // forward[i]: next node at level i
  }
}

/** Ordered set with expected O(log n) search, insert, and delete. */
class SkipList {
  constructor(maxLevel = 16, p = 0.5) {
    this.maxLevel = maxLevel;
    this.p = p;
    this.head = new Node(null, maxLevel);
    this.level = 0; // highest lane in use
  }

  /** Right while smaller, then down. update[i] is where level i stopped. */
  _sweep(key) {
    const update = new Array(this.maxLevel).fill(this.head);
    let x = this.head;
    for (let i = this.level; i >= 0; i -= 1) {
      while (x.forward[i] !== null && x.forward[i].key < key) {
        x = x.forward[i];
      }
      update[i] = x;
    }
    return [x.forward[0], update];
  }

  search(key) {
    const [node] = this._sweep(key);
    return node !== null && node.key === key;
  }

  insert(key) {
    const [node, update] = this._sweep(key);
    if (node !== null && node.key === key) return; // already in
    let height = 1;
    while (height < this.maxLevel && Math.random() < this.p) height += 1;
    if (height > this.level + 1) {
      // new top lanes attach at the head
      for (let i = this.level + 1; i < height; i += 1) update[i] = this.head;
      this.level = height - 1;
    }
    const fresh = new Node(key, height);
    for (let i = 0; i < height; i += 1) {
      fresh.forward[i] = update[i].forward[i];
      update[i].forward[i] = fresh;
    }
  }

  delete(key) {
    const [node, update] = this._sweep(key);
    if (node === null || node.key !== key) return;
    for (let i = 0; i < node.forward.length; i += 1) {
      update[i].forward[i] = node.forward[i];
    }
    while (this.level > 0 && this.head.forward[this.level] === null) {
      this.level -= 1;
    }
  }
}

```

### Skip list ordered set (Java)

```java
import java.util.Random;

public class SkipList<K extends Comparable<K>, V> {
    private static class Node<K, V> {
        K key;
        V value;
        @SuppressWarnings("unchecked")
        Node<K, V>[] forward;

        Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            this.forward = new Node[level];
        }
    }

    private final int maxLevel;
    private final double p;
    private final Random rnd = new Random();
    private final Node<K, V> head;   // sentinel

    private int level = 1;           // highest level in use
    private int size = 0;

    public SkipList(int maxLevel, double p) {
        if (maxLevel < 1) throw new IllegalArgumentException("maxLevel must be >= 1");
        this.maxLevel = maxLevel;
        this.p = p;
        this.head = new Node<>(null, null, maxLevel);
    }

    public SkipList() { this(16, 0.5); }

    private int randomLevel() {
        int lvl = 1;
        while (rnd.nextDouble() < p && lvl < maxLevel) lvl++;
        return lvl;
    }

    /** Predecessor of key at every level — the nodes whose pointers may change. */
    @SuppressWarnings("unchecked")
    private Node<K, V>[] findPredecessors(K key) {
        Node<K, V>[] update = new Node[maxLevel];
        java.util.Arrays.fill(update, head);

        Node<K, V> x = head;
        for (int i = level - 1; i >= 0; i--) {
            while (x.forward[i] != null && x.forward[i].key.compareTo(key) < 0) {
                x = x.forward[i];
            }
            update[i] = x;   // dropping down: remember where we left this level
        }
        return update;
    }

    public V search(K key) {
        Node<K, V> x = head;
        for (int i = level - 1; i >= 0; i--) {
            while (x.forward[i] != null && x.forward[i].key.compareTo(key) < 0) {
                x = x.forward[i];
            }
        }
        x = x.forward[0];
        return (x != null && x.key.compareTo(key) == 0) ? x.value : null;
    }

    public void insert(K key, V value) {
        Node<K, V>[] update = findPredecessors(key);

        Node<K, V> existing = update[0].forward[0];
        if (existing != null && existing.key.compareTo(key) == 0) {
            existing.value = value;
            return;
        }

        int lvl = randomLevel();
        if (lvl > level) level = lvl;   // new levels: update[] already holds head

        Node<K, V> node = new Node<>(key, value, lvl);
        for (int i = 0; i < lvl; i++) {
            node.forward[i] = update[i].forward[i];
            update[i].forward[i] = node;
        }
        size++;
    }

    public boolean remove(K key) {
        Node<K, V>[] update = findPredecessors(key);

        Node<K, V> target = update[0].forward[0];
        if (target == null || target.key.compareTo(key) != 0) return false;

        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != target) break;   // target isn't this tall
            update[i].forward[i] = target.forward[i];
        }

        while (level > 1 && head.forward[level - 1] == null) level--;
        size--;
        return true;
    }

    public int size() { return size; }
}
```

### Skip list ordered set (C)

```c
#include <stdlib.h>
#include <string.h>

#define SL_MAX_LEVEL 16
#define SL_P 0.5

typedef struct Node {
    int key;
    int value;
    struct Node *forward[];   /* flexible array member: exactly `level` pointers */
} Node;

typedef struct {
    Node *head;               /* sentinel */
    int   level;              /* highest level in use */
    int   max_level;
    double p;
    size_t size;
} SkipList;

static Node *node_create(int key, int value, int level) {
    Node *n = calloc(1, sizeof(Node) + (size_t)level * sizeof(Node *));
    if (!n) return NULL;
    n->key = key;
    n->value = value;
    return n;
}

SkipList *sl_create(int max_level, double p) {
    if (max_level < 1) return NULL;

    SkipList *sl = calloc(1, sizeof *sl);
    if (!sl) return NULL;

    sl->head = node_create(0, 0, max_level);
    if (!sl->head) { free(sl); return NULL; }

    sl->level = 1;
    sl->max_level = max_level;
    sl->p = p;
    return sl;
}

void sl_free(SkipList *sl) {
    if (!sl) return;
    Node *x = sl->head;
    while (x) { Node *next = x->forward[0]; free(x); x = next; }
    free(sl);
}

static int random_level(const SkipList *sl) {
    int lvl = 1;
    while ((double)rand() / ((double)RAND_MAX + 1.0) < sl->p && lvl < sl->max_level)
        lvl++;
    return lvl;
}

/* Fills update[] with the predecessor of key at every level. */
static void find_predecessors(const SkipList *sl, int key, Node **update) {
    for (int i = 0; i < sl->max_level; ++i) update[i] = sl->head;

    Node *x = sl->head;
    for (int i = sl->level - 1; i >= 0; --i) {
        while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
        update[i] = x;   /* dropping down: remember where we left this level */
    }
}

/* Returns 1 on a hit (value written to *out), 0 on a miss. */
int sl_search(const SkipList *sl, int key, int *out) {
    Node *x = sl->head;
    for (int i = sl->level - 1; i >= 0; --i) {
        while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
    }
    x = x->forward[0];
    if (!x || x->key != key) return 0;
    if (out) *out = x->value;
    return 1;
}

/* Returns 0 on success, -1 on allocation failure. */
int sl_insert(SkipList *sl, int key, int value) {
    Node *update[SL_MAX_LEVEL];
    find_predecessors(sl, key, update);

    Node *existing = update[0]->forward[0];
    if (existing && existing->key == key) {
        existing->value = value;
        return 0;
    }

    int lvl = random_level(sl);
    if (lvl > sl->level) sl->level = lvl;   /* new levels: update[] holds head */

    Node *node = node_create(key, value, lvl);
    if (!node) return -1;

    for (int i = 0; i < lvl; ++i) {
        node->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = node;
    }
    sl->size++;
    return 0;
}

/* Returns 1 if a node was removed, 0 if the key was absent. */
int sl_remove(SkipList *sl, int key) {
    Node *update[SL_MAX_LEVEL];
    find_predecessors(sl, key, update);

    Node *target = update[0]->forward[0];
    if (!target || target->key != key) return 0;

    for (int i = 0; i < sl->level; ++i) {
        if (update[i]->forward[i] != target) break;   /* target isn't this tall */
        update[i]->forward[i] = target->forward[i];
    }
    free(target);

    while (sl->level > 1 && sl->head->forward[sl->level - 1] == NULL) sl->level--;
    sl->size--;
    return 1;
}
```

### Skip list ordered set (CSharp)

```csharp
using System;
using System.Collections.Generic;

public class SkipList<TKey, TValue> where TKey : IComparable<TKey>
{
    private class Node
    {
        public TKey Key;
        public TValue Value;
        public Node[] Forward;

        public Node(TKey key, TValue value, int level)
        {
            Key = key;
            Value = value;
            Forward = new Node[level];
        }
    }

    private readonly int maxLevel;
    private readonly double p;
    private readonly Random rnd = new();
    private readonly Node head;      // sentinel

    private int level = 1;           // highest level in use

    public int Count { get; private set; }

    public SkipList(int maxLevel = 16, double p = 0.5)
    {
        if (maxLevel < 1) throw new ArgumentOutOfRangeException(nameof(maxLevel));
        this.maxLevel = maxLevel;
        this.p = p;
        this.head = new Node(default, default, maxLevel);
    }

    private int RandomLevel()
    {
        int lvl = 1;
        while (rnd.NextDouble() < p && lvl < maxLevel) lvl++;
        return lvl;
    }

    // Predecessor of key at every level — the nodes whose pointers may change.
    private Node[] FindPredecessors(TKey key)
    {
        var update = new Node[maxLevel];
        for (int i = 0; i < maxLevel; i++) update[i] = head;

        Node x = head;
        for (int i = level - 1; i >= 0; i--)
        {
            while (x.Forward[i] != null && x.Forward[i].Key.CompareTo(key) < 0)
                x = x.Forward[i];
            update[i] = x;   // dropping down: remember where we left this level
        }
        return update;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        Node x = head;
        for (int i = level - 1; i >= 0; i--)
        {
            while (x.Forward[i] != null && x.Forward[i].Key.CompareTo(key) < 0)
                x = x.Forward[i];
        }

        x = x.Forward[0];
        if (x != null && x.Key.CompareTo(key) == 0)
        {
            value = x.Value;
            return true;
        }
        value = default;
        return false;
    }

    public void Insert(TKey key, TValue value)
    {
        var update = FindPredecessors(key);

        Node existing = update[0].Forward[0];
        if (existing != null && existing.Key.CompareTo(key) == 0)
        {
            existing.Value = value;
            return;
        }

        int lvl = RandomLevel();
        if (lvl > level) level = lvl;   // new levels: update already holds head

        var node = new Node(key, value, lvl);
        for (int i = 0; i < lvl; i++)
        {
            node.Forward[i] = update[i].Forward[i];
            update[i].Forward[i] = node;
        }
        Count++;
    }

    public bool Remove(TKey key)
    {
        var update = FindPredecessors(key);

        Node target = update[0].Forward[0];
        if (target == null || target.Key.CompareTo(key) != 0) return false;

        for (int i = 0; i < level; i++)
        {
            if (!ReferenceEquals(update[i].Forward[i], target)) break;  // not this tall
            update[i].Forward[i] = target.Forward[i];
        }

        while (level > 1 && head.Forward[level - 1] == null) level--;
        Count--;
        return true;
    }

    // Level 0 is a plain sorted list, so range scans are just a walk.
    public IEnumerable<KeyValuePair<TKey, TValue>> Range(TKey lo, TKey hi)
    {
        Node x = head;
        for (int i = level - 1; i >= 0; i--)
        {
            while (x.Forward[i] != null && x.Forward[i].Key.CompareTo(lo) < 0)
                x = x.Forward[i];
        }

        for (x = x.Forward[0]; x != null && x.Key.CompareTo(hi) <= 0; x = x.Forward[0])
            yield return new KeyValuePair<TKey, TValue>(x.Key, x.Value);
    }
}
```