Yes, 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 item

Yes, 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.