A skip list is a layered linked data structure that stores sorted data and supports fast search, insertion, and deletion. It is useful because it gives performance similar to balanced binary search trees while using simpler pointer-based logic. This cheat sheet helps students understand how towers, forward pointers, and random levels work together.
It is especially helpful for comparing expected performance with worst-case behavior.
Key Facts
- A skip list stores elements in sorted order using multiple linked levels, where higher levels act as shortcuts over lower levels.
- Search starts at the top-left head node and moves right while the next key is less than the target, then moves down when it cannot move right.
- The expected search time in a skip list is O(log n) when node heights are chosen with a fixed probability such as p = 1/2.
- The expected insertion time is O(log n) because the search path finds update positions, and the new node is linked into each level it receives.
- The expected deletion time is O(log n) because the node is found first, then pointers that reference it are bypassed at each level.
- The expected space complexity is O(n) because the expected number of pointers per node is constant when 0 < p < 1.
- A common random height rule is: start with level 1, then add one more level while a random test succeeds with probability p.
- The maximum level is often chosen near log base 1/p of n to keep the structure efficient and prevent unlimited tower growth.
Vocabulary
- Skip List
- A probabilistic sorted data structure made of linked lists at multiple levels that allows efficient search, insertion, and deletion.
- Level
- One horizontal linked list layer in a skip list, with level 0 or level 1 usually being the bottom layer containing all keys.
- Tower
- The stack of linked nodes representing the same key across several levels of a skip list.
- Forward Pointer
- A pointer from one node to the next node on the same level.
- Promotion Probability
- The probability p that a node is promoted to the next higher level when its height is chosen.
- Expected Time
- The average running time over many random choices, which is O(log n) for standard skip list operations.
Common Mistakes to Avoid
- Forgetting that the bottom level contains every key is wrong because higher levels are only shortcuts and may skip many elements.
- Moving down too early during search is wrong because you should keep moving right while the next key is still less than the target.
- Assuming skip lists always guarantee O(log n) worst-case time is wrong because the basic structure is randomized and can have rare bad height patterns.
- Not updating pointers at every affected level during insertion or deletion is wrong because it can leave broken links or unreachable nodes.
- Choosing a promotion probability without considering space is wrong because larger p values create taller towers and more pointers per node.
Practice Questions
- 1 In a skip list with n = 1024 and p = 1/2, what is the approximate expected maximum level if it is chosen near log base 2 of n?
- 2 If a skip list has 500 keys and uses p = 1/2, about how many total node appearances are expected across all levels?
- 3 During a search for key 42, the next key on the current level is 50 and the current node is 35. What should the search do next, move right or move down?
- 4 Explain why a skip list can have expected O(log n) search time even though it is built using linked lists instead of arrays or tree rotations.