= Solution
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:
$$
\boxed{x\text{ occurs}\iff\mathrm{preds}(0).\mathrm{nexts}(0)\ne\mathrm{tail}\ \land\ \mathrm{datum}=x.}
$$
The additional work after the <skip list> search is constant.
Back to article page
