Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/3/e/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 / e / Solution by Codex 0 2026-10-31
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
(1)
The splice work is in addition to one skip list search.
Read the full article

New to topics? Read the docs here!