I was studying Skip Lists in section 3.10 of Advanced Data Structures by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, not homework).
The book explains the find
algorithm for a Skip List as follows:
...any access to an item, given a query key, starts on the list of the maximum level that currently exists. On this list we move until the key of the next item on the list will be past the query key; then we go down a level and repeat the procedure until we are at the bottom level. There we either find the queried item, or, when the next item is already past the query key, no such item exists.
The code sample for this (written in C) from the book is as follows.
First, they define the following structure:
typedef struct tr_n_t {
key_t key;
struct tr_n_t *next;
struct tr_n_t *down;
/* Possibly other information */
} tree_node_t;
Next, here is the actual find
method:
object_t *find(tree_note_t *tree, key_t query_key)
{
tree_note_t *current_node;
int beyond-placeholder = 0; /* This is a C idiom where ints can be used like booleans - 0 is false and 1 is true */
if (tree->next == NULL) /* empty skip list */
return(NULL);
else
{
current_node = tree;
while (current_node->down != NULL)
{
while (current_node->next != NULL && current_node->next->key <= query_key)
{
current_node = current_node->next;
beyond_placeholder = 1;
}
current_node = current_node->down;
}
/* This is the code I'm confused about */
if (beyond_placeholder && current_node->key == query_key)
/* Why not just return current_node here? Why current_node->next? */
return ((object_t *)current_node->next);
else
return(NULL);
}
}
I'm particularly confused about the following:
if (beyond_placeholder && current_node->key == query_key)
return ((object_t *)current_node->next);
Why does it return current_node->next
instead of just returning current_node
? Am I missing something about how the algorithm works?