3 ms·
The nice thing with skip lists, is all 'rungs' of the list are stored in an array for a given node, so there's a lot less pointer chasing. The not so nice thin
by torginus 6mo ago
The nice thing with skip lists, is all 'rungs' of the list are stored in an array for a given node, so there's a lot less pointer chasing.
The not so nice thing about it is that you have to pre-guess how deep your tree will be and allocate as many slots, or otherwise itll degrade into a linked list when you run out of rungs, or you end up wasting space.
- akoboldfrying 6mo agoYou don't really have to pre-guess the number of rungs -- you can just have a linked list of them and add a new rung "on top" when necessary, because you always start at the top rung, and only ever move sequentially along a rung, or step down to the rung immediately below. The overhead of pointer chasing is pretty small because there will only be O(log n) rungs; you move between rungs roughly often as you move along them. Also you can freely choose the "compaction rate" (base of that logarithm) to be something other than 2 -- e.g., choosing 4 means half as many rungs (but ~twice as much wandering along each rung).