Skip List

Probabilistic balanced search structure alternative to BST.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Skip List Concept

Skip List is a probabilistic alternative to balanced BST. Multiple levels of linked lists with increasing sparsity. Bottom level = all elements. Each higher level skips some elements (like express lanes). Search starts at top, drops down when next element > target.

Structure

Goskip-list-node-and-structure.go

31 linesLn 1, Col 1Go

Each node has array of forward pointers (one per level). Level determined randomly with probability p (typically 0.5). Max level typically 16-32 for practical sizes.

Operations

Search: start at highest level, move right while next.key ≤ target, then drop down. Insert: search to find position at each level, create node with random level, update forward pointers. Delete: search, update forward pointers to bypass node.

Goskip-list-search-and-insert.go

48 linesLn 1, Col 1Go

Update array tracks last node at each level before insertion point. New node level determined probabilistically. Link new node into each level's forward chain.

Complexity Analysis

Operation	Average	Worst Case	Space
Search	O(log n)	O(n)	O(n)
Insert	O(log n)	O(n)	O(n)
Delete	O(log n)	O(n)	O(n)

Expected O(log n) with high probability. Worst case O(n) but probability decreases exponentially. Simpler to implement than RB/AVL trees. Space overhead: ~2n pointers.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.