Skip List

Probabilistic data structure using multiple linked lists.

Skip lists

A probabilistic data structure that uses multiple levels of linked lists to achieve logarithmic time complexity for search, insertion, and deletion operations. Each element has a randomly determined number of forward pointers allowing traversal at different levels of granularity, effectively creating shortcuts through the list. This balances search efficiency with relatively simple implementation compared to balanced trees.

Skip lists are a probabilistic data structure introduced by William Pugh in 1989.

data structure probabilistic data structure

linked lists forward pointers

algorithm data structure search strategy