Linked list - new Node pointer vs. new Node variable

Question

I am creating a linked list for practice and I came to a problem.

I've created 2 similar codes and in the first one I create certain structure called Node as a variable and in the second code I create a structure called Node as a pointer.

In my opinion it should work the same way but it doesn't. I will post code and look at the function called addNode().

Also I have a next question: Why do I have to pass pointers like this: addNode( Node *& head, Node *& tail ) to make it work properly instead of passing them as addNode( Node * head, Node * tail ).

First code ( bad ):

#include <iostream>
#include <string>

using namespace std;

struct Node{
    int    val;
    Node * prev;
    Node * next;

    Node( int val ) : val( val ) { }
};


void printList( Node * ptr ){
    while( ptr != NULL ){
        cout << ptr -> val << " ";
        ptr = ptr -> next;
    }   
    cout << endl;
}

void addNode( int val, Node *& head, Node *& tail ){
    Node tmp( val );
    if( head == NULL ){
        head            = &tmp;
        tail            = &tmp;
        tmp . prev      = NULL;
        tmp . next      = NULL;
    }
    else{
        tail -> next    = &tmp;
        tmp . prev      = tail;
        tmp . next      = NULL;
        tail            = &tmp;
    }
}

int main(){

    Node * head         = NULL;
    Node * tail         = NULL;

    addNode( 3, head, tail );
    addNode( 8, head, tail );
    addNode( 2, head, tail );
    addNode( 4, head, tail );
    addNode( 15, head, tail );
    addNode( 11, head, tail );

    /*Node b( 5 );

    cout << b . val << endl;
    */
    printList( head );
    return 0;
}

Second code ( good ):

#include <iostream>
#include <string>

using namespace std;

struct Node{
    int      val;
    Node * prev;
    Node * next;

    Node( int val ) : val( val ) { }
};


void printList( Node * ptr ){
    while( ptr != NULL ){
        cout << ptr -> val << " ";
        ptr = ptr -> next;
    }   
    cout << endl;
}

void addNode( int val, Node *& head, Node *& tail ){
    Node * tmp = new Node( val );
    if( head == NULL ){
        head            = tmp;
        tail            = tmp;
        tmp -> prev     = NULL;
        tmp -> next     = NULL;
    }
    else{
        tail -> next    = tmp;
        tmp -> prev     = tail;
        tmp -> next     = NULL;
        tail            = tmp;
    }
}

int main(){

    Node * head         = NULL;
    Node * tail         = NULL;

    addNode( 3, head, tail );
    addNode( 8, head, tail );
    addNode( 2, head, tail );
    addNode( 4, head, tail );
    addNode( 15, head, tail );
    addNode( 11, head, tail );

    /*Node b( 5 );

    cout << b . val << endl;
    */
    printList( head );
    return 0;
}

Answer 1

If you do Node tmp, then tmp is destroyed after you exit the scope in which it was defined.

On the other hand, doing Node *tmp = new Node allocates memory for a Node on the heap and gives you a pointer tmp to it. The Node is only destroyed if and when you call delete on it.

Coming to the second part of your question, you would want to pass a pointer by reference if you have a need to modify the pointer rather than the object that the pointer is pointing to.

If you do head = tmp, tail = tmp without passing head and tail by reference, then head and tail will only retain this value until the scope of this function. This change will not reflect outside of addNode().

Answer 2

In order to modify head and tailusing function, they must be passed by reference i.e second code snippet. In first snippet, they were passed by value, any modification has done inside function addNode() will be vanished after the function out of scope.

---

case 1: pass by value

addNode(head);   // call

function body:

void addNode(Node *headCopy) {   // Node *headCopy = head,   copy is created
    headCopy = &someThing;    // the copy of head point to something else
                              // not the actual 'head' that changes its pointee
}

---

case 2: pass by reference

addNode(&head);

function body:

void addNode(Node *&headReference) {    // reference to 'head'
    headReference = &someThing;  // the actual 'head' changes its pointee
}

Answer 3

Since copy operation for raw-pointers is cheap there's no reason to pass it by reference.

void addNode( int val, Node *& head, Node *& tail ){
Node tmp( val ); // tmp - local variable
if( head == NULL ){
    head            = &tmp; // address of local variable
    tail            = &tmp; // above
    tmp . prev      = NULL;
    tmp . next      = NULL;
}
else{
    tail -> next    = &tmp; // above
    tmp . prev      = tail;
    tmp . next      = NULL;
    tail            = &tmp; // above
}
} // local variable tmp get destructed, tail head contain address of unexisting object

it's double-linked list, and change name of Node member val or parameter val in Node constructor, add head(nullptr), tail(nullptr), else it won't be NULL