Fish Touching🐟🎣

Skip List

Apr 3, 2023

# What

probabilistic  data structure that allows $O(\log n)$ average complexity for search and insertion within a ordered sequence of n elements.
Not Cache friendly.

# How

The idea: create multiple layers so that we can skip some nodes.

# Why

Search in a sorted linked list better than $O(n)$ time

Skip list - Wikipedia
Skip List | Set 1 (Introduction) - GeeksforGeeks