Algorithms and data structures · Intermediate

Build ordered shortcuts with a skip list

Trace predecessor links during insertion and deletion, separating randomized expectations from a fixed-height teaching implementation.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Layer shortcuts over an ordered list
  2. Move right until descending is necessary
  3. Splice only the participating levels
  4. Execute deletion and duplicate checks
  5. Separate expected link count from bytes
  6. Use the bottom level for range enumeration
  7. Change promotion probability deliberately
  8. Exercise: draw the predecessor updates
  9. Ask Logeia about this articleCheck your understanding

Layer shortcuts over an ordered list

A skip list adds shortcut links above a sorted linked list. Suppose the bottom contains ten, twenty, thirty, forty, fifty and sixty, while a higher level contains ten, thirty and sixty. To find fifty-five, move through ten and thirty, stop before overshooting to sixty, then descend. Every stored key appears at the bottom; higher levels only accelerate navigation.

Instead of rotating a tree to restore balance, insertion chooses a node height randomly. A fixed seed makes a teaching trace reproducible but does not guarantee favorable input or worst-case speed. Our example implements an integer set: duplicate insertion returns False without creating another node. Establish membership and duplicate semantics before discussing expected costs, since a multiset would need a different storage and deletion contract.

Move right until descending is necessary

Start at the highest level and move right while the next key is strictly smaller than the target. If the next link is absent or would overshoot, descend and repeat. At the bottom, the following node is either the target or its insertion successor. Using a strict comparison also identifies the predecessor needed for updates. Save one predecessor per level in an update array.

The head sentinel has links for every level but its placeholder key is never compared with real keys. Stored keys are integers in this implementation. A node reached along a level necessarily participates in that level and has the corresponding link slot. Preserve that invariant when descending and updating; arbitrary movement to a shorter node followed by reading a higher-level slot would be invalid.

Splice only the participating levels

To insert twenty-five, first find its predecessor at every level. For a new node of height two, redirect the bottom two levels: point the new node at the former successor, then point each predecessor at the new node. Higher levels remain untouched. Existing heights are not regenerated. The code extends height with probability one half and caps the teaching structure at eight levels.

That fixed cap matters. The general expected O(log n) analysis does not apply unchanged to arbitrarily large n with only eight levels. A scalable implementation needs an appropriate height policy or growth rule. State the random choices and level assumptions used by an analysis, and keep them separate from this bounded example tested over forty possible keys. Reproducible testing is not a proof of asymptotic balance.

Height-two insertionLinks changedOther condition
Level 0update[0] and new next[0]Preserve sorted order
Level 1update[1] and new next[1]Preserve sorted order
Levels 2+UnchangedNew node does not participate

Execute deletion and duplicate checks

Deletion first collects predecessors and confirms that the bottom successor is the target. If absent, return False. Otherwise bypass the target at every level it occupies. This Python example is single-threaded: no concurrent reader can still hold a removed node while another thread reuses its storage. A short pointer update does not make the structure safe for concurrent access or memory reclamation.

The included run performs one thousand seeded insert/delete choices and checks every possible key against a Python set after each operation. Return values must also match whether membership changed. Separate seeds control node heights and the operation sequence, making failures reproducible without conflating layout and workload. These functional checks do not certify lock-free progress or concurrent correctness.

The introductory upper lane is illustrative. Inserting ten through sixty with seed seven in the published code produces the table: only forty occupies levels three through five, and levels six and seven are empty. Distinguish this executed random layout from the hand-chosen introductory one.

python
import random
class Node:
    def __init__(self,key,height):self.key=key;self.next=[None]*height
class SkipList:
    def __init__(self,seed=7):self.head=Node(None,8);self.rng=random.Random(seed)
    def previous(self,key):
        update=[self.head]*8;node=self.head
        for level in range(7,-1,-1):
            while node.next[level] is not None and node.next[level].key<key:node=node.next[level]
            update[level]=node
        return update
    def contains(self,key):
        node=self.previous(key)[0].next[0]
        return node is not None and node.key==key
    def insert(self,key):
        update=self.previous(key)
        if update[0].next[0] is not None and update[0].next[0].key==key:return False
        height=1
        while height<8 and self.rng.random()<0.5:height+=1
        node=Node(key,height)
        for level in range(height):node.next[level]=update[level].next[level];update[level].next[level]=node
        return True
    def discard(self,key):
        update=self.previous(key);node=update[0].next[0]
        if node is None or node.key!=key:return False
        for level in range(len(node.next)):update[level].next[level]=node.next[level]
        return True
if __name__=='__main__':
    demo=SkipList(seed=7)
    for key in [10,20,30,40,50,60]:demo.insert(key)
    for level in range(7,-1,-1):
        keys=[];node=demo.head.next[level]
        while node is not None:keys.append(node.key);node=node.next[level]
        if keys:print('demo level=',level,'keys=',keys)
    s=SkipList();reference=set();rng=random.Random(11)
    for _ in range(1000):
        key=rng.randrange(40)
        if rng.randrange(2):assert s.insert(key)==(key not in reference);reference.add(key)
        else:assert s.discard(key)==(key in reference);reference.discard(key)
        assert [x for x in range(40) if s.contains(x)]==sorted(reference)
    print('seed=7/11 operations=1000 reference=set passed')
Level (zero is bottom)Keys after inserting 10..60 with seed7
540
440
340
210,30,40,50
110,20,30,40,50
010,20,30,40,50,60

Separate expected link count from bytes

With an unbounded geometric height and promotion probability one half, expected height is one plus one half plus one quarter and so on, which equals two. That gives an expected linear total number of links. Link count is not an exact Python byte estimate: object headers, list storage and integer objects contribute additional memory. A capacity measurement must identify which representation it counts.

If every node stays at the bottom, search degenerates to a linear linked-list walk. Expected behavior under random heights is not a deterministic logarithmic worst-case guarantee. Compare balanced trees when worst-case bounds matter. Skip lists also support ordered range traversal at the bottom, so choose based on the full operation mix and storage costs rather than one favorable lookup timing.

Use the bottom level for range enumeration

To return every key from thirty inclusive to fifty-five exclusive, first search for the starting predecessor, then follow bottom-level links until the upper bound. Staying on a shortcut level would skip keys that never appear there. Search shortcuts and complete enumeration have different jobs. Map inclusive and exclusive endpoints to the corresponding comparisons.

Returning r keys adds output work to the starting search cost. An expected logarithmic lookup statement does not make an arbitrarily long range enumeration logarithmic. The fixed-eight-level caveat still applies to the small code. Comparing all bottom-level memberships with a reference set helps verify that changes to shortcut layout preserve the actual represented set.

Change promotion probability deliberately

Reducing promotion probability from one half to one quarter lowers expected link count but also makes upper levels sparser. Link count alone cannot establish which version searches faster. Count horizontal steps and descents using the same inserted keys and query set. The unbounded expected-height series is1+p+p²+…=1/(1−p).

Changing randomness must not change represented membership. Check both layouts against the same reference before comparing traversal. Save level cap, probability, seed and operation trace to reproduce layout separately from function. A visually attractive short list does not establish a universal timing advantage. This is another instance of separating a randomized expectation from an observed structure and the actual contract it must preserve.

Exercise: draw the predecessor updates

Start with bottom keys ten, twenty, thirty, forty and upper keys ten, thirty. Insert twenty-five at height two. Replace twenty-to-thirty at the bottom with twenty-to-twenty-five-to-thirty, and ten-to-thirty above with ten-to-twenty-five-to-thirty. No existing node height changes. Deleting twenty-five bypasses those two links again. The predecessor differs by level because each shortcut view contains a different subset of keys.

A second insertion of twenty-five returns False under set semantics. A multiset adaptation must choose between a count field and separate equal-key nodes and define whether deletion removes one occurrence or all. Explain search stopping, modified links, expected random behavior and the fixed-height limitation independently. Those distinctions are necessary before extending the code beyond this small single-threaded example.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path