Insert a Node at the beginning of a Singly Linked List Using C++

Let’s start with some basic concepts behind the linked list. Why it is so popular, why it’s used in a huge range in industries? First, we will look into the fact why the linked list is so popular rather than an array. By the way, we are going to look on the linked list approach with the C++ programming language.

Why Linked list? :-

1. Suppose take an array. Insert elements into it. Now if you want to add one element within it, then there will be a problem to do so as it’s a static allocation of memory[you have to predefine the size of array whether you are getting the size and the allocating]. But the linked list doesn’t have such a concept. It’s completely a dynamic allocation. We are linking the elements. In this case, if you want to insert one element, just you have to break the link and insert the element and relink that part. That’s the main advantage to use the linked list.

Types of the Linked list: 

  1. Singly-linked list
  2. Doubly linked list
  3. Circular linked list

 The main operations, we can perform in the linked list are:-

  1. Insertion
  2. Deletion

Insertion at the Beginning of the Singly Linked List Using C++

We will first see to the program then we will discuss the program:

 #include <iostream>
 using namespace std;
 struct node
 {
 int data;
 node *next;
 }*head=NULL;

 void insert(int value) // Making of the linked list
  {
    node *newnode;
    newnode=new node;
    newnode->data=value;
    newnode->next=NULL;
   if(head==NULL)
    {
     head=newnode;
    }
   else
   {
    node *tmp=head;
    while(tmp->next != NULL)
    tmp=tmp->next;
    tmp->next=newnode;
   }
 }
 void insert_beg(int value) //insert at beginning
 {
  node *newnode;
  newnode = new node;
  newnode->data=value;
  if(head==NULL) 
   {
    head=newnode;
   }
  else 
   {
    newnode->next=head;
    head=newnode;
   }
 }

void print(node *t) //printing the corresponding linked list
 {
 cout<<"Traversing from very first:-";
 node *temp=t;
 while(temp->next != NULL) {
 cout<<temp->data<<" ";
 temp=temp->next;
 }
 cout<<temp->data<<" ";
 }

 int main()
 {
 int value,loc,position,n,i=0;
 cout<<"Enter the n value:";
 cin>>n;
 cout<<"Enter the elements you want to insert:- ";
 do
  {
   cin>>value;
   insert(value);
   i=i+1;
  }while(i<n);
 print(head);
 cout<<endl<<"Insert at first:";
 cin>>value;
 insert_beg(value);
 print(head);
 return 0;
}

In this tutorial, we are going to see about the insertion operation in the singly linked list at the beginning. All other singly list operation we will discuss later on, in the different tutorial whose link will be provided at the end of this tutorial.

Let’s explore what are the things going on inside the above code:

Part: 1

Let’s first initially look on to the main function.

int main() 
{ 
   int value,loc,position,n,i=0; 
   cout<<"Enter the n value:"; 
   cin>>n;
   cout<<"Enter the elemnts you want to insert:- ";
   do
    { 
      cin>>value; 
      insert(value); 
      i=i+1; 
    }while(i<n);
   print(head);
   cout<<endl<<"Insert at first:";
   cin>>value;
   insert_beg(value);
   print(head);
 return 0; 
}
  • Here, first, we are taking the input from the user of the size of the list.
  • Then within a do while loop we are inserting elements and one bt one passing it to the insert function. That is making the actual list.
  • Next, we have called the print function for printing where we are only passing the starting of the array.
  • The main operation is done at the very end passing the element which we are going to insert at the front of the array and printing also.

Part: 2

In this part, we will see how to create a linked list.

struct node 
{ int data; 
  node *next; 
}*head=NULL; 
void insert(int value) // Making of the linked list 
{ 
  node *newnode; 
  newnode=new node; newnode->data=value; 
  newnode->next=NULL; 
 if(head==NULL) 
  { 
    head=newnode; 
  } 
 else 
  { 
    node *tmp=head; 
    while(tmp->next != NULL) 
    tmp=tmp->next; 
    tmp->next=newnode; 
  } 
}
  • Struct node part is nothing but of the information what are the things or data attribute and their name and type ad most importantly what is the pointer name. By the way, previously I have mentioned we need a pointer to link all the elements.
    That is the thing we have made
    int data (this is for the data attribute)
    node *next (this is as a pointer)
    Here we are assigning head to null.
  • Now we will explore insert function. In this function, we will pass the values from the main function. Here what we have done is –
    1. First, we have created a blank node newnode (node *newnode).
    2. Then we have allocated its memory.(newnode =new node;).
    3. Now we have filled newnode data field with the current passing data.
    4. And we have mentioned its linked part to null as there is no link
  • if(head==null):
    Here we are checking whether there is an element present in the list or not. If the head is null, means there are no elements present inside the list. If not we assigning the head to the newnode.
  • Next, we are going to add elements inside the existing list. Here we are making a node, named as tmp and at the same time, we are making it as a head element. Then we are checking whether it’s the end of the list or not.
    If it’s not we are making to move “tmp” node to the next(tmp=tmp->next).
    If we are there at the end of the existing list. Then we are linking the list with the newnode. [tmp->next=newnode].

Now we have successfully created a linked list.

Part : 3

This part is nothing but making a function in the linked list that can enter extra element to the front of the list. Let’s have a look what’s going on inside the program.

void insert_beg(int value) //insert at beginning
  { node *newnode;
    newnode = new node;
    newnode->data=value;
    if(head==NULL)
     { 
      head=newnode;
     }
    else
     {
      newnode->next=head;
      head=newnode;
     }
  }

In the above part what we have done is, we have just created a new node which will hold the value of the element which we are going to insert at the beginning of the list. On the same note, we are checking for the existence of the list and if already element is there then,

We are making the newnode’s pointer to be linked with the current head. [newnode->next=head]

Later on, making the newnode as the head. [head=newnode]

Part:4

Here we will discuss how to print the linked list.

void print(node *t) //printing the corresponding linked list
 {
   cout<<"Traversing from very first:-";
   node *temp=t;
   while(temp->next != NULL)
    {
      cout<<temp->data<<" ";
      temp=temp->next;
    }
 cout<<temp->data<<" "; //for the current pointer value(last one)
 }

Here we are traversing the whole linked list, setting “t” (which is actually the head. As we are passing head from anywhere inside the print function. That is being assigned to as a new node). Traversing the temp up to the last until when we are not reaching to the last of the list. At the same time, we are moving temp to the next and before that printing current temp value. Very last line of this function is the printing of the temp data when its pointer mentioning the end of the list. As we can’t traversal more, so there is no chance to print that value.

Leave a Reply

Your email address will not be published.