· Development

Skip lists: how coin-flip levels give O(log n) expected search

Why does adding random-level pointers to a sorted linked list make search O(log n) expected? Pugh's algorithms, what 'expected' covers, and what Java's ConcurrentSkipListMap docs promise.

DevelopmentAlgorithmsData Structures

To find 19 in a sorted linked list holding 3, 6, 7, 9, 12, 17, 19, 21, 25 and 26, you walk past 3, 6, 7, 9, 12 and 17 in turn. With an array you could jump to the middle with binary search, but a linked list only has a pointer to the next node.

A skip list fixes this by giving some nodes extra pointers that jump further ahead, and it decides how many each node gets by flipping coins. This article follows William Pugh’s technical report “A Skip List Cookbook” (July 1989, revised June 1990) and the Java SE 25 API documentation.

Every node has a level

Each node in a skip list has a level, which is the number of forward pointers it holds. A node’s i-th pointer points to the next node of level i or higher. At the end sits NIL, whose key is greater than any legal key, and every level ends there.

Give the keys above some levels and the list looks like this. The levels were picked by hand for illustration.

level 4  H  -------> 6  -------------------------------------------------> NIL
level 3  H  -------> 6  -------------------------------------> 25 -------> NIL
level 2  H  -------> 6  -------> 9  -------> 17 -------------> 25 -------> NIL
level 1  H  -> 3  -> 6  -> 7  -> 9  -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> NIL

H is the header. It has one pointer for each level up to MaxLevel, and pointers above the list’s current level point to NIL.

Search: go right until you would overshoot, then drop a level

Search starts at the list’s current maximum level. If the next node’s key is smaller than the key you want, move right; otherwise drop one level. When you can’t move any further at level 1, the key you want, if present, is in the very next node.

x := header
for i := list level downto 1
    while key of x's next node at level i < search key
        x := x's next node at level i
x := x's next node at level 1
if x's key = search key, return x's value; otherwise fail

Searching for 19 in the diagram goes like this:

  1. Level 4: the header’s next node, 6, is smaller than 19, so move to 6. After 6 comes NIL, so drop down.
  2. Level 3: 6’s next node is 25, larger than 19, so drop down.
  3. Level 2: move to 9, then 17. 17’s next node is 25, too large, so drop down.
  4. Level 1: 17’s next node is 19, which is not smaller than 19. Stop, step forward once, and check 19.

The search passes through 6, 9 and 17. Following level 1 alone would have passed through six nodes, 3 through 17. With only ten nodes the gap is small, but the idea is that sparse high-level nodes let the search take big steps near the top.

Insertion and deletion: search, then splice

Insertion and deletion run the same search, but at each level they record in update[i] the node they were standing on just before dropping down. When the search finishes, update[i] is the rightmost node of level i or higher to the left of the insertion or deletion point.

A new node’s level comes from this function:

randomLevel()
    lvl := 1
    while random() < p and lvl < MaxLevel
        lvl := lvl + 1
    return lvl

With p = 1/2, 50% of nodes get level 1, 25% get level 2 and 12.5% get level 3. Levels are chosen without regard to how many elements the list holds. The insert then redirects the pointers of update[i] to the new node for levels 1 through the new level, and points the new node at what used to come next. Deletion splices the node out the same way and lowers the list’s level if the top levels are left empty. Either way, only pointers next to that node change; the report calls these local modifications.

Pugh recommends setting MaxLevel to log_{1/p} N, where N is an upper bound on the number of elements. With p = 1/2, he writes that MaxLevel = 32 is appropriate for up to 2³² elements.

What “expected” O(log n) means

The cookbook gives the expected cost of search, insertion and deletion as O(log n). Nothing rules out the worst case. If the levels come out badly, for example every node at level 1, a search is just a walk along a linked list. The report’s analysis shows such arrangements are rare.

That comes with an assumption: users cannot see the levels of elements. The report itself notes that a user who could see them might delete every element that is not level 1 and force worst-case running times. Luck is also not redrawn for every operation on the same structure. Two successive searches for the same element take exactly the same time. If a key was slow to find once, it stays slow until the list changes.

The cookbook derives a probabilistic upper bound on the number of comparisons and gives its expected value as L(n)/p + 1/(1−p) + 1, where L(n) = log_{1/p} n. Table 2 in the report lists:

p Average search cost Average pointers per element
1/2 2 lg n + 3 2
1/4 2 lg n + 7/3 1⅓

Plugging n = 2²⁰ (1,048,576) into the p = 1/2 row gives 2 × 20 + 3 = 43. That is a computed expectation of an upper bound, not a measurement. Lowering p to 1/4 keeps that expectation nearly the same while cutting pointers per element from 2 to 1⅓. The same table gives the variance at p = 1/4 as 6 lg n − 68/9 − 16/n, larger than 2 lg n − 4/n at p = 1/2. You save space, and search times become less even.

Working by position, not just by key

As the title suggests, the report is mostly about what comes after the basic operations. A few of them:

  • Search fingers: keep the update vector from the last operation, and finding an element k positions away takes O(log k) expected time. The report warns that the overhead can slow things down overall when searches lack locality of reference.
  • Split and concatenate: splitting a list at a key, or joining two lists when the last key of the first is ≤ the first key of the second, takes O(log n) expected time.
  • Search by position: store with each pointer the number of elements it skips (fDistance), and the same walk finds “the k-th element”, inserts after the k-th element or deletes the k-th.
  • Duplicate keys: change insertion to always add a new node and duplicates are allowed. A search then finds the most recently inserted copy, and deletion removes the most recent one first.

What Java’s ConcurrentSkipListMap promises

Java’s standard library has a sorted map and a sorted set built on skip lists. The notes below follow the Java SE 25 documentation.

ConcurrentSkipListMap is described as implementing a concurrent variant of skip lists, with expected average log(n) time for containsKey, get, put, remove and their variants. Insertion, removal, update and access can run safely from multiple threads at once. Keys are sorted by natural ordering or by a Comparator supplied at construction. The documentation lists these caveats:

  • Iterators and spliterators are only weakly consistent.
  • Ascending views and their iterators are faster than descending ones.
  • Bulk operations such as putAll, equals, toArray, containsValue and clear are not guaranteed to be atomic. An iterator running concurrently with putAll might see only some of the added elements.
  • containsValue takes time linear in the map size, and its result may be inaccurate if the map changes while it runs.
  • null keys and values are not allowed, because a null return could not be reliably told apart from an absent element.

The documentation for ConcurrentSkipListSet, which is built on ConcurrentSkipListMap, warns that size is not a constant-time operation, unlike in most collections. Finding the current number of elements requires traversing them, and the result may be inaccurate if the set is modified during that traversal. If you tend to put size() in loop conditions, this collection is worth a second look.

The properties of the data structure and the promises of this API are separate things. The algorithms in Pugh’s cookbook do not handle concurrent access; the report points to a separate technical report, “Concurrent Maintenance of Skip Lists”, for that. What the Java documentation promises is the time costs and concurrent behavior above; this article does not cover how the class is implemented internally.

Report and documentation used

The documentation was checked on 14 October 2026.

Back to the blog