Insertion in Linked List
Tags: linkedlist, arrays
Published: 2022-05-19 12:40:28

There are three possibilities of inserting a node in a linked list :

1. Insert at beginning.
2. Insert at end.
3. Insert after a given position.

To understand the process of inserting a node in a linked list, you must have the knowledge of creating and displaying the linked list. To know the implementation of linked list [click here](https://www.coderlogs.com/post/627a4309752339739aa908d9/implementation-of-Linked-List-in-C--).

Lets assume that the linked list is already created as shown in fig below,

![image](https://i.ibb.co/CJ9x736/IMG-20220512-150607.jpg)

###### Fig.1 Linked list

## 1. Inserting node at beginning :

* To insert a node at beginning, first you need to create a one node using dynamic memory allocation function `malloc`.

* `malloc` assigns 8-bytes of locations whose starting address is stored into pointer `newnode` of type `struct node`.

* Enter the data into that newly created node by accessing the structure member `data` using pointer `newnode`. 

* Now to insert this new node at the beginning, copy  the pointer `head` into  the address part of  newly created node  and copy the pointer `newnode` into pointer `head`.

* Display the newly created linked list.

```
void insertAtBeg(struct node **head)
{
  struct node *newnode = (struct node *)malloc(sizeof(struct node));
  printf("\nEnter the data into new node : ");
  scanf("%d", &newnode->data);
  newnode->next = *head;
  *head = newnode;
}
```

## 2. Inserting node at end :

* To insert a node at end, first you need to create a node using dynamic memory allocation function `malloc`.

* `malloc` assigns 8-bytes of locations whose starting address is stored into pointer `newnode` of type `struct node`.

* Enter the data into that newly created node by accessing the structure member `data` using pointer `newnode`.

* To add this new node at the end of linked list, initialize the address part of newly created node to `NULL` and copy the pointer `head` into pointer `temp`.

* Now pointer `temp` is pointing to the first node so move this pointer `temp`  from first node to the last node using `while loop`. Once the `temp` points the last node, copy the pointer `newnode` into the address part of last node by accessing the structure member `next` using pointer `temp`.

* Display the newly created linked list. 

```
void insertAtEnd(struct node *head, struct node *temp)
{
  struct node *newnode = (struct node *)malloc(sizeof(struct node));
  printf("\nEnter the data into new node : ");
  scanf("%d", &newnode->data);
  newnode->next = NULL;
  temp = head;
  while(temp->next != 0)
  {
      temp = temp->next;
  }
  temp->next = newnode;
}
```

## 3. Inserting node after a given position :  

* Enter the position after which a node is to be inserted in the list and store that position value into any variable of type `int` 
Here, position variable is taken as `pos`.

* If  `pos` (entered position) is greater than the number of nodes in the linked list, then print `invalid position`. 

* If  `pos` (entered position) is less than the number of nodes in the linked list, then create a new node using `malloc`.

* Enter the data into that newly created node by accessing the structure member `data` using pointer `newnode`.

* Initialize the address part of the newly created node to `NULL` and copy the pointer `head` into pointer `temp` so that `temp` points to the first node in the list.

* Initialize an integer variable `i` to `1`. Now, simultaneously keep incrementing the variable `i` and moving the pointer `temp` from first node until variable `i` is less than  the entered position `pos` value using `while loop`.

* Copy the address part of a node to which pointer `temp`  is pointing into the address part of a new node to which pointer `newnode` is pointing by accessing structure member `next`.
 
* Copy the `newnode` into the address part of a node to which `temp` is pointing by accessing a structure member `next`.

*  Display the newly created linked list.

```
void insertAfterPos(struct node **head, struct node *temp, int count)
{
  int pos, i=1;
  printf("\nEnter the position after which the node is to be inserted : ");
  scanf("%d", &pos);
  if(pos>count)
  {
      printf("Invalid position.");
      exit(0);
  }
else
 {
   struct node *newnode = (struct node *)malloc(sizeof(struct node));
   printf("\nEnter the data into new node : ");
   scanf("%d", &newnode->data);
   newnode->next = NULL;
   temp = * head;
   while(i<pos)
   {
      temp = temp->next;
      i++;
   }
  newnode->next = temp->next;
  temp->next = newnode;
}
}

```
## C code that demonstrates the insertion in linked list :

```
#include <stdio.h>
#include <stdlib.h> 
 
struct node
{
    int data;
    struct node *next;
};  
 
int displayLL(struct node *head)
{
    int num = 0;
    struct node *temp;
    temp = head;
    temp=head;
    while(temp!=0)
    {
       printf("%d ",temp->data);
       temp = temp->next;
       num++;
    }
return num;
} 
 
void insertAfterPos(struct node **head, struct node *temp, int count)
{
   int pos, i=1;
   printf("\nEnter the position after which the node is to be inserted : ");
   scanf("%d", &pos);
   if(pos>count)
   {
      printf("Invalid position.");
      exit(0);
   }
else
{
    struct node *newnode = (struct node *)malloc(sizeof(struct node));
    printf("\nEnter the data into new node : ");
    scanf("%d", &newnode->data);
    newnode->next = NULL;
    temp = * head;
    while(i<pos)
    {
       temp = temp->next;
       i++;
     }
    newnode->next = temp->next;
    temp->next = newnode;
}
}
 
void insertAtBeg(struct node **head)
{
   struct node * newnode = (struct node *)malloc(sizeof(struct node));
   printf("\nEnter the data into new node : ");
   scanf("%d", &newnode->data);
   newnode->next = *head;
   *head = newnode;
}
 
void insertAtEnd(struct node *head, struct node *temp)
{
   struct node * newnode = (struct node *)malloc(sizeof(struct node));
   printf("\nEnter the data into new node : ");
   scanf("%d", &newnode->data);
   newnode->next = NULL;
   temp = head;
   while(temp->next != 0)
   {
       temp = temp->next;
   }
   temp->next = newnode;
}
 
int main()
{
   struct node *head = 0, *newnode, *temp; 
   int n, choice, newdata;
 
// Create Linked List //
 
   printf("Enter the number of nodes in the list : ");
   scanf("%d", &n);
   for(int i = 1; i<=n; i++)
   {
   newnode = (struct node *)malloc(sizeof(struct node));
   printf("Enter the data%d : ", i);
   scanf("%d", &newnode->data);
   newnode->next = 0;
   if(head == 0)
    {
        head = temp = newnode;
    } 
    else
       { 
        temp->next = newnode;
        temp = newnode;
       }
 }
   printf("--------------------------------\n");
   printf("Linked list : ");
   int count = displayLL(head);
   printf("\nCount = %d", count);
 
   printf("\nEnter '1' for inserting node at beginning.\nEnter '2' for inserting node at end.\nEnter '3' for inserting after given position.\n");
   scanf("%d", &choice); 
   switch(choice)
   {
     case 1:
     {
        insertAtBeg(&head);
        printf("\nLinked list after inserting a node at beginning : ");
        int count = displayLL(head);
        break;
     }
     case 2:
     {
        insertAtEnd(head, temp);
        printf("\nLinked list after inserting a node at end : ");
        int count = displayLL(head);
        break;
      }
     case 3:
      {
         insertAfterPos(&head, temp, count);
         printf("\nLinked list after inserting node after specified pos : ");
         int count = displayLL(head);
         break;
      }
    }
}
```

I own a website www.coderlogs.com where in I write similar blogs so do visit this for more such blog posts.