4 ms·
I think your size computation is wrong, no? A skip list is a doubly-linked list at each level, so two pointers per node at level zero (i.e. same as a tree). E
by ajross 18y ago
I think your size computation is wrong, no? A skip list is a doubly-linked list at each level, so two pointers per node at level zero (i.e. same as a tree). Each higher level has (statistically) half as many entries, so you have to multiply by the sum of the 1/2^N series, which is 2. So on average a skip list takes 4 pointers per node, which is twice as much as a tree. It's just a constant factor, there's no dependence on set size.
(It's true that balanced trees take a little more than two pointer per node, but e.g. red-black trees only need one extra bit, which you can pack into the bottom of one of the pointers if you like).
On the whole, skip lists are cute, but not really "better" than a red-black or AVL tree. And the balanced trees aren't that hard to implement, even if you decide to do your own. Add that to the fact that tree stuctures in code are kinda esoteric (almost always, you just want to be able to fetch an item by identity. Range comparisons are pretty rare in memory -- that's what databases are for) and skip lists leave me a little ... meh.
- BrandonM 18y agoYes, the size could be computed that way. However, I was going by the original paper in my implementation. This meant that I had to first estimate how many items would be in the tree, then take the base-2-log of that (in order to get O(lg n) performance), and then make each node allocate that many pointers. Of course, with most nodes, most of these pointers are uninitialized and unused. In my comment, I was referring to my (and the reference) implementation. After reading your comment, though, you're right that you could allocate a number of pointers equal to the height of the specific node. The only downside is that you then have two mallocs for each new node (once for the node and once for its array of pointers), unless you do something hackish like putting the array of pointers at the end of the struct and manually adjusting your malloc call to allocate the right amount. One other note: I don't think my skiplist was doubly-linked. The search algorithm involves moving forward on the highest level until the move would take you past the desired element, then you move down a level and continue. By the time you hit the bottom, you're guaranteed to either hit the element you're looking for, or your position is the node before where the element would be if it was in the list. Thus double-linking is entirely unnecessary.