  We describe todolists (top-down skiplists), a variant of skiplists (Pugh
1990) that can execute searches using at most $\log_{2-\varepsilon} n + O(1)$
binary comparisons per search and that have amortized update time
$O(\varepsilon^{-1}\log n)$. A variant of todolists, called working-todolists,
can execute a search for any element $x$ using $\log_{2-\varepsilon} w(x) +
o(\log w(x))$ binary comparisons and have amortized search time
$O(\varepsilon^{-1}\log w(w))$. Here, $w(x)$ is the "working-set number" of
$x$. No previous data structure is known to achieve a bound better than
$4\log_2 w(x)$ comparisons. We show through experiments that, if implemented
carefully, todolists are comparable to other common dictionary implementations
in terms of insertion times and outperform them in terms of search times.
