Do not skip lists have the same limitations as arrays?

Question

I would be right in saying: "Skipping lists, like arrays, can be very effective if you know" n "in advance (the number of elements to keep)?

The maxlevel of the skip list (log n + 1) , and since I need to know maxlevel before creating the skip list, this means that I need to have an idea of ​​what the number of items will be stored.

Answer 1

You do not need to know the maximum skipist level before creating it, if you are ready to dynamically change the size of the head, the size of which is exactly equal to maxlevel . Since maxlevel approximately log N , changing the size of the head is rare, and when it does, it requires very little work. If you really wanted to avoid this, you could create a head with enough power for the entire available storage, although it would be a waste of space if most of your skipists were several hundred elements.

This all works because the search procedure for a skipist never rises to the level; just down. Therefore, the insertion of a new node with a higher level than any existing node does not require modification of any existing node, except for the chapter, which must be changed to point to the new node at its highest level. (Otherwise, a new level will be useless.)

As a curious implementation detail, there is no need to store the size of the node; the fact that a node is specified at level i is sufficient to demonstrate that node has at least i levels, so you never need to compare i with the size of the node. You need to know only the size of the head.

Answer 2

maxlevel can dynamically increase.

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