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

135 views Asked by At

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...

3

There are 3 answers

0
Tabaqui On BEST ANSWER

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.

0
AudioBubble On

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.

0
Vlad from Moscow On

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.