Questions
16 of 16
What is a Skip List? How does it improve search time?
Difficulty: 5/10
Skip Lists
A Skip List is a probabilistic data structure built on top of linked lists. It maintains multiple levels of forward pointers, allowing searches to skip over many nodes instead of traversing every node sequentially. With randomized level assignment, expected search, insertion, and deletion complexity is O(log n).
javascript
- 1
Expected search complexity: O(log n).
- 2
Expected insertion and deletion: O(log n).
- 3
Worst-case complexity can be O(n), depending on the random structure.
- 4
Multiple levels act as express lanes over the base linked list.
- 5
Skip Lists are conceptually simpler than many balanced-tree implementations.
- 6
They are useful in ordered indexes and some concurrent data structures.
Follow-up Questions
- How does a Skip List compare with a balanced BST?
- Why is Skip List complexity probabilistic?
- How are levels selected?