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.
Understanding Skip List Data Structure Reference
The key idea behind a skip list is that a search does not need to inspect every item in the bottom chain. A tall node appears in several layers. Its upper links jump across many shorter nodes.
When the search gets close to the wanted key, it drops to a lower layer for a finer move. This is similar to using an express train for a long trip, then using local stops near the destination.
Each move right is safe because the keys remain sorted at every level. Each move down is safe because a lower level contains all the nodes visible above it, plus more nodes between them.
Randomness replaces the rotations and strict shape rules used by many search trees. When an item is inserted, it always joins the bottom level. A random trial then decides whether it rises one level higher.
Another successful trial lets it rise again. With a promotion chance of one half, about half of the nodes reach level two, about one quarter reach level three, and so on. Very tall towers become rare.
This produces a structure with many short links near the bottom and a small number of long links near the top. The exact layout can differ after each run even when the inserted keys are the same.
Expected performance has an important meaning. It describes the average behavior over the random choices used to build heights. A badly lucky sequence can create a structure that is close to one long linked list.
In that case, a search may need to inspect nearly every item. This poor case is unlikely when the random generator behaves fairly and the data set is large. Students should not claim that every operation always takes logarithmic time.
The more accurate statement is that search, insertion, and deletion usually take logarithmic time in expectation. This difference between expected time and guaranteed time matters when comparing skip lists with self-balancing search trees.
Insertion and deletion require careful pointer work. During a search for an insertion point, an implementation normally remembers the last node visited at each level. These remembered nodes form an update path.
The new node is connected after each remembered node up to its chosen height. For deletion, the same kind of path identifies every link that points to the target node. Each such link is redirected to skip over the target.
The target node can then be removed. Forgetting one level creates a broken structure, where an upper shortcut may point to a node that no longer belongs in the list.
Skip lists appear in systems that need ordered keys with frequent updates. They are used in some databases, caches, memory tables, and concurrent software. Their linked design can be easier to adapt for multiple threads than a tree with complex rebalancing steps, though correct concurrent code is still difficult.
When studying them, trace one search by hand across several levels. Mark the predecessor at every level before inserting or deleting.
Check that keys remain ordered and that every upper-level link has matching nodes below it. Those checks reveal most mistakes quickly.