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....
CodePudding user response:
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
CodePudding user response:
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_;
}
}
};