What
A probabilistic data structure that allows 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 time
Links
Skip list - Wikipedia
Skip List | Set 1 (Introduction) - GeeksforGeeks