Search rule
Start at the highest level. Move right while the next value is smaller than the target; when you cannot move right, drop one level. Repeat until level 0 finds the value or its predecessor.
Data Structures algorithms / interactive lesson
Skip List
Build a layered ordered list where sparse upper levels act as express lanes for logarithmic expected search and insertion.
University
Guided lesson
Layered probabilistic search structure
Skip list
Step 1 / 92level 0
About the algorithm
A skip list is a probabilistic ordered data structure built from several linked-list levels. Level 0 contains every value in sorted order, while higher levels contain fewer nodes and act as express lanes.
Insertion
Insertion first performs the same search and remembers the predecessor on every level. Then it creates a tower for the new value and splices that tower into each remembered level.
Probability
In a normal skip list, each new node flips coins to decide how tall its tower is. This gives expected O(log n) search, insertion, and deletion while keeping the implementation simpler than many balanced trees.
Code companion
Connect each visual decision to an implementation pattern.
search(target):
node = head
for level from maxLevel down to 0:
while node.next[level] exists and node.next[level].value < target:
node = node.next[level]
return node.next[0]