Skip Lists

• Skip List, a data structure that expands on the Linked List and uses extra forward pointers with some random number generation to simulate the binary search algorithm achievable in Array Lists
• every node in the Skip List has multiple layers, where each layer of a node is a forward pointer.
• The very bottom layer is exactly a regular Linked List, and each higher layer acts as an "express lane" for the layers below.
• Also, the elements in a Skip List must be sorted. The sorted property of the elements in a Skip List will let us perform a find algorithm that is functionally similar to binary search.
• the distribution of heights in a Skip List affects the performance of the Skip List.
• the worst-case time complexity to find, insert, or remove an element in a Skip List is O(n) -> same as normal linked list
• the average-case time complexity of a Skip List is O(log n)

  REFERENCE: Stepik 2.3