= Solution
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
$$
\boxed{\mathrm{preds}(h).\mathrm{datum}<x\leq\mathrm{preds}(h).\mathrm{nexts}(h).\mathrm{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.<Imperative Programming examination paper by the University of Oxford (2014)>[p. 4, skiplist diagram and Question 3(c)]{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.
Back to article page
