Re: Skip List for GLIB

[Eric Vander Weele <ericvw gmail com>]

2010/12/22 Sebastian Dröge <sebastian droege collabora co uk>

On Wed, 2010-12-22 at 11:03 -0500, Eric Vander Weele wrote:
> Hello,
>
>
> Before I started working on this, I wanted to bounce the idea of
> adding a skip list -- GSkipList.  It shouldn't be that more
> complicated than the balanced binary tree implementation and the test
> driver for a skip list would almost be the same as the the one for the
> balanced binary tree.

What would be the advantage over GSequence (which internally uses a
balanced binary tree)? Would you implement a deterministic (which of the
many variants?) or probabilistic skip list (would you expose the level
selection probability to allow slower but less memory hungry
skiplists?)?

Insertion/deletion/search could be done with amortized O(log n) time, which is similar to GSequence if insertions are done using the 'insert_sorted()' methods.  However, the advantage over GSequence is that insertions are always sorted, there would be no 'prepend' or 'append' methods and the space efficiency of skip lists is also an advantage over GSequence and GTree.  

I was thinking about implementing a probabilistic skip list where the level selection probability and max level would be exposed to allow for tuning for space/time trade-offs depending on the application.  Using NULL as the skip list terminator makes implementing a multi-set skip list more natural and slightly more efficient, but a set skip list implementation can be done as well.