Local variable pointer overwritten on each method call

Question

I am currently reading a book on data structures and learning c++ on the side. I am trying to implement a simple linked list. Below is some code for a list that can take a maximum of two elements (in order to isolate my problem). What is going wrong is the pointer declaration to the next node in the list. When I create a new Node instance and create a pointer to it, the pointer stays the same on each method call, so all elements in the list point to the same node. However, if I create a pointer directly, everything works as expected.

What I am guessing is that I have some fundamental misunderstanding of pointers, references and the new keyword.

Feel free to run the code below. The working code is commented out.

#include <iostream>
using namespace std;

template <typename T> class Node {
public:
    Node(T nvalue) {
        this->value = nvalue;
        this->next = NULL;
    }
    T value;
    Node *next;
};

template <typename T> class LinkedList {
    public:
        Node<T> *head;
        LinkedList() {
            this->head = NULL;
        }
        void append(T newVal) {
            // Correct
            // Node<T>* newNode_ptr = new Node<T>(newVal); // newNode_ptr is different on each call
            // Incorrect!?
            Node<T> newNode = Node<T>(newVal);
            Node<T> * newNode_ptr = &newNode; // newNode_ptr is the same on each call
            cout << "New Node Address: " << newNode_ptr << endl; 
            if (!(this->head)) {
                this->head = newNode_ptr;
                cout << "Value 0: " << this->head->value << endl;
            } else {
                this->head->next = newNode_ptr;
                cout << "Value 0: " << this->head->value << endl;
                cout << "Value 1: " << this->head->next->value << endl;
            }
        }
};

int main() {
    LinkedList<int> list = LinkedList<int>();
    list.append(21);
    cout << "..." << endl;
    list.append(42);
}

Note that this code is not exactly well designed (some stuff should be private, using namespace std should be avoided). I am familiar with python so this pointer stuff is a little overwhelming. Thanks for your help in advance!

Answer 1

 Node<T>* newNode_ptr = new Node<T>(newVal);

This is the more correct way of the two. It is normal that the address of newNde_ptr is different, it's what you want. Each node is a different node, two different objects cannot have the same address! The version without new gives the same address because you are creating the objects on the stack. This will not work, every node is destroyed at the end of the append function. You will see unusual results (if it doesn't crash) if you move the printing portion of append to another function. Since all your pointers point to the same address (in your case) and at the point where you print out the values that address just so happens to be a valid Node, you do not see a crash. However, this is undefined behavior and can change for any number of reasons.

The difference between free-store (heap for malloc/free) and the stack is a fundamental concept of c++. You should read about it here.

The reason I saw more correct way of the two is that you still have to remember to delete your nodes. A better way would be to use std::unique_ptr instead of raw pointers to avoid that (and may other) mistakes that using raw pointers encourages.

// Node * next; becomes
std::unique_ptr<Node> next;

// Node<T> newNode = Node<T>(newVal); becomes
newNode = std::make_unique<T>(newVal);