Why does declaring an instance pointer with new keyword inside a function causes problems and undefined behaviour?

Question

I am learning C++ and came across something interesting while solving challenges on the platform HackerRank. The code is from the Linked List problem. The goal is to display the linked list with the display method in the Solution class. I noticed that I have to use the new keyword while initializing a class instance for this to work otherwise the code does not detect the end of the list. Please see the following two codes and their respective outputs.

Why is the end of the linked list is not detected correctly when the new keyword is not used as in the second code example? I read on the internet that it is discouraged to use new as the pointers will need to be explicitly deleted afterwards to avoid a memory leak, so I am pretty confused.

Both codes use the same following input:

Input

4
2
3
4
1

Code 1

#include <iostream>
#include <cstddef>
using namespace std;    
class Node
{
    public:
        int data;
        Node *next;
        Node(int d){
            data=d;
            next=NULL;
        }
};
class Solution{
    public:

      Node* insert(Node *head,int data)
      {
          //Complete this method
        Node* new_node = new Node(data); //Check this line
        if (head) {
          Node *current = head;
          while(current->next) {
            current = current->next;
          }
            current->next = new_node;
        }
        else
        {
          head = new_node;

        }
        //   Node** pp = &head;
        //   while (*pp) {
        //       pp = &((*pp)->next);
        //   }
        //   *pp = new Node(data);
        return head;
   
      }

      void display(Node *head)
      {
          Node *start=head;
          while(start)
          {
              cout<<start->data<<" ";
              start=start->next;
          }
      }
};
int main()
{
    Node* head=NULL;
    Solution mylist;
    int T,data;
    cin>>T;
    while(T-->0){
        cin>>data;
        head=mylist.insert(head,data);
    }   
    mylist.display(head);
        
}

Output 1 (correct)

2 3 4 1 

Code 2

#include <iostream>
#include <cstddef>
using namespace std;    
class Node
{
    public:
        int data;
        Node *next;
        Node(int d){
            data=d;
            next=NULL;
        }
};
class Solution{
    public:

      Node* insert(Node *head,int data)
      {
          //Complete this method
        Node new_node(data);
        if (head) {
          Node *current = head;
          while(current->next) {
            current = current->next;
          }
            current->next = &new_node;
        }
        else
        {
          head = &new_node;

        }
        //   Node** pp = &head;
        //   while (*pp) {
        //       pp = &((*pp)->next);
        //   }
        //   *pp = new Node(data);
        return head;
   
      }

      void display(Node *head)
      {
          Node *start=head;
          while(start)
          {
              cout<<start->data<<" ";
              start=start->next;
          }
      }
};
int main()
{
    Node* head=NULL;
    Solution mylist;
    int T,data;
    cin>>T;
    while(T-->0){
        cin>>data;
        head=mylist.insert(head,data);
    }   
    mylist.display(head);
        
}

Output 2 (incorrect)

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1....

Answer 1

While it's true that using new requires explicit deallocation, this also means that if you are not using new, then somehow the lifetime of the object is already managed implicitly.

This is what happens in your second scenario:

Node new_node(data);
head = &new_node;

Here you are actually taking the address of a local variable and assign it to a global variable. But the local variable itself ceases to exist whenthe function returns and the address you stored is no longer valid.

When you use new, instead, the memory for the object is allocated in a standalone heap and persists as long as you don't delete it.

PS. In c++ you can (and should) use nullptr instead that NULL

Answer 2

As already explained, your data structure was pointing to a local object that had already gone out of scope when the function returned. Accessing a non-existent object results in undefined behavior.

It appears you were attempting to avoid using new. One way to avoid explicitly using new would be to use a smart pointer to represent your Node.

A solution based on unique_ptr could look something like:

struct Node;
using NodePtr = std::unique_ptr<Node>;

So instead of calling new, you would use make_unique instead.

class Node {
    friend class Solution;

    int data_;
    NodePtr next_;

    static NodePtr make (int d) {
        return std::make_unique<Node>(d);
    }

public:
    Node (int d) : data_(d) {}

};

To avoid searching for the last element, you can just maintain a reference to the last element all the time in your list. I implemented a shim called NodeRef around std::reference_wrapper that makes it act more like a pointer.

class Solution {
    NodePtr head_;
    NodeRef tail_;

public:
    Solution () : tail_(head_) {}

    void insert (int d) {
        *tail_ = Node::make(d);
        tail_ = tail_->next_;        
    }

    void display () {
        NodeRef p = head_;
        while (p) {
            std::cout << p->data_ << ' ';
            p = p->next_;
        }
    }
};

Try it online!