Building ideal skip lists

Question

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list.

The definition of an “ideal skip list” is that in the first level we'll have all the elements, half of them in the next level, a quarter of them in the level after that, and so on.

I'm thinking about a $\mathcal{O}(n)$ run-time algorithm involving throwing a coin for each node in the original linked-list, to determine for any given node whether it should be placed in a higher or lower level, and create a duplicate node for the current node at a higher level. This algorithm should work in $\mathcal{O}(n)$; is there any better algorithm?

Answer 1

Following your idea, you can do this:

• Iterate through the (sorted) list.
• For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.

For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log_{1/p} n)$ additional memory in expectation.

Note that the resulting list is not stricly "ideal" but in expectation; the interesting operations have logarithmic expected runtime due to the resulting distribution. See William Pugh's Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) and the work referenced there for details.

It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).