Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?

Question

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?

Answer 1

I have checked the book and it seems that in the implementation, when the node holding the queried key is found, the code current_node->next retrieves the object held by the node, which is also the reason for the cast:

((object_t *)current_node->next).

You can check the diagram of the skip list below, which was taken from the book and notice that the next field of the nodes at the lowest level points to an object instead of a node:

If you check the implementation of find for search trees (pages 31-32), the same idea is used, but instead of next, the left field was used to hold the object.