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

A skip list is a sorted linked list enhanced with additional, sparser linked-list lanes. The bottom lane contains every stored element in sorted order. Higher lanes contain selected elements and act as shortcuts across the complete list.

This extra structure changes how navigation works. A plain linked list must follow one pointer at a time, even when the target is far away. A skip list can move across a high lane, approach the target quickly, and then descend to lower lanes for precision. With a suitable randomized height policy, search, insertion, and deletion take expected $O(\log n)$ time.

The central idea is straightforward:

• A plain sorted linked list searches in $O(n)$ time.
• A skip list adds sparse index lanes above the complete list.
• Search moves forward while the next key is still smaller than the target.
• When the next key would pass the target, search drops to a lower lane.
• Randomized node heights make the upper lanes progressively sparser.
• The resulting search, insertion, and deletion costs are expected $O(\log n)$.

The word expected matters. A skip list does not guarantee that every possible arrangement has logarithmic height. Its performance depends on how extra levels are selected. Under the usual randomized construction, the average behavior over the random choices is logarithmic.

1. The starting point: a sorted linked list​

Consider a sorted linked list containing the following keys:

3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42

Each node stores a key and a pointer to the next node. To search for $29$, the algorithm starts at $3$, compares the current key with the target, and follows pointers until it reaches $29$. Searching for a key near the end requires visiting many nodes.

For a list containing $n$ nodes, a search may inspect nearly all $n$ nodes. The search therefore has linear complexity, written as $O(n)$.

Sorting alone does not solve this problem. A sorted array can support binary search because an array provides constant-time access to an indexed middle position. A linked list has no such direct access. Reaching the middle still requires following links from the beginning.

A skip list addresses this limitation by storing additional links. These links do not remove the complete sorted list. Instead, they provide carefully arranged shortcuts through it.

2. Adding sparse index lanes​

The lowest lane, usually called level $0$, contains every key. Above it are shorter lanes containing selected nodes. A conceptual skip list might look like this:

Level 2:  -inf ----------------------------> 21 ----------------------------> +inf
Level 1:  -inf ------------> 14 ----------> 21 ------------> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42 -> +inf

The higher lanes are subsequences of level $0$:

• Level $0$ contains the complete sorted sequence.
• Level $1$ contains fewer nodes and provides larger shortcuts.
• Level $2$ contains still fewer nodes and provides even larger shortcuts.
• Additional levels, when present, become progressively sparser.

The exact keys appearing in the upper lanes can vary. The important structural property is that every node appearing at a higher level also appears at every lower level. A node on level $2$ must also be present on levels $1$ and $0$.

A useful mental model is a transportation network. Level $0$ is a local road that visits every location. Level $1$ is an express route that stops less frequently. Level $2$ is an even faster route with fewer stops. A search begins on an express route and changes to slower routes when it needs more precise positioning.

The lanes are not separate, unrelated lists. They are multiple views of one ordered structure. Every forward link points to a later key in sorted order, and every upper lane skips over a portion of the lane below it.

3. Node shape and structural invariants​

A normal linked-list node has one forward pointer. A skip-list node can have several forward pointers, one for each level on which it appears. If a node has height $3$, it participates in levels $0$, $1$, and $2$.

Conceptually, its representation is:

Node:
    key
    forward[0]
    forward[1]
    ...
    forward[h - 1]

Here, $h$ is the node's height. The node has a level-$0$ pointer, a level-$1$ pointer, and so on through level $h-1$.

A correct skip list maintains several invariants:

1. Every level is sorted by key.
2. Level $0$ contains every stored key.
3. A node present at level $i$ is also present at every level below $i$.
4. A forward pointer at level $i$ points to a later node in that same level or to the end marker.
5. Traversing level $i$ produces a subsequence of the keys in level $i-1$.
6. Forward pointers never move backward.

These rules make the upper lanes trustworthy shortcuts. If a search has reached a node that is smaller than the target, it can safely continue forward or descend without revisiting earlier nodes.

Implementations commonly use a special head or sentinel node. The sentinel is not an ordinary stored key. It provides a starting position at every level and simplifies boundary cases. For example, inserting a new smallest key can use the head as its predecessor rather than requiring separate logic for the first ordinary node.

An implementation may also use an end sentinel or null references to represent the end of each lane. This is a representation choice; the algorithm needs a reliable way to recognize that no further node exists.

4. Why the hierarchy must have multiple levels​

Suppose a linked list has one additional lane containing roughly every second node:

Upper:  3 ------------> 14 ------------> 29 ------------> 42
Lower:  3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42

The upper lane provides useful shortcuts, but it still contains a linear number of nodes as the list grows. Searching it can still require order $n$ steps.

The improvement comes from indexing the index lane. A lane containing approximately half as many nodes can itself be represented by another lane containing approximately half as many nodes again. The approximate sizes become:

The number of levels needed before the lane contains approximately one node is related to the logarithm of $n$. If each level reduces the number of candidates by a factor of two, then the height $h$ satisfies

Rearranging gives

so

A skip list does not need perfectly regular lanes. Randomized heights usually produce an irregular structure. Nevertheless, the expected number of nodes decreases geometrically as the level increases, which provides the same logarithmic scaling in expectation.

5. Searching: move forward, then drop down​

Skip-list search follows a greedy movement rule. Begin at the head on the highest active level. At the current level, inspect the next node:

• If the next key is smaller than the target, move forward.
• If the next key equals the target, report success.
• If the next key is greater than the target, remain at the current node and drop to the next lower level.

When the search drops, it keeps the same current node. That node is already known to be the last visited key that is smaller than the target at the current point. Because the list is sorted, there is no reason to move backward.

Using the earlier structure, search for $29$ proceeds as follows:

Level 2:  -inf ----------------------------> 21 ----------------------------> +inf
Level 1:  -inf ------------> 14 ----------> 21 ------------> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42 -> +inf

1. Start at the head on level $2$.
2. The next key is $21$, which is smaller than $29$, so move to $21$.
3. The next level-$2$ key would pass the target, so drop to level $1$ while staying at $21$.
4. The next level-$1$ key is $35$, which is greater than $29$, so drop to level $0$.
5. The next level-$0$ key is $29$, so the search succeeds.

Search for $30$ follows almost the same route. It reaches $29$ on level $0$, then sees that the next key is $35$. Because $35$ is greater than $30$, the search reports that $30$ is absent. The gap between $29$ and $35$ is also the correct insertion position for $30$.

A language-independent outline is:

current = head at the highest active level
while a level is available:
    next = current.forward[level]
    if next exists and next.key < target:
        current = next
    else if next exists and next.key == target:
        return found
    else if level > 0:
        level = level - 1
    else:
        return not found

The important distinction is between horizontal and vertical movement. A horizontal move follows a forward pointer within one lane. A vertical move lowers the lane while preserving the current position in the ordered sequence.

6. Why search is expected $O(\log n)$​

The expected analysis has two parts: the number of levels and the amount of horizontal movement on each level.

Suppose a node is allowed to continue to the next level with fixed probability $p$, where $0 < p < 1$. Informally, the expected number of nodes reaching level $i$ is proportional to

The highest useful level is reached when the expected number of nodes on that level is close to one:

This means

Taking logarithms shows that $h$ grows proportionally to $\log n$, because $p$ is a fixed constant below one.

At each level, the search normally advances through only a bounded expected number of nodes before the next node would pass the target. It then drops down one level. Therefore, the expected work is approximately

This is the main performance advantage of the skip list. The search does not scan the complete bottom lane. It performs short scans across a logarithmic number of lanes.

The qualification is important. A particular random arrangement may contain an unusually long gap or an unexpectedly tall structure. The expected bound is derived over the random choices used to assign node heights. It is not an unconditional guarantee that every individual layout will have logarithmic search time.

7. Insertion: search first, then splice​

Insertion begins by searching for the position where the new key belongs. During this search, the algorithm records the last node visited at each level before the insertion position. These nodes are often stored in an update array.

Suppose the current bottom lane is:

3 -> 8 -> 14 -> 21 -> 35 -> 42

To insert $29$, the search identifies $21$ as the predecessor and $35$ as the successor at level $0$. It also records predecessors at any higher levels where the new node may be inserted.

Assume that the new node receives height $2$. It will therefore participate in levels $0$ and $1. Before insertion, the relevant lanes might look like this:

Level 1:  -inf ------------> 14 ----------> 21 ------------> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 35 -> 42 -> +inf

After insertion, the new node is spliced into both lanes:

Level 1:  -inf ------------> 14 ----------> 21 -----> 29 -> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42 -> +inf

At each level, the local transformation is:

predecessor -> successor

becoming:

predecessor -> new node -> successor

For one level, the safe pointer-update order is:

new.forward[level] = predecessor.forward[level]
predecessor.forward[level] = new

The old successor is saved in the new node before the predecessor's pointer is redirected. This preserves access to the remainder of the lane.

If the new node has height $h$, the algorithm performs this splice on levels $0$ through $h-1$. It does not need to appear on every existing level. A node of height $1$, for example, appears only in level $0$.

The search phase costs expected $O(\log n)$. The splice phase costs $O(h)$. Under the usual randomized height policy, the expected height of one node is constant, so the total expected insertion cost is

The bottom-level sorted-order invariant is preserved because the new node is placed between its correct predecessor and successor. The layered invariant is preserved because the node is added to every level represented by its height.

8. Deletion: unlink the target at every level​

Deletion also begins with a search. If the target is found, the algorithm removes the target from every level in which it appears.

Suppose the target is $29$ and has height $2$:

Before:
Level 1:  -inf ------------> 21 ------------> 29 ------------> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 29 -> 35 -> 42 -> +inf

The target is removed from both levels:

After:
Level 1:  -inf ------------> 21 ----------------------------> 35 ------------> +inf
Level 0:  -inf -> 3 -> 8 -> 14 -> 21 -> 35 -> 42 -> +inf

At each level, the local transformation is:

predecessor -> target -> successor

becoming:

predecessor -> successor

The target must be removed from every level it occupies. Removing it only from level $0$ would leave upper-level pointers referring to a node that is no longer represented in the complete list. Removing it only from an upper level would leave the key in the bottom lane. Both situations violate the layered representation.

The search and update work together take expected $O(\log n)$ time. The number of links to update equals the target's height, whose expected value is constant under the standard randomized model. Therefore, deletion also has expected $O(\log n)$ complexity.

After deletion, the highest active level may become empty. The implementation can lower its recorded top level so that future searches do not begin on unused lanes. This is bookkeeping; it does not change the stored keys.

9. Randomized heights and expected performance​

A skip list needs a rule for deciding how many levels each new node receives. The exact probability is a design choice, but the general principle is that higher levels should be less common than lower levels.

A common conceptual rule is:

1. Give every new node level $0$.
2. Repeatedly flip a biased random choice.
3. If the choice succeeds, promote the node to the next level.
4. Stop when the choice fails.

With a fixed continuation probability $p$, tall nodes are rare. Most nodes remain short, fewer nodes reach level $1$, still fewer reach level $2$, and so on.

This distribution supplies two useful properties:

1. The expected height of one node is bounded by a constant.
2. The expected number of nodes at level $i$ decreases roughly like $np^i$.

The first property supports expected linear space. The second supports an expected logarithmic number of levels and short horizontal gaps.

Randomization does not guarantee a perfectly balanced structure in every run. A particular run can contain an unusually long gap. That is why the precise complexity statement is expected $O(\log n)$ rather than guaranteed $O(\log n)$.

The distinction should appear in documentation and complexity tables. Omitting the word expected can hide an important assumption about the height-selection process.

10. Complexity summary​

For a skip list using a suitable randomized height policy, the common expected bounds are:

The expected space bound follows from the geometric decrease in the number of nodes at higher levels. If the expected number of forward references per node is constant, the total number of references is proportional to $n$.

A complete traversal still takes $O(n)$ time. The simplest traversal follows level $0` from left to right, visiting every stored key exactly once. This is the appropriate cost when the operation must produce all$n$ values.

These bounds describe the usual randomized construction. An unusual height assignment can behave worse, even though the expected behavior remains logarithmic over the random choices.

11. Skip lists compared with plain sorted linked lists​

A plain sorted linked list has a simple, uniform node representation. Once the correct predecessor is known, insertion and deletion require only local pointer changes. The difficulty is finding that predecessor. Without extra links, the list normally must be scanned from the beginning, giving $O(n)$ search, insertion, and deletion in the comparison-based setting.

A skip list retains the linked-list foundation while adding navigation links. Its trade-offs include:

• Extra forward pointers consume additional memory.
• Nodes can have different heights.
• The update logic must maintain several levels instead of one.
• Performance is probabilistic when random heights are used.

In return, expected search cost falls from $O(n)$ to $O(\log n)$. The upper lanes act like an index maintained alongside the complete sorted sequence.

The bottom lane remains necessary. It contains every key, supports complete traversal, and provides the final level where searches can make precise decisions. The upper lanes accelerate navigation but do not replace the complete representation.

12. A complete search and update example​

Start with this sorted list:

4 -> 9 -> 16 -> 23 -> 31 -> 38 -> 45

Assume the nodes have been assigned heights that produce the following lanes:

Level 2:  -inf ----------------------------> 23 ----------------------------> +inf
Level 1:  -inf ------------> 16 ----------> 23 ------------> 38 ------------> +inf
Level 0:  -inf -> 4 -> 9 -> 16 -> 23 -> 31 -> 38 -> 45 -> +inf

Searching for 31​

Start on level $2$. The next key is $23$, so move to $23$. The next level-$2$ key would pass $31$, so drop to level $1$. The next level-$1$ key is $38$, which is too large, so drop to level $0$. The next level-$0$ key is $31$, so the search succeeds.

The higher lanes narrowed the search to the neighborhood between $23$ and $38$. Only then did the search inspect the bottom-level key $31$.

Searching for 34​

The search again reaches $23$. On level $1$, the next key is $38$, so it drops to level $0. It moves past$31$and then sees$38$. Since$38$is greater than$34$, the search reports absence. It has also found the insertion gap between$31$and$38$.

Inserting 34​

Suppose the new node receives height $1$. It is inserted only into level $0$:

Level 1:  -inf ------------> 16 ----------> 23 ------------> 38 ------------> +inf
Level 0:  -inf -> 4 -> 9 -> 16 -> 23 -> 31 -> 34 -> 38 -> 45 -> +inf

The upper levels remain valid. They do not need to contain every key; only level $0$ must contain the complete set.

Deleting 23​

If $23$ has height $3$, deletion redirects the predecessor's pointer around it on levels $0$, $1$, and $2$. The remaining lanes are still sorted subsequences of level $0$.

This example shows that all three main operations use the same navigation idea. Search finds the predecessor at each relevant level. Insertion adds a node between predecessor and successor. Deletion connects predecessor directly to successor.

13. Boundary cases and invariants to protect​

Middle-of-the-list examples show the basic idea, but a robust implementation must also handle boundaries.

Inserting before the first key​

If the new key is smaller than every existing key, the head sentinel is the predecessor at each level used by the new node. The new node becomes the first ordinary node in those lanes.

Inserting after the last key​

If the new key is larger than every existing key, the predecessor at each relevant level points toward the end marker. The new node is linked immediately before the marker.

Searching an empty structure​

The head sentinel has no ordinary successor containing a key. The search descends through the available levels and reports absence without trying to access a nonexistent ordinary node.

Deleting the only ordinary node​

The target's forward references point to the end marker at every level it occupies. Redirecting the head's references to those successors makes the lanes empty. The recorded top level can then be reduced.

Duplicate keys​

A skip list implementation must choose a policy for duplicate keys. It may reject duplicates, store multiple equal entries, or define a consistent position among equal keys. The supplied structure description does not require one particular policy. What matters is that searching and updating follow the selected policy consistently at every level.

The main invariant checklist is:

• Level $0$ contains exactly the stored entries.
• Every level is sorted.
• Every upper-level entry also occurs below it.
• Forward pointers never point backward.
• Every update changes all levels represented by the affected node.

If these conditions remain true, later searches can safely use the upper lanes.

14. How an animation can show the structure​

An animation makes the changing shape of a skip list easier to understand than a single static diagram. A useful sequence is:

1. Show the original sorted linked list.
2. Add a sparse lane above it.
3. Add another, even sparser lane.
4. Highlight a search moving forward on a high lane.
5. Show the search dropping when the next key would pass the target.
6. Highlight the links changed by insertion.
7. Highlight the links that bypass a deleted node.

The visual should distinguish horizontal movement from vertical movement. A horizontal move follows a forward pointer within one level. A vertical drop changes the level while keeping the current ordered position.

The animation should also avoid implying that the lanes must have perfectly regular spacing. Regular spacing is useful for teaching the concept, but randomized skip lists usually have irregular gaps. The required property is progressive sparsity, not exact visual uniformity.

15. Practical implementation plan​

A language-independent implementation can be organized around a few components.

Node representation​

Each node stores its key and a collection of forward references. The length of that collection is the node's height.

Head and active height​

The structure stores a head sentinel with forward references for the maximum supported level. It also records the highest level currently in use so searches do not begin on permanently empty lanes.

Height selection​

A randomized helper chooses the height of every new node. Higher heights should be less frequent than lower heights so that upper lanes remain sparse.

Search with predecessors​

The search routine can return whether a key was found while also recording the predecessor at every level. These predecessors are exactly the nodes whose references must change during insertion or deletion.

Local splicing​

Insertion first assigns the new node's forward references and then redirects predecessor references. Deletion redirects each predecessor around the target.

Level cleanup​

After a deletion, empty top levels can be removed from the active-height bookkeeping. This prevents future searches from starting on unused lanes.

Useful tests include the empty list, a one-node list, insertion at both ends, deletion at both ends, absent-key searches, and deletion that empties the highest active level.

16. Common misunderstandings​

A skip list is not an array with indexes​

Its shortcuts are links between nodes, not direct numeric positions. Moving forward means following references rather than accessing a contiguous memory position by index.

Every node does not appear on every level​

Only level $0$ contains every node. A node's height determines the highest level on which it appears.

Higher levels are not independent structures​

They can be traversed as sorted lists, but structurally they are subsequences of the lower levels. Their nodes and links must agree with the bottom-level representation.

Expected $O(\log n)$ is not guaranteed $O(\log n)$​

The expected bound depends on the randomized height distribution. A particular layout may have longer-than-usual gaps.

Local pointer changes do not make insertion constant time​

Once the predecessor is known, splicing is local. Finding that predecessor is the search phase and costs expected $O(\log n)$.

The bottom lane is not redundant​

It provides the complete sorted sequence, supports full traversal, and serves as the final precise level for search and update operations.

17. Practical takeaways​

A skip list can be understood as a sorted linked list plus a hierarchy of sparse shortcuts. Its most important rules are structural:

• Keep every key in level $0$.
• Make higher levels progressively sparser.
• Begin searches at the highest active level.
• Move forward while the next key remains below the target.
• Drop one level when the next key would pass the target.
• For insertion, record predecessors and splice the new node into every level it occupies.
• For deletion, bypass the target at every level it occupies.
• Describe the performance as expected $O(\log n)$ when randomized heights are used.
• Preserve sorted order and cross-level containment after every update.

The complexity comes from geometric sparsity. If each level contains a constant fraction of the nodes in the level below, only $O(\log n)$ levels are needed. If the search performs expected constant horizontal work per level, the complete route is expected logarithmic.

Starting with an $O(n)$ sorted linked list, a skip list adds carefully organized redundancy: extra links that repeat selected nodes at higher levels. That redundancy requires expected $O(n)$ space, but it changes navigation from a full scan into a sequence of short scans and downward steps. The result is a flexible linked structure with expected $O(\log n)$ search, insertion, and deletion.