Linked List C++ Class What is the diffence between these two add node implementations?

Question

I have written following class for linked list. There are two separate functions for adding new node (addValue1 and addValue2). One uses pointer to node, another does not.

#include <stdlib.h>
#include <iostream>

class linkedList{
private:
    struct Node {
        int data;
        Node* next;
    };
    Node* head;

public:
    linkedList(){
       //constructor
        this->head = NULL;
    }

    ~linkedList(){
        //destructor
    }

    void addValue1(int n) {
        Node* newNode = new Node();
        newNode->data = n;
        newNode->next = head;
        this->head = newNode;
    }

    void addValue2(int n) {
        Node newNode;
        newNode.data = n;
        newNode.next = head;
        this->head = &newNode;
    }

    void print(){
        Node* curNode = this->head;
        while(this->head != NULL) {
            std::cout << curNode->data << " "<< std::endl;
            curNode = curNode->next;
        }
    }

};

int main() {


    linkedList llist;

    llist.addValue2(5);
    llist.addValue1(4);
    llist.addValue1(9);
    llist.print();

}

Which one of these two is recommended and why? Is there any difference between these two? If we don't use new operator, we don't need to use the delete operator later on. This seems like an advantage to me. Is it really?

Answer 1

addValue2 will wreak havoc since you're storing a pointer to a node newNode which has automatic storage duration. The pointer &newNode will dangle once that goes out of scope.

Boom!

Note that it's also unfashionable to write the destructor out explicitly if that's what the compiler would do for you anyway. If you need to introduce the destructor in order to make it virtual then write

virtual ~linkedList() = default;

In your case though you will need to delete the nodes allocated with new else your class will leak memory.

Finally, if you don't want to worry about memory at all then use

typedef linkedList std::list;

and head off to the pub.

Answer 2

The two are very different. If one would rewrite your addNode2 to use manual allocations instead of automatic it would look like this (original code as comments):

void addValue2(int n) {
    Node* newNode = Node();   // Node newNode;
    newNode->data = n;        // newNode.data = n;
    newNode->next = head;     // newNode.next = head;
    this->head = newNode;     // this->head = &newNode;
    delete newNode;           // (newNode is deleted automatically !)
}

When you use automatic storage, objects get destroyed as soon as they go out of scope. The method alone does not do much harm, but it leaves this->head as an invalid pointer (the object newNode was pointing to no longer exists when the method returns). Dereferencing an invalid pointer is undefinded behaviour, hence in all other methods that use the pointer anything could happen (including just what you expect, which is actually the worst incarnation of undefined behaviour, because you wont spot it until it is too late).

More in line with the original code, but much simplified, this is wrong for the same reason:

int* return_invalid_pointer() {
    int x = 3;
    return &x; 
}                      // <--- x's lifetime ends here

Here x lifetime is bound to the body of the function. You can return a pointer to a local variable, but this pointer has no meaning whatsoever outside of the function, because the value it pointed to no longer exists.