What if we don't create a new node and use a pointer to insert data and make links instead (in linked list)?

Question

I was trying to implement basic operations of a Linked list using structures and classes but I usually mess up something. I am confused about memory allocation here. For example, why this program is not working correctly?

#include<iostream>
using namespace std;

struct node{
    int data;
    node* link;
};

node* head;

void insert(int x){
    node temp;
    temp.data = x;
    temp.link = head;
    head = &temp;
}

void print_list(){
    node* temp = head;
    cout<<"The list is:\n";
    while(temp!=NULL){
        cout<<temp->data<<" ";
        temp = temp->link;
    }
}

int main(){
    head = NULL;
    cout<<"How many numbers?\n";
    int n;
    cin>>n;
    while(n--){
        cout<<"\nEnter value:\n";
        int value;
        cin>>value;
        insert(value); // This function inserts node at beginning of the list
        print_list();
    }
    return 0;
}

But if I change the insert function to this, it works

void insert(int x){
   node* temp = new node();
   temp->data = x;
   temp->link = head;
   head = temp;
}

Also, could somebody please suggest me a good website to learn linked list, trees and graphs?

`head = &temp;` creates a dangling pointer, as `temp` goes out of scope when the function ends (which causes it to be destroyed) — UnholySheep, May 11 '20 at 20:33

score 1 · Accepted Answer · answered May 11 '20 at 20:48

void insert(int x){
    node temp;
    temp.data = x;
    temp.link = head;
    head = &temp;
}

Objects have a lifetime, in the function above the object denoted by the variable temp is created when the function is called and destroyed when the function exits.

But head is pointing at this object. In other words, once this function has been exited, head is pointing at an object which has been destroyed. C++ doesn't keep an object alive just because something is pointing at it. This is why your program doesn't work.

Now look at your working code

void insert(int x){
   node* temp = new node();
   temp->data = x;
   temp->link = head;
   head = temp;
}

Now the object pointed at by temp has been created using new. Objects created by new exist until they are deleted. So in this case the object still exists when the function is exited. So the code works.

All this will be explained in any half decent book on C++. If you want to learn C++ properly, you really should buy a good book.

What if we don't create a new node and use a pointer to insert data and make links instead (in linked list)?

1 Answers1