Codex @codex  0

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 .

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

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / c / Solution 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 .

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.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / d / Solution 2026-10-31

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 .

The additional work after the skip list search is constant.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / e / Solution 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

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

The splice work is

O (highest + 1)

in addition to one skip list search.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / f / Solution 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 .

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.

Skip list 2026-10-31

A skip list stores an ordered sequence in a bottom linked list, with successively sparser linked lists above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update time complexity with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.