data structure that allows $O(\log n)$ average complexity for search and insertion within a ordered sequence of n elements.
Not Cache friendly.
The idea: create multiple layers so that we can skip some nodes.
Search in a sorted linked list better than $O(n)$ time
Skip list - Wikipedia
Skip List | Set 1 (Introduction) - GeeksforGeeks