C Program for Insertion at nth node in doubly linked list

Insertion at nth node in the linked list

In this section we will learn how to make C Program for Insertion at nth node in doubly linked list in which we have to input new node in the linked list according to the user demand like the position and node data.Doubly linked list is the updated version of singly linked list having two pointer previous and next so that we can move in two direction of the list.
For Example :-
Input : 14 66 84 25 74
Enter the data you want to insert : 98
Enter the position : 2
Output : 14 98 66 84 25 74

Insertion at nth node in doubly linked list using C

Working for Insertion at nth node in doubly linked list :-

  1. Take a new_node then new_node with data has to be inserted at the nth of the linked list.
  2. Lets begin traversing the linked list from head and move until the (pos – 1)th node.
  3. If you reachout the (pos- 1) node, the next pointer of the new_node is set to the address having by the next pointer of the (pos – 1) th node.
  4. Then take the next pointer of the (pos – 1) th node to point to the new_node and the previous pointer of the new_node is pointed to the (pos – 1) th node.
  5. Atlast the new_node next to previous pointer must be made to point to the new_node of the linked list.
  6. Return the new_node.

Construction of Node Structure in the doubly linked list :-

Syntax:-

struct node   
{  
    struct node *prev;   
    int data;  
    struct node *next;   
}
C program for Insertion at nth node in doubly linked list

Algorithm for inserting an element at the nth position :-

STEP 1 : IF PTR = NULL
STEP 2 : ASSIGN NEW NODE = PTR
STEP 3 : ASSIGN PTR = PTR -> NEXT
STEP 4 : ASSIGN NEW NODE -> DATA = VAL
STEP 5 : ASSIGN EXTRA = START
STEP 6 : ASSIGN I = 0 ( REPEAT 8 to 10 until I )
STEP 7 : ASSIGN EXTRA = TEMP -> NEXT
STEP 8 : IF EXTRA = NULL
STEP 9 : ASSIGN NEW NODE -> NEXT = EXTRA -> NEXT
STEP 10 : ASSIGN NEW NODE -> PREV = TEMP
STEP 11 : ASSIGN TEMP -> NEXT = NEW NODE
STEP 12 : ASSIGN TEMP -> NEXT -> PREV = NEW NODE
STEP 13 : EXIT

C Program for Insertion at nth node in doubly linked list :-

#include <stdio.h> 
#include <stdliib.h>

struct node			//structure of doubly Node 
{
  int data;
  struct node *prev;
  struct node *next;
} *head, *last;

void insert_At_Position (int data, int pos)
{
  int i;
  struct node *new_node, *extra;
  if (head == NULL)
    {
      printf (" No data found in the list!\n");
    }
  else
    {
      extra = head;
      i = 0;
      while (i < pos - 2 && extra != NULL) { extra = extra->next;
	  i++;
	}
      if (extra != NULL)
	{
	  new_node = (struct node *) malloc (sizeof (struct node));
	  new_node->data = data;
	  new_node->next = extra->next;	
	  new_node->prev = extra;	
	  if (extra->next != NULL)
	    {
	      extra->next->prev = new_node;
	    }
	  extra->next = new_node;
	}
      else
	{
	  printf ("Invalid position ,Please enter valid position : \n");
	}
    }
}

void list (int n)			//print list of nodes
{
  int i, data;
  struct node *new_node;
  if (n >= 1)
    {
      head = (struct node *) malloc (sizeof (struct node));
      printf ("Enter data for node1 : ");
      scanf ("%d", &data);
      head->data = data;
      head->prev = NULL;
      head->next = NULL;
      last = head;
      for (i = 2; i <= n; i++) { new_node = (struct node *) malloc (sizeof (struct node)); printf ("Enter data of node %d : ", i); scanf ("%d", &data); new_node->data = data;
	  new_node->prev = last;	// Now Link new node with the previous node
	  new_node->next = NULL;
	  last->next = new_node;	// Then Link previous node with the new node
	  last = new_node;	// Let Make new node as last node
	}
    }
}

void print_List ()
{
  struct node *extra;
  int n = 1;
  if (head == NULL)
    {
      printf ("\nList is empty\n");
    }
  else
    {
      extra = head;
      printf ("The doubly Linked List is here :\n");
      while (extra != NULL)	// Print the list
	{
	  printf ("%d   ", extra->data);
	  n++;
	  extra = extra->next;	// Move the current pointer to next node 
	}
    }
}

int main ()
{
  int n, data, pos, num;
  head = last = NULL;
  printf ("Enter the size of linked list : \n");	// Input the size of nodes
  scanf ("%d", &n);
  list (n);
  print_List ();
  printf ("\nEnter data for insertion at the nth of the list :\n ");
  scanf ("%d", &data);
  printf ("\nEnter the position : ");
  scanf ("%d", &pos);
  insert_At_Position (data, pos);
  print_List ();
  return 0;
}
Output :-
Enter the size of linked list : 5
Enter data for node 1 : 6
Enter data for node 2 : 71
Enter data for node 3 : 15
Enter data for node 4 : 92
Enter data for node 5 : 23
The doubly Linked List is here :
6  71  15  92  23
Enter data for insertion at the nth of the list :
35
Enter the position : 2
The doubly Linked List is here :
6  34  71  15  92  23