Skip List
# What
A
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
# Links
Skip list - Wikipedia
Skip List | Set 1 (Introduction) - GeeksforGeeks