So I was learning how to make a linked list, and I was wondering why we need to use "new" when adding a node. Below is function that adds a node correctly:

void addNode(int value){

    Node* new_node_ptr = new Node;

    new_node_ptr->value = value;

    if (root == NULL){
        root = new_node_ptr;
        traveler = new_node_ptr;
    } else {
        traveler->next = new_node_ptr;
        traveler = new_node_ptr;
    }
}

But, since I am new to c++, when I tried to figure out how to do this by myself, instead of having the line:

Node* new_node_ptr = new Node;

I wrote:

Node new_node;
Node* new_node_ptr = &new_node;

This doesn't work. It seems that the new_node variable keeps being assigned to the same memory address each time you try to add a new node. This is simultaneously fascinating and infuriating. Could anybody explain this c++ weirdness to me?

Thanks!

3 Answers

3
Carcigenicate On

When you write

Node new_node;

The variable is created on the stack and should not be used once addNode exits. addNode loses "ownership" of that memory once the function exits, and memory associated with new_node is allowed to be used again by other parts of your program. Attempting to use it is undefined behavior and cannot be relied upon.

You must allocate memory dynamically to ensure that the life of the data extends beyond the scope of the function.

In the second case with stack allocation, if new_node is always assigned memory at the same address, that's just how it happens to work out in your test case. Depending on the order of other functions being called before addNode, that may not always happen, and likely won't consistently in a "real program".

0
Julián Palladino On

When you declare a variable without using new, you are saving a portion of memory allocated in the stack. Variables stored in the stack belong inside a function but not outside (for example, a counter, iterators, etc.).

When you declare by using new, you save a portion of memory allocated in the heap. Variables stored in the heap can be accessed in your entire program (and, by some methods, by other programs too).

You can find more detailed information in the following link: https://www.gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html

0
n.m. On
Node* new_node_ptr = new Node;

The above means "create a new node object and keep it indefinitely long".

Node new_node;
Node* new_node_ptr = &new_node;

The above does not mean "create a new node object and keep it indefinitely long".

If both versions did what you want them to do, now that would be weird, because then ithe new construct would appear to serve no legitimate purpose whatsoever.