Why can't I insert nodes after head into a C++ linked list?

Question

Could someone please help me identify the problem with the code below.

#include <iostream>

using namespace std;

struct node
{
    int a,b;
    struct node* next=NULL;
};

node* head=NULL;

void insert(int a,int b)
{
    if(head==NULL)
    {
        head=new node;
        head->a=a;
        head->b=b;
        return;
    }
    node* cur=head;
    while(cur!=NULL)
    {
        cur=cur->next;
    }
    cur=new node;
    cur->a=a;
    cur->b=b;
    return;
}

void display()
{
    node* cur=head;
    while(cur!=NULL)
    {
        cout<<cur->a<<"\t"<<cur->b<<"\n";
        cur=cur->next;
    }

}

int main()
{
    int i;
    for(i=0;i<3;++i)
    {
        insert(i,i+1);
    }
    display();
    //cout<<h->next->a;
    return 0;
}

This is the output that I get:

        0        1

It seems that I can only display the head node and none after gets inserted. If I try to access the next node after head, I get a segmentation fault. Why is that?

Answer 1

At the time of creation of any node , the next pointer of that node becomes null as per the definition of your node.

struct node
{
    int a,b;
    struct node* next=NULL;
};

Now,after the creation of start node ,the next pointer of start node is NULL.And when u created your second node ,you didn't point the next node of your first node to the second node.Then how will you be able to reach to the second node if you do not have the pointer to the second node.

So the solution will be --

void insert(int a,int b)
{

node *temp;
if(head==NULL)
    {
        head=new node;
        head->a=a;
        head->b=b;
       temp=head;
        return;
    }
    node* cur=head;
    while(cur!=NULL)
    {
        cur=cur->next;
    }
    cur=new node;
   temp->next=cur;
    cur->a=a;
    cur->b=b;
    temp=cur;
        return;
}

Answer 2

I found out the bug .While inserting , instead of sitting in a node and checking if it is null , look 1 node ahead and check if its null. Because if you don't , then the list will get broken and cpp allocates memory else where rather than to the pointer of the last list node's next branch.

Modified insert function :

void insert(int a,int b)
{
    if(head==NULL)
    {
        head=new node;
        head->a=a;
        head->b=b;
        head->next=NULL;
        return;
    }
    node* cur=head;
    while(cur->next!=NULL)
    {
        //cout<<cur->a<<"\t"<<cur->b<<"\n";;
        cur=cur->next;
    }
    cur->next=new node;
    cur->next->a=a;
    cur->next->b=b;
    return;
}

Answer 3

• While inserting, update head->next to NULL (when head is NULL) and curr->next to NULL (when some elements are already in the list) respectively.

• You are not linking head to curr. To link head and curr, you can create another pointer instead to hold the new element, say new_ptr. Keep curr such that curr->next=NULL, and then write curr->next=new_ptr.

  void insert(int a,int b)
  {
      if(head==NULL)
      {
          head=new node;
          head->a=a;
          head->b=b;
          head->next=NULL;
          return;
      }
      node* cur=head,*new_ptr;
      while(cur->next!=NULL)
      {
          cur=cur->next;
      }
      new_ptr=new node;
      new_ptr->a=a;
      new_ptr->b=b;
      new_ptr->next=NULL;
      curr->next=new_ptr;
      return;
  }
  

Answer 4

Your search code is:

node* cur=head;
while(cur!=NULL)
{
    cur=cur->next;
}
cur=new node;

At the end of the loop, you've found the right place to add the new node, but you overwrite that with cur = new node; — so you need to use something more like:

node *new_node = new node;
new_node->a = a;
new_node->b = b;
new_node->next = nullptr;
cur->next = new_node;

Or, equivalently:

cur->next = new node;
cur->next->a = a;
cur->next->b = b;
cur->next->next = nullptr;

Even better, you'd create a constructor for the struct node class, such as:

node(int a_init = 0, int b_init = 0) : a(a_init), b(b_init), next(nullptr) { }

and then:

cur->next = new node(a, b);

would do the whole initialization job.