4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Could you please reformat the question? $\endgroup$ – Dave Clarke Apr 30 '12 at 13:14
  • $\begingroup$ Hint: what is the relationship between a skip list and a binary tree? $\endgroup$ – AProgrammer Apr 30 '12 at 13:46
  • $\begingroup$ @AProgrammer: I didn't learn yet binary trees , so I can't use it $\endgroup$ – JAN Apr 30 '12 at 13:48
  • 2
    $\begingroup$ Please, try to ask only one question at a time. If you want to ask two unrelated questions, post two different questions. $\endgroup$ – svick Apr 30 '12 at 14:25
  • 1
    $\begingroup$ Welcome to Stack Exchange. This is a questions and answers site. If you have two separate questions (even if they're about related topics), please ask them separarely. I've edited out your second question, which wasn't very usefully formulated. Please ask it in a separate post, but you should say what you've already tried and what kind of improvement you're expecting. $\endgroup$ – Gilles Apr 30 '12 at 22:28
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.