Using pointers vs. address-of operator while copying linked lists in C++

Question

I made the following linked list structure and printList function. Both functioned correctly:

struct Node{
    int data;
    Node *np;
};

void printList(Node *x){
    cout << x->data << " ";
    if (x->np != NULL){
        printList(x->np);
    }
    return;
}

Then I decided to write a recursive function to copy over a linked list. One implementation, returning a pointer value, works...whereas the other, returning an address-of didn't work...I can't for the life of me figure out why this is the case:

This works:

Node * copyList(Node *x){

    Node * y = new Node;
    y->data = x->data;
    if (x->np != NULL){
        y->np = copyList(x->np);
    }else{
        y->np = NULL;
    }
    return y;
}

This doesn't work:

Node * copyList(Node *x){
    Node y = {x->data,NULL};
    if (x->np != NULL){
        y.np = copyList(x->np);
   }
   return &y;
}

I'm a little confused as to why. I would assume that given that a pointer essentially refers to a memory address, returning &y would be just as fine...

Depending on your compiler, if you turn warnings on it should be able to tell you exactly why this isn't working. — user657267, Jun 23 '15 at 21:42

score 6 · Accepted Answer · answered Jun 23 '15 at 21:42

6

In the second case the Node y object you are creating will go out of scope when the function call will end. The address you are returning will then be not valid.

answered Jun 23 '15 at 21:42

Tabaqui

427
1
3
11

score 1 · Answer 2 · answered Jun 23 '15 at 21:42

As soon as copyList exits, all of its local variables are destroyed; there no longer exists a Node object at the location pointed to by the pointer you return. That memory will likely be used for some other purpose the next time you call a function.

Vlad from Moscow · Answer 3 · 2015-06-23T22:24:27.733

The first function is also invalid because in general the argument that is x can be equal to NULL. So you have undefined behaviour in statement

y->data = x->data;

A correct function can look like

Node * copyList( const Node *x )
{
    if ( x == NULL )
    {
        return NULL;
    }
    else
    {
        Node *y = new Node { x->data, copyList( x->np ) };
        return y;
    }
}

Or even like

Node * copyList( const Node *x )
{
    return ( x == NULL ) ? NULL : new Node { x->data, copyList( x->np ) };
}

The same problem exists with function printList. It should be defined like

void printList( const Node *x )
{
    if ( x == NULL )
    {        
        std::cout << std::endl;
    }       
    else
    {        
        std::cout << x->data << ' ';
        display( x->np );
    }        
}

As for the second function then apart from this error it returns pointer to a local variable that after exiting the function becomes invalid because the local variable will be deleted.

Using pointers vs. address-of operator while copying linked lists in C++

3 Answers3