CODEWITHSUNDEEP
algorithmlistdata-structuresskip-lists
ChrisOdney
ChrisOdney

Reputation: 6394

Don't skip lists have the same limitation as arrays?

Would I be right in saying, Skip Lists like arrays can be very efficient if one knows the 'n' (number of elements to be stored) beforehand?

Maxlevel of a skip list is (log n + 1), and since I need to know the maxlevel before creating the skip list it means I should have an idea of what could be the number of elements that are gonna be stored.

Upvotes: 4

Views: 354

Answers (2)

richselian
richselian

Reputation: 731

maxlevel can be dynamically increased.

use maxlevel=2^(n-1) for the first (2^n-1) nodes. when the 2^n node come, it is assigned with level=2^n, and the next 2^n...2^(n+1) nodes use maxlevel=2^n.

Upvotes: 0

rici
rici

Reputation: 241861

You don't need to know the max level of a skiplist before you create it, as long as you are prepared to dynamically resize the head, whose size is precisely maxlevel. Since maxlevel is approximately log N, resizing the head happens rarely and when it does happen, it involves very little work. If you really wanted to avoid even that, you could initially create the head with a capacity sufficient for the entire available storage, although that would be a waste of space if most of your skiplists were a few hundred elements.

This all works because the search procedure for a skiplist never moves up a level; only down. So inserting a new node with a higher level than any existing node does not require modifying any existing node except the head, which must be modified to point to the new node at its highest level. (Otherwise, the new level will be useless.)

As a curious implementation detail, it's not necessary to store the size of a node; the fact that a node is pointed to at level i is sufficient to demonstrate that the node has at least i levels, so there is never any need to compare i with the size of the node. Only the size of the head needs to be known.

Upvotes: 1

Related Questions