How to insert a node in Linked List in C++

In this tutorial, I will be giving you a quick guide of how to insert a node in linked list data structure in C++. Now, as already I told you that there are three ways of insertion in the linked list.

  1. Adding a node at the front
  2. Inserting a node in the mid
  3. Inserting a node at the end of the  list

Adding a node at the front

Now, To add a node in the front of the list, do as follows:-

  • First is allocate memory to new node
  • Put the value in new node
  • Make next node of new node as first(head) node
  • Move the first(head) to point to the new node
void add(struct node* first, int value) 
{ 
    struct node* newnode = (struct node*) malloc(sizeof(struct node)); 
 
    newnode->data  = value; 
   
    newnode->next = (first); 
   
    first = newnode; 
}

Time Complexity: O(1)

Adding a node in the middle

If you want to add a node in middle of two nodes, do as follows. Basically, we have pointer to a node, and we will be adding new node after this given node.

  • Check if the previous node is null
  • Allocate memory to new node
  • Put the value in new node
  • Make the next of new node as next of previous node
  • Make the next of previous node as new node.
void middle(struct node* previous, int value)
 {
if (previous== NULL) 
{ printf("the given previous node cannot be NULL");
 return;
 }
 struct node* newnode =(struct node*) malloc(sizeof(struct node));

 newnode->data = value;

 newnode->next = previous->next;

 previous->next = newnode;
}

Time Complexity: O(1)

Adding a node at the end

To add a new node at the end means adding a node after the last node. Do as follows:

  • Allocate memory to new node
  • Put the value in the new node
  • Since this new node will be the last node, so its next is going to be NULL
  • If there is no node in the linked list so far, then make the new node as first(head)
  • Else search till last node is found
  • Make the next of last node point to this newly added node
void end(struct node* first, int value) 
{ 
    struct node* newnode = (struct node*) malloc(sizeof(struct node)); 
  
    struct node *lastnode = *first; 
  
    newnode->data  = value; 
   
    newnode->next = NULL; 
    if (*first == NULL) 
    { 
       *first = newnode; 
       return; 
    }   
   while (lastnode->next != NULL) 
        lastnode = lastnode->next; 
   
    lastnode->next = newnode; 
    return;     
}

Time Complexity: O(n) where n is the number of nodes in linked list since we have to traverse the complete list to find the last node.

For any queries, write your doubts in comments.

So, this was all about how to insert in linked list. Also, give a read to this article for implementation in java.

 

Leave a Reply

Your email address will not be published. Required fields are marked *