Overview
A Skip List is an ordered collection of linked lists arranged in multiple levels. The lowest level contains all elements, while higher levels contain selected elements that act as shortcuts. These shortcuts allow searches to skip over many nodes instead of examining every element.
How it works
Start searching from the highest available level.; Move forward while the next node's value is smaller than the target.; When moving forward would pass the target, move down one level.; Continue until reaching the bottom level.; Insertion finds the correct position and randomly chooses the node's height.; Deletion removes the node from every level in which it appears.
Structure
description: Each node may contain several forward pointers, one for each level in which it appears. The highest level provides long-distance jumps, while lower levels provide increasingly detailed navigation.; levels: level: Top levels; description: Contain relatively few nodes and allow large jumps through the sorted sequence.; level: Middle levels; description: Provide shorter jumps toward the target.
Key concepts
Multiple linked-list levels; Forward pointers; Randomized node heights; Probabilistic balancing; Sorted search; Expected complexity
Time complexity
operation: Search; average: O(log n); worst: O(n); operation: Insertion; average: O(log n); worst: O(n); operation: Deletion; average: O(log n); worst: O(n)
Space complexity
O(n) expected space under common probability choices, although the exact number of forward pointers depends on node heights.
Example
sortedValues: 10; 20; searchTarget: 60; explanation: Higher levels provide shortcuts across the list. The search moves forward through large intervals, then descends to lower levels to locate 60.; result: The target 60 is found without examining every element.