Returning a pointer to a structure and accessing its fields C++

Question

I am implementing a skiplist for my self and I'm experiencing some problems with C++. I have two structures:

1. A node of the skiplist - it holds its int value, and a pointer to an array of pointers to other nodes.

   struct node{
       int val;
       node** next;
   };
   

2. Skiplist which holds pointers to the head and tail of the list (sentinels).

   struct skiplist{
       node *head, *tail;
   };
   

Also, I have a function which returns a pointer to the skiplist structure (I use this function to initialize the skiplist):

skiplist* createSkipList(){
    skiplist* l = new skiplist;
    node* listHead = new node;
    node* listTail = new node;

    node* headNext[MAX_LEVEL]; //array of pointers
    listHead->next = headNext;

    for(int i=0; i<MAX_LEVEL; i++){
        listHead->next[i] = listTail;
    }

    l->head=listHead;
    l->tail=listTail;
}

And in the main() function I call:

skiplist* skiplist=createSkipList();

Everything works fine in the createSkipList() function, but if I want to refer to the skiplist in the main() i.e. by accessing skiplist->tail the program crashes. I've been searching for related posts, but they didn't help me.

As mentioned in a similar post I should't experience dangling pointers because I am using the new operator to allocate the structures. I would be grateful for any hints ;)

Answer 1

First problem:

You are not returning anything from createSkipList(), which means your program has undefined behavior. Add a return statement:

skiplist* createSkipList(){
    skiplist* l = new skiplist;
    // ...
    return l;
//  ^^^^^^^^^
}

Per paragraph 6.6.3/2 of the C++11 Standard:

[...] Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

Second problem:

As mentioned in a similar post I should't experience dangling pointers because I am using the new operator to allocate the structures [...]

Unfortunately, you do experience dangling pointers. As mentioned by Angew in the comments, what you are doing here:

node* headNext[MAX_LEVEL]; //array of pointers
listHead->next = headNext; 

Is to create a local array object and let listHead->next point to its first element, without considering that the array (as well as the objects it contains) will be destroyed once createSkipList() returns - objects with automatic storage duration get destroyed when they fall out of scope.

Moreover, as a general advice, consider using smart pointers for modeling ownership rather than doing manual memory management through raw pointers, new, and delete.