= Solution
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
$$
\boxed{\alpha_{\mathrm{new}}=\alpha_{\mathrm{old}}\text{ with one extra occurrence of }x.}
$$
The splice work is $O(\mathrm{highest}+1)$ in addition to one <skip list> search.
Back to article page
