Skip List: O(log n) Search from a Linked List

A linked list is excellent at representing a sequence of connected nodes, but it is not naturally good at finding a particular value. Even when the list is sorted, a normal linked list usually has only one useful direction of movement: from the current node to the next node. To search for a key, the algorithm must follow links one by one until it finds the key or passes the position where the key should occur.

For a list containing n values, that search takes O(n) time in the worst case. A target near the end of the list, or a value that is absent but belongs near the end, may require visiting almost every node.

A skip list improves this behavior by adding sparse layers of forward links above the original sorted list. The bottom layer still contains every value in sorted order. Higher layers contain fewer nodes and act as shortcuts over the nodes below them. A search starts at a high layer, moves forward across large ranges when it is safe to do so, and drops to lower layers for increasingly precise navigation.

With appropriately sparse layers, a skip list provides expected O(log n) time for search, insertion, and deletion. It retains the sequential nature of a linked list while adding an index-like hierarchy for faster navigation.

The limitation of a sorted linked list​

Consider this sorted linked list:

3 -> 8 -> 12 -> 17 -> 21 -> 26 -> 31 -> 35 -> 40

Suppose we want to search for 31. Starting at the first node, the search examines values in order:

3, 8, 12, 17, 21, 26, 31

The sorted order is useful because the search can stop once it reaches a value greater than the target. However, sorted order does not give the algorithm a way to jump directly to the middle or to a distant node. The search still has to follow the links one at a time.

This is an important difference between a sorted array and a sorted linked list. A sorted array can use binary search because an array supports direct access to a middle position. Given an index, the program can reach the corresponding element in constant time. A linked list has no equivalent constant-time indexing operation. Reaching the middle requires traversing from the beginning.

Consequently, applying the usual binary-search idea directly to a linked list does not provide the same benefit. Finding the middle node repeatedly would itself require traversal. A skip list addresses this navigation problem by explicitly storing additional forward links.

The basic layered structure​

The bottom layer of a skip list contains the complete sorted sequence:

Level 0: 3 -> 8 -> 12 -> 17 -> 21 -> 26 -> 31 -> 35 -> 40

A higher layer contains only selected nodes from the level below:

Level 1: 3 ------> 12 ------> 21 ------> 31 ------> 40

An even higher layer contains fewer nodes:

Level 2: 3 -----------------> 21 -----------------> 40

The values remain sorted from left to right on every layer. A node that appears at a higher level also appears at the bottom level, because the upper layers are indexes over the complete sequence rather than separate collections of unrelated values.

The layers can be understood as levels of detail:

• Level 0 contains every element and provides the complete ordered list.
• Level 1 contains fewer elements and provides larger forward steps.
• Level 2 contains even fewer elements and provides broader navigation.
• Higher levels continue the same pattern when the structure is large enough.

A search uses the upper levels to skip over regions that cannot contain the target. It then moves downward when the next forward link would go too far.

Searching from the top down​

Suppose the structure is arranged as follows:

Level 2: head ----------------> 21 ----------------> 40
Level 1: head ------> 12 ------> 21 ------> 31 ------> 40
Level 0: head -> 3 -> 8 -> 12 -> 17 -> 21 -> 26 -> 31 -> 35 -> 40

To search for 31, begin at the head of the highest active level.

At level 2, move from head to 21. The next node is 40, which is greater than 31, so moving forward would pass the target. The search therefore stays near 21 and drops to level 1.

At level 1, the next node after 21 is 31, so the search moves to it and finds the target.

If the target were 35, the path would be slightly different. The search would move to 21 at level 2, drop to level 1 because 40 is too large, move to 31, and then observe that 40 is still too large. It would drop to level 0 and move from 31 to 35.

The general movement rule is:

Move forward while the next node exists and remains before the target. When the next node would pass the target, move down one level.

For exact lookup, the comparison is often expressed using < target while moving forward, followed by a check for equality on the bottom level. For insertion-position searches, the stopping condition may instead be based on the first node greater than or equal to the target. The exact comparison can vary, but the horizontal-then-downward navigation pattern remains the same.

Why sparse layers lead to logarithmic behavior​

The performance improvement comes from reducing the number of candidates at each higher level. Imagine that each layer contains approximately half as many nodes as the layer below it:

Level 0: about n nodes
Level 1: about n / 2 nodes
Level 2: about n / 4 nodes
Level 3: about n / 8 nodes

After repeatedly reducing the number of nodes by a constant factor, only a small number of nodes remain at the highest levels. The number of reductions needed to go from n candidates to a constant number is proportional to log n.

A skip list does not need every gap to be exactly the same size. In practice, its layers may be uneven. The key property is that the layers are sparse in a way that gives a good expected distribution of shortcuts. Some sections may have more nodes at a given level and other sections may have fewer, but the structure as a whole should become progressively smaller as the level increases.

The search therefore combines two kinds of movement:

horizontal movement: jump across several values using a shortcut
vertical movement: descend to a denser level for more precision

At the highest level, horizontal movement covers broad regions. Near the target, lower levels provide the missing detail. The expected total number of horizontal and vertical steps is logarithmic, giving expected O(log n) search time.

How the layers are constructed​

Conceptually, construction begins with an ordinary sorted linked list:

Level 0: 2 -> 5 -> 9 -> 14 -> 18 -> 23 -> 27 -> 32 -> 38 -> 44

Some nodes are selected to appear on the next layer:

Level 1: 2 ------> 9 ------> 18 ------> 27 ------> 38

A smaller group is selected for the layer above that:

Level 2: 2 -----------------> 18 -----------------> 38

The upper layers are sparse summaries of the lower layers. They do not need to duplicate the complete list. Their purpose is to provide enough forward links to guide searches efficiently.

A common way to select higher-level participation is a probabilistic promotion rule. A new node first appears at level 0. It may then be promoted to level 1 according to a probability, and if promoted, it may be promoted again to level 2 according to another application of the rule. This tends to produce many nodes at the bottom, fewer nodes above them, and progressively fewer nodes at still higher levels.

The important point is not the exact probability or a perfectly uniform pattern. The important point is the resulting shape: higher layers should be sparse enough to make large jumps, while lower layers preserve enough detail to finish the search.

This probabilistic organization explains the word expected in the complexity claim. The usual performance depends on the expected distribution of promoted nodes rather than on a rigid balancing rule that guarantees an exact shape after every update.

A search procedure in pseudocode​

A simplified exact-search procedure looks like this:

search(target):
    current = head at the highest active level

    while current has a lower level:
        while current.next at this level exists
              and current.next.key < target:
            current = current.next at this level

        current = current.down one level

    candidate = current.next at level 0

    if candidate exists and candidate.key == target:
        return candidate

    return not found

Different implementations may store vertical relationships explicitly or may represent the current position and its forward references in another way. The pseudocode captures the algorithmic idea rather than a particular memory layout.

At each level, the search advances only as long as the next key is still less than the target. When the next key is too large, descending preserves the correct region of the list. Because the lower layer contains more detail than the higher layer, the search never needs to move backward.

The importance of the bottom layer​

Every stored value appears at level 0. This layer is the authoritative ordered sequence and serves several purposes:

• It guarantees that every value can be reached.
• It provides the final step for exact searches.
• It supports complete sequential traversal.
• It supplies the neighboring nodes needed for insertion and deletion.

The upper levels are acceleration layers. They may skip over many values, but they do not have to contain every value. If a target lies inside a gap between two upper-level nodes, the search drops to a lower layer where that gap is represented in greater detail.

This division keeps the design conceptually simple. The skip list is still a complete linked list, but it has additional links that act as indexes over that list.

Inserting a value​

Insertion must preserve sorted order at level 0 and add the new node to any higher levels selected for it.

Suppose the bottom layer is:

3 -> 8 -> 12 -> 17 -> 21 -> 26 -> 31 -> 35

To insert 24, the correct location is between 21 and 26:

3 -> 8 -> 12 -> 17 -> 21 -> 24 -> 26 -> 31 -> 35

The algorithm first performs a skip-list search for the insertion position. While navigating, it records the last node visited at each level before the new key. These nodes are the predecessors at the levels that may need link updates.

For example, the recorded predecessors might conceptually look like this:

Level 2 predecessor: 21
Level 1 predecessor: 21
Level 0 predecessor: 21

If the new node is assigned only level 0, only the bottom-level links change. The update is:

21 -> 26

becoming:

21 -> 24 -> 26

If the new node is promoted to level 1 as well, the level-1 sequence is updated too. At each affected level, the same local transformation is applied:

predecessor -> successor

becomes:

predecessor -> new node -> successor

The search is what makes this efficient. The algorithm does not scan the entire bottom list to find the insertion point, and it already knows where the new node belongs at each participating level.

Insertion complexity​

Finding the insertion position takes expected O(log n) time. The subsequent link changes involve the levels assigned to the new node. With sparse levels and the usual promotion behavior, the expected total insertion cost remains O(log n).

The operation must still update all relevant levels. Updating only level 0 would leave the upper indexes unaware of the new node, which could make their shortcuts inconsistent with the bottom list.

Deleting a value​

Deletion uses almost the same navigation as insertion. The algorithm searches for the target while recording the predecessor at every level where the target may occur.

At a particular level, deletion changes:

predecessor -> target -> successor

to:

predecessor -> successor

The target must be bypassed at level 0 because the bottom layer contains the complete data. It must also be bypassed at every higher level where it was promoted.

For example, before deleting 21:

Level 1: 3 ------> 12 ------> 21 ------> 31
Level 0: 3 -> 8 -> 12 -> 17 -> 21 -> 26 -> 31

After deletion:

Level 1: 3 ------> 12 -----------------> 31
Level 0: 3 -> 8 -> 12 -> 17 -> 26 -> 31

The upper-level shortcut is repaired by connecting 12 directly to 31.

If deletion removes the only useful node from the highest active layer, the structure may reduce its active height. This keeps future searches from starting in empty or unnecessary levels. The exact mechanics depend on the implementation, but the conceptual requirement is straightforward: every layer must continue to represent a valid sorted subsequence of the bottom list.

Deletion complexity​

The search for the target takes expected O(log n) time. Once the target and its predecessors have been identified, deletion performs a limited number of pointer changes. Therefore, deletion also has expected O(log n) running time under the intended sparse-layer behavior.

Expected time is not a strict worst-case guarantee​

The phrase expected O(log n) is essential when describing skip lists.

A plain linked list has a clear worst-case bound of O(n) for key-based search. A skip list normally performs much better because its index layers are expected to be sparse and well distributed. However, a particularly unfavorable arrangement of promoted nodes could provide poor shortcuts. In an extreme case, the structure could behave much more like a plain linked list.

The normal analysis assumes an appropriate promotion process and discusses the average behavior over the resulting layouts. Under that assumption, the number of levels and the amount of horizontal movement are logarithmic in expectation.

A practical complexity summary is:

The skip list does not make sequential traversal asymptotically faster. Its benefit is efficient navigation to a key or to a position in the ordered sequence.

Space usage and the indexing trade-off​

A basic linked-list node needs a key and a link to the next node. A skip-list node may need several forward references because it can participate in multiple levels.

Those extra links consume memory, but they provide shortcuts. Under common sparse-layer behavior, the total number of stored links remains expected O(n), so total space is expected linear in the number of elements. The constant factor is larger than for a simple linked list because the structure stores additional navigation information.

This is a classic time-space trade-off:

plain linked list: less indexing overhead, linear key-based search
skip list: extra forward links, expected logarithmic key-based operations

The skip list does not store every possible connection. Doing so would require excessive space. Instead, it stores a carefully limited hierarchy of sparse links that provides most of the navigation benefit at expected linear total space.

A useful mental model: express lanes​

An express-lane analogy makes the navigation pattern intuitive. Imagine that the bottom road visits every location:

A -> B -> C -> D -> E -> F -> G -> H -> I

A higher road visits only selected locations:

A ------> C ------> E ------> G ------> I

An even faster road visits fewer locations:

A -----------------> E -----------------> I

To reach H, begin on the highest road. Move from A to E, but do not move to I because I would pass the destination. Drop to the middle road, move to G, and then descend to the bottom road to reach H.

This analogy captures the two rules used by a skip-list search:

1. Move forward on the current layer when the next shortcut does not pass the target.
2. Descend when the next shortcut would go too far.

The upper lanes reduce the amount of sequential travel. The bottom lane provides the exact route when the remaining gap is small.

Node representation​

A conceptual skip-list node contains a key and an array or collection of forward references:

Node:
    key
    forward[0]
    forward[1]
    forward[2]
    ...

forward[0] points to the next node in the complete bottom-level list. A forward[1] reference means that the node participates in the next layer. Additional references represent higher layers.

A head or sentinel node is often used as the starting point for every level. The sentinel does not need to represent a user value. Its purpose is to make navigation and updates uniform, particularly when operating on the smallest key or an empty list.

The representation makes the layered structure visible in the data model: each node has a height, and its forward-reference collection contains links for the levels in which it participates.

The exact representation can vary. Some implementations maintain explicit downward references between levels; others keep a single node object with multiple forward pointers. The algorithmic idea is the same: at each level, the current position has a forward link that may skip over nodes present only in lower levels.

Searching for a missing value​

The skip-list search pattern is useful even when the target is not present. Suppose the ordered values are:

5 -> 11 -> 18 -> 24 -> 30

If the search target is 20, the algorithm can locate the gap between 18 and 24. The upper levels help it reach the predecessor 18 without scanning from 5 through every node.

At the bottom level, the algorithm examines the next node after the final predecessor. There are two possible outcomes:

• The next node has key 20, so the search succeeds.
• The next node has a key greater than 20, or there is no next node, so 20 is absent and its insertion position has been found.

This is why the same navigation procedure can support exact lookup, predecessor lookup, successor lookup, and insertion-position discovery. The differences are mainly in the comparison and in what the caller does with the final neighboring nodes.

Duplicate keys and comparison rules​

A skip list needs a clear policy for duplicate keys. The layered structure itself does not require one particular choice. An implementation may reject duplicates, allow multiple nodes with the same key, or associate a key with multiple values.

The navigation rule must match the selected policy. For example, moving forward while the next key is strictly less than the target tends to stop before the first equal key. Allowing movement while the next key is less than or equal to the target tends to move past equal keys and can help locate a later occurrence.

The important requirement is consistency. Every layer must preserve the same ordering, and search, insertion, and deletion must use compatible comparison rules. If different operations interpret equal keys differently, the structure can produce surprising positions or remove the wrong occurrence.

Duplicate handling is an implementation policy rather than a change to the central skip-list idea. Sparse upper layers still provide shortcuts, and level 0 still contains the complete ordered sequence.

Practical implementation checklist​

When implementing or evaluating a skip list, consider the following questions.

1. What is the ordering key?​

Define how two nodes are compared. The ordering must be stable across all layers, because every upper layer is a sorted subsequence of the bottom layer.

2. Are duplicate keys allowed?​

Choose whether duplicates are rejected, stored separately, or grouped under one key. Document how searches identify the first, last, or any matching value.

3. How is the head represented?​

A sentinel head node usually simplifies boundary cases. It gives every level a consistent starting position and avoids special handling for inserting before the current first value.

4. How are levels selected?​

The promotion rule should create sparse upper layers. The expected performance depends on the resulting distribution, so a rule that frequently promotes too many nodes can reduce the effectiveness of the index hierarchy.

5. How is the active height maintained?​

The structure needs to know which levels are currently active. If the highest level becomes empty after deletions, reducing the active height avoids unnecessary navigation through unused layers.

6. What operations are required?​

Exact search, insertion by key, deletion by key, predecessor search, successor search, and ordered traversal can share the same core navigation but may use different stopping conditions.

7. What guarantee is acceptable?​

Skip lists are normally described using expected complexity. If an application requires a strict worst-case bound, that requirement should be considered separately from the normal skip-list analysis.

Common implementation mistakes​

Starting every search at level 0​

If the search always begins at the bottom list, it never uses the index layers and remains O(n). A skip-list search should start at the highest active level and descend only when necessary.

Moving past the target​

At each layer, the algorithm must check the next node before advancing. If the next key would pass the target, the search should descend instead. Moving too far can cause the algorithm to lose the correct predecessor position.

Updating only the bottom level​

An insertion or deletion that changes level 0 but leaves upper levels unchanged makes the shortcuts inconsistent. Every level containing the affected node must be updated.

Breaking sorted order​

Each layer must remain sorted. A shortcut is valid only when it moves forward through the same key order as the bottom layer. A single incorrect link can cause searches to skip valid regions or return an incorrect position.

Treating expected complexity as guaranteed complexity​

The usual logarithmic claim depends on the expected shape of the sparse layers. Documentation and performance discussions should preserve the word “expected” rather than presenting the result as an unconditional worst-case guarantee.

Ignoring boundary cases​

Empty lists, one-element lists, insertion before the first value, insertion after the last value, deletion of the first value, deletion of the last value, and searches for absent values all exercise different link boundaries. Sentinel nodes and predecessor tracking make these cases easier to handle consistently.

Why the skip-list idea is useful​

The skip list illustrates a broad algorithmic technique: start with a simple sequential representation and add a hierarchy of sparse indexes to accelerate navigation.

The original list remains complete and easy to traverse. The added layers do not need to duplicate every element. They only need enough links to guide a search toward the correct region. This lets the structure combine the linked-list model with expected logarithmic key-based operations.

The idea also shows that logarithmic search does not depend on one specific representation. Binary search uses direct array indexing. Balanced search trees use branching structure. Skip lists use multiple sorted linked layers. These structures differ internally, but they share a goal: reduce the number of candidates examined during a search.

For software engineers, the practical lesson is to look for useful navigation information that can be stored alongside the primary data. A plain sequence may be easy to update but slow to search. A sparse index can preserve the sequence while making important positions easier to reach.

Summary​

A sorted linked list contains values in order, but finding a key normally requires a linear traversal. Its links describe adjacency, not distant navigation. A skip list adds sparse forward-link layers above the complete bottom-level list.

During a search, the algorithm begins at the highest active level. It moves forward while the next node remains before the target, then descends when the next shortcut would pass the target. Repeating this process narrows the search region from coarse navigation to precise bottom-level movement.

Insertion and deletion use the same search path. They record the predecessor at each relevant level and then insert or bypass the affected node in every layer where it participates. Under an appropriate sparse-layer construction, search, insertion, and deletion each take expected O(log n) time. The total space usage is expected O(n), with additional links providing the indexing overhead.

The key takeaways are:

• A plain sorted linked list provides O(n) key-based search.
• The bottom skip-list layer still contains every value.
• Higher layers act as sparse indexes and shortcuts.
• Searches move horizontally across a layer and vertically downward.
• Expected sparse layers reduce search, insertion, and deletion to O(log n).
• Extra forward links increase space usage but remain expected linear in total.
• Insertions and deletions must update every affected level.
• The skip-list guarantee is expected rather than an unconditional worst-case bound.

A skip list is therefore a clear example of how additional indexing links can transform a simple sorted linked list into a structure with expected logarithmic-time navigation.