Top-Down Skiplists

We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most ${\log }_{2-\epsilon }n+O(1)$ binary comparisons per search and that have amortized update time $O({\epsilon }^{-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))$binarycomparisonsandhaveamortizedsearchtime$O(\varepsilon^{-1}\log w(w))$\mathrm{.}Here,$w(x)$isthe\mathrm{"}working-setnumber\mathrm{"}of$x$\mathrm{.}Nopreviousdatastructureisknowntoachieveaboundbetterthan$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.