1. Skip Lists

• A skip list for a set S of key and element pairs is a series of lists S0, S1, ... , S_h where,
  • Each list has +infinite and -infinite
  • S_0 (base) contains all the keys of S in the non decreasing order
  • Each list is a subsequence of the previous one → S_0 $\supseteq$ S1 $\supseteq$ S2 ... $\supseteq$ S_h

2. Operation

Search

• Start at the first element of the top list
• x : a key to search for / p : the current position / y : key(next(p))
  • x = y : return element(next(p))
  • x > y : scan forward
  • x < y : drop down
  • if drop down at the bottom, return null

Insertion

• Toss a coin till you get a tail, i is the number of heads
  • if i ≥ h, add S_h+1, ... , S_i+1
• search for x, and find the positions p0, p1, ..., pi of the items with the largest key less than x in each list
• For each list S0, ..., Si, insert (x, o) after all 'p's

Deletion

• find p0, ... , pi of the items with the key x in each list
• remove 'p's
• remove all the lists only with +,- infinite but one