cs126 skip lists

What is a skip list?

• An ADT that is an implementation of a Map

• Can be viewed as a 2D collection of positions arranged horizontally into levels and vertically into towers

Describe the structure of a skip list.

• For a set S, its skip list is a series of lists

  S₀, S₁ , … , S_h such that:

  • Each list S_i contains the special keys +∞ and −∞

  • S₀ contains all the keys of S in ascending order, and the special keys

  • S_h contains only +∞ and −∞

  • Each list is a (random) subset of the previous one

    • S₀ ⊇ S₁ ⊇ … ⊇ S_h

What is the java implementation of a skip list?

java.util.ConcurrentSkipListMap

List the (4) operations used to traverse a skip list.

• next(p): Returns the position following p on the same level.

• prev(p): Returns the position preceding p on the same level.

• above(p): Returns the position above p in the same tower.

• below(p): Returns the position below p in the same tower.

Explain how a search for the key k is performed on a skip list.

• Start at the first position of the top list, then repeat:

  • At the current item p, compare k with next(p)

  • If k == next(p)

    • Return next(p)

  • If k > next(p)

    • “scan forward” // p = next(p)

  • If k < next(p)

    • “drop down” // p = below(p)

  • If we try to drop down past the bottom list, return null, as the item is not in the list.

Explain how an insertion of (k,v) is performed on a skip list.

• A randomised algorithm is used

• Perform a search, if the k is found, replace its value with v

• Otherwise, insert (k,v) in the bottom tower

• Then ‘flip a coin’ to determine the height of the tower for (k, v)

  • If tails, stop here

  • If head, insert (k,v) into the next level (same tower) and repeat until a tails is flipped

Explain how a deletion of (k,v) is performed on a skip list.

• Search for k

• If k is not found, return null

• Otherwise, remove the element at its position, and all elements above it.

Name the (5) things stored in a skip list quad-node.

• The element / data

• Link to previous node

• Link to next node

• Link to node below

• Link to node above

What special keys are required in a skip list?

• PLUS_INF and MINUS_INF

• Must modify the key comparator to handle them

What determines the height of a skip list?

• The randomised insertion algorithm

• P(tower has a height i) = P(gets i consecutive heads) = 1/2ⁱ

• P(level i has an entry) ≤ n/2ⁱ

What is the expected space requirement of a skip list?

O(n)

What is the (very likely) height of a skip list?

O(logn)

What is the worst-case time cost of performing a search / deletion / insertion on a skip list?

O(logn)

How can a pseudorandom boolean be generated in java?

nextBoolean()

How can a pseudorandom double between 0.0 and 1.0 be generated in java?

nextDouble()

How can a pseudorandom integer be generated in java?

• nextInt()

• nextInt(n) returns a number up to but not including n