You need ordered keys and logarithmic lookup. A balanced tree will do it — after you keep the height honest with rotations. Sorted input, deletes, and concurrent writers all become rotation stories. Teams that wanted a map paid for a balancing algorithm.
A skip list is a layered linked list: level 0 holds every key; higher levels skip ahead. Search drops from express lanes to local streets. Height comes from coin flips, not from rotating a parent. Expected search, insert, and delete are O(log n) without a tree.
ADT vs implementation, expected vs worst-case, and how to read a complexity table live on the Data Structures Roadmap. This post stays on one layout: the layers, the coin, search and insert, and the JDK type that ships it.
Levels are express lanes on a sorted list
Level 0 is a sorted singly linked list of every key. Each higher level is another sorted list over a subset of those keys. A node that appears on level 2 also appears on 1 and 0 — it is the same key with extra forward pointers.
L2: HEAD ----------------> 50 --------------------> NIL
L1: HEAD ------> 20 -----> 50 -----> 70 ----------> NIL
L0: HEAD -> 10 -> 20 -> 30 -> 50 -> 70 -> 90 -----> NIL20 is an express stop: from HEAD on L1 you jump to 20 instead of walking 10. 50 is on every level — a long-haul lane. 30 lives only on L0; you only meet it after you have already narrowed the range.
That is the whole trade: extra pointers buy skips; the list stays sorted; nobody rotates a subtree. Space is expected O(n) because most nodes have one or two forwards, not a tower of height n.
A node is a key plus an array of next pointers, one per level it participates in:
final class Node {
final int key;
final Node[] next; // next[i] = successor on level i
Node(int key, int height) {
this.key = key;
this.next = new Node[height];
}
}Height 1 means L0 only. Height 3 means L0, L1, and L2. The list head is a sentinel with the maximum height and no key — every search starts there.
Coin-flip height: expected log, not a rotation
When you insert a key, you do not pick a clever slot in a tree. You splice it into L0 (it belongs in sorted order), then decide how many express lanes it joins. The usual rule is a fair coin: stay on the next level with probability 1/2, else stop.
int randomHeight(int maxHeight, Random rng) {
int h = 1;
while (h < maxHeight && rng.nextBoolean()) {
h++;
}
return h;
}Expected height of a node is 2. Expected maximum height of the whole list is O(log n) if you cap maxHeight around log2 n plus a small constant (JDK skip maps use a fixed cap, on the order of 32 or 64). A node of height h appears on levels 0 .. h-1.
Note: The coin is why skip lists are expected O(log n), not worst-case O(log n). A pathological run of heads builds a tall sparse tower; a run of tails leaves L0 as a plain list and search walks it. With an independent coin and a height cap, that is rare. It is still not a height invariant you can prove the way AVL proves |balance| ≤ 1.
No rotation, no color bit, no “left-left case.” The random bits are the balance.
Search: right until you would pass, then drop
Start at the head on the highest occupied level. Walk right while the next key is still ≤ the target (or <, if you treat equals as “found”). When the next key would overshoot — or the next pointer is null — drop one level and keep going. On L0, either you land on the key or you know it is missing.
boolean contains(Node head, int topLevel, int key) {
Node node = head;
for (int level = topLevel; level >= 0; level--) {
while (node.next[level] != null && node.next[level].key < key) {
node = node.next[level];
}
}
Node candidate = node.next[0];
return candidate != null && candidate.key == key;
}Search for 30 on the diagram:
L2: HEAD, next is 50 > 30 → drop
L1: HEAD → 20 (20 < 30), next is 50 > 30 → drop
L0: 20 → 30 foundSearch for 40 (absent): same walk to 30 on L0; next is 50, so not present. Each drop throws away a span of keys you no longer need to scan. With geometric height, the expected number of right-steps per level is constant, so the whole walk is expected O(log n).
Insert: search for predecessors, then splice
Insert is search that remembers the last node visited at each level — those are the predecessors whose next pointers will change. Then coin-flip the new height, allocate the node, and relink.
void insert(Node head, int topLevel, int key, Random rng) {
Node[] pred = new Node[topLevel + 1];
Node node = head;
for (int level = topLevel; level >= 0; level--) {
while (node.next[level] != null && node.next[level].key < key) {
node = node.next[level];
}
pred[level] = node;
}
if (node.next[0] != null && node.next[0].key == key) {
return; // already present
}
int height = randomHeight(topLevel + 1, rng);
Node fresh = new Node(key, height);
for (int level = 0; level < height; level++) {
fresh.next[level] = pred[level].next[level];
pred[level].next[level] = fresh;
}
}Insert 25 with a coin that lands height 2 (L0 and L1):
predecessors: L2 stays HEAD (25 < 50, never spliced at L2)
L1 is HEAD (next is 20; 20 < 25, then 50 > 25 → pred = 20)
L0 is 20
splice L0: 20 → 25 → 30
splice L1: 20 → 25 → 50Delete is the same predecessor walk, then bypass the node at every level it occupies. You do not “fix” height afterward; the remaining towers still skip. That is why skip lists stay simple under mutation: splice pointers, do not restore a global shape invariant.
| Operation | Expected | Worst-case (degenerate coins) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Space | O(n) | O(n) with a height cap |
Read that table the hub’s way: expected is the production bill with a real coin. Worst-case is the “every insert got height 1” list. If you need the worst-case column to be O(log n) always, this is the wrong layout.
ConcurrentSkipListMap is the JDK type
Java does not ship a public SkipList class. The production type is java.util.concurrent.ConcurrentSkipListMap (and ConcurrentSkipListSet on top of it): a concurrent, sorted NavigableMap whose keys sit in a skip list.
NavigableMap<Integer, String> ranks = new ConcurrentSkipListMap<>();
ranks.put(50, "mid");
ranks.put(20, "low");
ranks.put(70, "high");
ranks.get(20); // "low" — expected O(log n)
ranks.ceilingKey(35); // 50
ranks.subMap(20, 70); // 20, 50 — ordered viewUse it when several threads read and write an ordered map without wrapping TreeMap in a lock. Iterators are weakly consistent. null keys are forbidden. Cost is expected logarithmic, not hash-table constant time.
Redis sorted sets use the same idea: a hash table for key → score, plus a skip list for rank and range by score. You do not implement either from scratch for a leaderboard; you recognize the layout when the docs say “skip list.”
Note: Sequential sorted maps in the JDK are still TreeMap / TreeSet (red-black). Reach for ConcurrentSkipListMap when the job is concurrent and ordered. Do not pick it as a faster HashMap.
When not to use a skip list
Skip the skip list when the job is not “ordered keys, expected log n, no rotations”:
- You needed unique keys and fast lookup, not order. That is a hash table —
HashMap/ConcurrentHashMap.ceilingKeyandsubMapare how you know you wanted a skip list (or a tree).getalone is not. - You need deterministic worst-case
O(log n). AVL (and red-black) prove height. A skip list expects log n. Hard real-time, or a latency SLO that treats a linear walk as an incident, wants a balanced tree, not a coin. nis tiny and a sorted list is already there. Binary search on anArrayListyou rebuild rarely is simpler than explaining towers. Measure when the set mutates in the hot path.- Single-threaded sorted map, JDK default.
TreeMapis the sequential type.ConcurrentSkipListMapis the concurrent one. Swapping them to “use a skip list” without a concurrency story is cargo-culting the name.
Range queries over a mutable ordered set are the job this layout is for. Approximate membership, prefix search, and next-best element are other layouts — pick them from the hub by the hot operation, not by how clever the balancing looks.
Cheat sheet
Skip list: sorted linked list + higher levels that skip
L0: every key, sorted
Higher: subset; same key, extra forward pointers
Height: coin flip (p = 1/2 per extra level); cap it
Search: right until overshoot, drop a level; expected O(log n)
Insert: predecessor walk, splice, coin-flip height
Delete: predecessor walk, bypass
Not a tree: no rotations; balance is randomness
Expected: O(log n) search / insert / delete; not a worst-case law
JDK: ConcurrentSkipListMap / ConcurrentSkipListSet
Also: Redis sorted sets (skip list + hash)
Avoid: HashMap jobs (no order); AVL when worst-case must be log nDo:
- Name the hot operation: ordered lookup / range as the set mutates, possibly concurrently.
- Use
ConcurrentSkipListMapwhen that sentence is true in Java. - Treat the coin as expected cost; cap height so a tower cannot become
n.
Don’t:
- Replace
HashMapwith a skip list because both are “fast lookup.” - Promise worst-case
O(log n)the way AVL does. - Implement a skip list on Friday when the JDK already has
ConcurrentSkipListMap.
Wrap-up
A skip list is a sorted linked list with express lanes. Level 0 holds every key. Higher levels skip. Search walks right, then drops. Insert splices after a predecessor walk and lets a coin pick the new node’s height. Expected cost is O(log n) without rotations.
The JDK type is ConcurrentSkipListMap. Redis sorted sets use the same layout. Reach for a hash map when you do not need order. Reach for AVL (or another balanced tree) when the worst-case column has to be logarithmic, not expected.
If the hot path is ordered keys and you would rather flip a coin than rotate a subtree, a skip list is the layout that makes that cheap. The series hub is the glossary and index when you need to match a different job to a different layout.