Ref: https://en.wikipedia.org/wiki/Skip_list

Skip list

  1. Bulit in layers.
  2. Bottom layer: ordered linked list.
  3. An element in layer \(i\) appears in layer \(i+1\) with probability \(p\).
  4. Express lane: 快车道
  5. Search process: top head \(\rightarrow\) go right \(\rightarrow\) if not found \(\rightarrow\) go down \(\rightarrow\) \(\cdots\)
  6. Indexable skiplist: \(O(\log n)\) look-up of the \(i\)th item. 
           1                               10
 o---> o---------------------------------------------------------> o    Top level
   1   |       3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1   |    2        1   |    2      |       3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
   1   | 1     1   | 1   | 1     1   | 1     1     1   | 1     1 
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level
                                         
Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node