= Solution
Identify the first matching node at level zero, then bypass \b[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
$$
\boxed{\text{Delete exactly one occurrence of }x\text{ if present; otherwise leave the list unchanged}.}
$$
The additional work is $O(\mathrm{NumLevels})$. With the usual level cap and random heights, updates have the expected logarithmic <time complexity> associated with a <skip list>.
Back to article page
