Skip Lists

📚 Drozdek (Ch. 3)

Linked List Efficiency

How efficient is a linked list?

• Adding/removing items
  • at Head
  • at Tail
  • in-order
• Finding (searching) items
  • Ordered list?
  • Un-ordered list?
• Traversal

What About Binary Search?

Recall how the binary search algorithm removed the complexity from searching an (ordered) array…

What if we could do some kind of non-sequential search on a linked list?

A special kind of linked list that allows just such a search is called a skip list .

Skip List

By making different nodes hold different numbers of pointers, you can search non-sequentially:

Perfect Skip List

• In a skip list of n nodes:
  • Every second node points two nodes ahead
  • Every fourth node points four nodes ahead
  • And so on…

Perfect Skip List

The “level” of a node refers to the number of pointers it has. The highest level is given by \(\lg(n) + 1\) (1-indexed), or \(\lg(n)\) (0-indexed).

Skip List Levels

• To search a skip list:
  • start at the highest level, and traverse until an element is found that is too large, or NULL is encountered.
  • If either case occurs, restart at the previous node, but at the next lowest level
  • Continue until the target value is found
    • Or until you hit the NULL at the end of the first-level list.

Skip List Search

This “perfect skip list” is easy to draw… but difficult (expensive) to achieve in practice.

Consider adding a new item / removing an item.

Skip List Search

Nodes do not have to be perfectly distributed…

As long as the requirements are met for the number of nodes at each level, the skip list can still work.

Imperfect Skip List

The new node can determine its number of links at random, provided that it uses a probability distribution that (in the long run) maintains the correct proportions of levels…

Imperfect Skip List

Another Take on Insertion

Keep a special “node” that points “back” at all “see-able” nodes… those you used to find the insertion point.

Use that backLook node to set the appropriate next pointers.

backLook Node

Skip List Efficiency

Searching: ?

Insert (random): ?

Space: ?

Imperfect Skip List

Skip List Efficiency

Searching: \(O(\log_2(n))\)

Insert (random): ?

Space: ?

Imperfect Skip List

Skip List Efficiency

Searching: \(O(\log_2(n))\)

Insert (random): \(O(\log_2(n))\)

Space: ?

Imperfect Skip List

Skip List Efficiency

Searching: \(O(\log_2(n))\)

Insert (random): \(O(\log_2(n))\)

Space: \(O(n \cdot \log_2(n))\)

Imperfect Skip List

Skip Lists