 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/3/c/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-31

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.

 Read the full article

 New to topics? Read the docs here!