Data Structures & Algorithms Lecture Notes

22 December 2010 • Skip Lists

---

Outline

Remember This?

• What’s the quickest way to the middle list element?
  • Have a reference to it.

    

• What about the other elements?
  • Have references to them.

    

• And so on.

Oh Really?

• To gain advantage, the references have to be layered.

  Each layer reference points to half of the next layer.

• Getting nearly equal halves was difficult.
  • Is there a better way?

Skip-List Example

Skip-List Searching

• find(v) returns a pointer to the level-0 node containing the largest value at most v.
  • Such a node always exist, although it may be –∞.

Skip-List Search

• In essence:
  1. Go as far right in the linked list as possible.
  2. Drop to the next linked list and repeat.
• Like so:
  1. Set n to the upper-left node (–∞).
  2. while n.next.value < v, n = n.next
  3. if n.level = 0,return n
  4. n = n.below
  5. Go to 2.

Skip-List Search Example

Skip-List Deletion

• A skip list is a pile of linked lists.
• To delete(v):
  1. Find v in the skip list.
  2. Unlink each of v’s nodes from its respective linked list.

Skip-List Delete Example

• Find 46.

• Remove 46.

Performance

• How do skip lists perform?

  

• In the worst case, searching takes O(n + h).
  • And deleting and inserting use searching.

How High?

• A value at level i won the coin toss i times.
  • The probability of that happening is (1/2)ⁱ.
• An n-value skip list should have n(1/2)ⁱ values at level i.
• How many values at level clog n, c > 1?
  • n/2^{log nc} = n/n^c = 1/n^{c - 1}.
  • There aren't many values at level clog n.
• Skip-list height should be bounded by O(log n).

How Long?

• 

• How many times can you lose a coin flip before winning?
  • If half the flips are losers, you'd expect a winner within two flips.
• Expect O(1) nodes going right.

Skip-List Performance

• Searching alternatively moves right and moves down a level.
  • We expect O(log n) levels, and O(1) visits per level.
  • Searching is expected to take O(log n) work.
• Insertion is searching followed by an expected O(log n) inserts.
• Deletion is searching followed by an expected O(log n) deletions.
• Skip lists have O(log n) expected performance.

Summary

References

• Skip Lists: A Probabilistic Alternative to Balanced Trees by William Pugh in Communications of the ACM, June, 1990.
• Skip Lists (Section 9.4) in Data Structures & Algorithms in Java, fifth ed., by Michael Goodrich and Roberto Tamassia, Wiley, 2010.
• Skip Lists by Bruce Schneier in Dr. Dobb’s Journal, January, 1994.
• Alternating Skip Lists by Laurence Marrie in Dr. Dobb’s Journal, August, 2000.

---

This page last modified on 22 April 2010.