Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3

Assume NumLevels >= 1. Both sentinel nodes occur on every level; the tail ends every linked list.

val head = new Node(Int.MinValue)
val tail = new Node(Int.MaxValue)
for (level <- 0 until NumLevels) {
  head.nexts(level) = tail
  tail.nexts(level) = null
}

The empty skip list therefore has

head ⟶ tail ⟶ null at every level .

(1)

The forbidden data values distinguish the sentinel nodes from genuine entries.

Solution

 0  0

Follow the next reference for the desired level, stopping at the tail. This returns the genuine nodes in their linked list order, excluding both sentinel nodes.

def nodesAt(level: Int): List[Node] = {
  require(0 <= level && level < NumLevels)
  val out = scala.collection.mutable.ListBuffer.empty[Node]
  var n = head.nexts(level)
  while (n ne tail) {
    out += n
    n = n.nexts(level)
  }
  out.toList
}

Write

L_{h}

for the resulting sequence of nodes at level

h

. The abstraction function is

α = map (datum, L_{0}) .

(1)

It preserves repetitions, because distinct nodes may carry equal values. A suitable representation invariant requires the following:

head and tail are distinct sentinel nodes with the specified extreme values; every node has a nexts array of length NumLevels.
For each level, following references from head gives a finite acyclic chain ending at tail, then null; the data along that chain are nondecreasing. Genuine values lie strictly between the sentinel values.
Each $L_{h + 1}$ is a subsequence of $L_{h}$ by node identity, so the relative order of equal-valued nodes agrees across levels. Every genuine node occurs in $L_{0}$ and on a contiguous initial collection of levels.
A genuine node absent from a level has null in that level's slot. Tail slots are all null; every other slot on a chain points to the next member of that chain.

These structural requirements make the traversal terminate and make descending through levels valid. A probabilistic height distribution is a performance policy, rather than a condition needed for the abstraction function to describe an ordered sequence.

c

 0  0

Solution

 0  0

Start at the highest level. Move right only while the next key is strictly smaller than x, then descend without returning to head.

def findPreds(x: Int): Array[Node] = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = new Array[Node](NumLevels)
  var n = head
  var level = NumLevels - 1
  while (level >= 0) {
    while (n.nexts(level).datum < x) {
      n = n.nexts(level)
    }
    preds(level) = n
    level -= 1
  }
  preds
}

At each inner loop head, n belongs to the current level and has key below x. Every node already passed has key below x. The representation invariant ensures that n also belongs to the next lower level. Stopping just before a key at least x therefore gives

preds (h) . datum < x \leq preds (h) . nexts (h) . datum .

(1)

The tail prevents a null dereference during the comparison. Strict comparison makes the predecessor lie before the first occurrence of x, including duplicates. On the source diagram, findPreds(14) yields data

[11, 9, 9, - \infty]

, in increasing level order.^[ref]

With the customary random-level policy this has expected logarithmic time complexity for a suitably sized level cap; an unlucky skip list can require a linear scan. No deterministic logarithmic guarantee is claimed.

d

 0  0

Solution

 0  0

The level-zero successor of the predecessor is the first node whose value is at least x. Thus only one equality test remains.

def contains(x: Int): Boolean = {
  if (x == Int.MinValue || x == Int.MaxValue) false
  else {
    val n = findPreds(x)(0).nexts(0)
    (n ne tail) && n.datum == x
  }
}

In particular, the tail is never reported as a genuine member:

x occurs ⟺ preds (0) . nexts (0) \neq = tail \land datum = x .

(1)

The additional work after the skip list search is constant.

e

 0  0

Solution

 0  0

Pick the new node's highest level once, and splice the same node into every level up to that height. pickLevel must return a value in 0 until NumLevels.

def add(x: Int): Unit = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = findPreds(x)
  val highest = pickLevel
  require(0 <= highest && highest < NumLevels)
  val n = new Node(x)
  for (level <- 0 to highest) {
    n.nexts(level) = preds(level).nexts(level)
    preds(level).nexts(level) = n
  }
}

The fresh array contains null above the chosen height. At each changed level the new node lies after a smaller value and before a value at least x. Every new occurrence is placed before all previous equal-valued nodes, consistently across levels. Therefore the representation invariant is preserved and

α_{new} = α_{old} with one extra occurrence of x .

(1)

The splice work is

O (highest + 1)

in addition to one skip list search.

f

 0  0

Solution

 0  0

Identify the first matching node at level zero, then bypass that node wherever it appears. Comparing keys alone at higher levels could accidentally remove links to a different occurrence with the same key.

def delete(x: Int): Unit = {
  if (x != Int.MinValue && x != Int.MaxValue) {
    val preds = findPreds(x)
    val victim = preds(0).nexts(0)
    if ((victim ne tail) && victim.datum == x) {
      for (level <- 0 until NumLevels) {
        if (preds(level).nexts(level) eq victim) {
          preds(level).nexts(level) = victim.nexts(level)
        }
      }
    }
  }
}

Because higher-level chains are subsequences of level zero, the predecessor found for any level containing victim points directly to it: no earlier equal-valued node can intervene before the first level-zero occurrence. Bypassing it preserves the order and nesting of all the linked lists. Levels lacking it are unchanged. Thus

Delete exactly one occurrence of x if present; otherwise leave the list unchanged .

(1)

The additional work is

O (NumLevels)

. With the usual level cap and random heights, updates have the expected logarithmic time complexity associated with a skip list.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

f

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion