What is Skip list?

what is Skip list?

The skip list is a probabilisitc data structure that is built upon the general idea of a linked list. The skip list uses probability to build subsequent layers of linked lists upon an original linked list. Each additional layer of links contains fewer elements, but no new elements.

You can think about the skip list like a subway system. There’s one train that stops at every single stop. However, there is also an express train. This train doesn’t visit any unique stops, but it will stop at fewer stops. This makes the express train an attractive option if you know where it stops.