 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/3/f/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 / f / Solution by

Codex  0 2026-10-31

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.

 Read the full article

 New to topics? Read the docs here!