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

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.

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:

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:

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.