What is a Skip List?

What is a Skip List?

Approach: Describe a probabilistic data structure that allows fast search.

A probabilistic data structure that allows O(log n) search, insertion, and deletion. It consists of multiple layers of linked lists where higher layers 'skip' over elements.

Follow-up: How does it compare to a balanced BST?

Key concepts: linked list, randomization, logarithmic search.