Friday, January 9, 2009

Generic Skip list (skiplist)

Skip lists are an interesting randomize data structure for storing pairs of . Skip lists have logaritmic search and insertion time. Here I sketch a generic skip list code

5 comments:

  1. The right grammar should be that "skip lists are a ..."

    ReplyDelete
  2. more precisely: "are an interesting"

    ReplyDelete
  3. if ((tk == 0) || // null?
    ( key < tk->key_)) // search key < next level link's key

    Is not correct. C++ does not guarantee left to right evaluation and so this may result in a segmentation fault depending on the compiler.

    ReplyDelete
  4. @anonymous:

    of course it does for && and ||: it is called shortcut evaluation, and test for null OR dereference is idiomatic both in C and C++.

    ReplyDelete
  5. I believe you have a bug in your search__ function:

    if ((x == 0)) ||
    (key < x->val_))

    Shouldn't this read:

    if ((x == 0)) ||
    (key < x->key_))

    ?

    ReplyDelete