Before start discussing on “Insert a node in the doubly linked list?” First, I will put a light on a “singly linked list”, A singly linked list is a collection of nodes in which a node consists of a data part and pointer part. The data part store the value (maybe integer, character, and floating etc.) and pointer part store the address of the next node (as shown in image mention below).
You can read this article, Pointer in C
Doubly linked list traversed in the forward and backward direction. A doubly linked list consists of a data part and two pointers (next and previous) in which one pointer store the address of the next node and another one store the address of the previous node.
Insertion operation in the doubly linked list has been done in various ways:
1. Insert a node at the beginning.
2. Insert a node after a node.
3. Insert a node at the end.
You can also see how to insert a node in a single linked list, check the article
Insert a node at the front
An algorithm to insert a node at the front of the doubly linked list.
Step1:
Create a HEAD pointer which points to the first node of the linked list.
Step2:
Create a new node TEMP and assign the value.
TEMP ->DATA = NEW_VALUE; TEMP->PREV = NULL; TEMP->NEXT = NULL;
STEP3:
if(HEAD ==NULL)
Then, move the address of the new node TEMP into HEAD.
if(HEAD != NULL)
then, TEMP node next pointer stores the value of the HEAD (Address of the first node) and HEAD pointer stores the address of the TEMP.
TEMP->next = HEAD; //TEMP store address of the first node
HEAD = TEMP; //HEAD point to the TEMP
C Program to insert a node at the front in the doubly linked list
In the below program, I am inserting a few nodes at the beginning of the doubly linked list.
#include <stdio.h>
#include <stdlib.h>
// Node of a doubly linked list
struct node
{
struct node *prev;
int data;
struct node *next;
};
void create(struct node** root, int new_value);
void print (struct node* root);
int main ()
{
struct node* head = NULL;
//Insert 10 in begning
create (&head,10);
//Insert 20 in begning
create (&head,20);
//Insert 30 in begning
create (&head,30);
//Insert 40 in begning
create (&head,40);
//Insert 50 in begning
create (&head,50);
//Insert 60 in begning
create (&head,60);
//print the linked list
print(head);
return 0;
}
void create (struct node** root, int new_value)
{
struct node *temp= malloc(sizeof (struct node)); //allocate node
temp->data = new_value; //put data into new_node
temp->prev = NULL;
temp->next = NULL;
//If the linked list is empty, then make the new node as a head.
if (*root==NULL)
{
(*root)= temp;
}
else
{
(*root)->prev = temp; //change prev of head node to new node
temp->next=(*root);
(*root)=temp; //Move the head to pint the new node
}
}
//Function to print data values of the linked list
void print(struct node* root)
{
struct node* temp1=root;
while (temp1!= NULL)
{
printf(" data=%d \n", temp1->data);
//temp1=root;
temp1 = temp1->next;
}
}
Insert a node after a node in the doubly linked list
Step1: Calculate the length of the doubly linked list
Step2: Create a new node TEMP.
Step3: Enter a location and move head pointer until it reaches the desired location.
See an example,
In below example, I am inserting the node after the given position.
#include <stdio.h>
#include <stdlib.h>
// Node of a doubly linked list
struct node
{
struct node *prev;
int data;
struct node *next;
};
void create(struct node** root, int new_value);
void add_node_after_node(struct node** root, int len, int new_value);
int length(struct node* root);
void print (struct node* root);
int main ()
{
int len = 0; //list length
struct node* head = NULL;
create (&head,10);
create (&head,20);
create (&head,30);
create (&head,40);
//Get length
len =length(head);
add_node_after_node(&head,len,70);
return 0;
}
//Function to create a doubly linked list
void create (struct node** root, int new_value)
{
struct node *temp;
temp=(struct node*)malloc(sizeof (struct node));
if(temp == NULL)
{
return;
}
temp->data = new_value;
temp->prev = NULL;
temp->next = NULL;
if (*root==NULL)
{
(*root)= temp;
}
else
{
struct node *ptr;
ptr = (*root);
while (ptr->next !=NULL)
{
ptr=ptr->next;
}
temp->prev=ptr;
ptr->next=temp;
}
}
//Function to print the elements of the linked list
void print(struct node* root)
{
struct node* temp1=root;
while (temp1!= NULL)
{
printf(" data=%d \n", temp1->data);
//temp1=root;
temp1 = temp1->next;
}
}
//Function to calculate the length of the doubly linked list
int length(struct node* root)
{
struct node *temp = root; int count = 0;
while (temp!=NULL)
{
count++;
temp=temp->next;
}
printf ("Linked list length = %d\n", count);
return count;
}
//Function to insert a node at the middle of the doubly linked list
void add_node_after_node(struct node** root,int len, int new_value)
{
int location =0;
printf ("Location to insert a node = ");
scanf ("%d",&location);
if ((location < 1) || (location > len))
{
printf (" Location does not exist\n\n");
return;
}
else
{
struct node *temp, *qtr;
temp = (struct node*)malloc (sizeof (struct node));
if(temp == NULL)
{
return;
}
temp->data = new_value;
temp->prev=NULL;
temp->next= NULL;
qtr = (*root);
while (--location)
{
qtr=qtr->next;
}
temp->next=qtr->next;
temp->prev=qtr;
if (qtr->next!=NULL)
{
qtr->next->prev = temp;
}
qtr->next=temp;
}
//print the list
print(*root);
}
Insert a node at the end of the doubly linked list
An algorithm to insert a node at the end of the linked list.
Step1:
Create a HEAD pointer which points to the first node of the linked list.
Step2:
Create a new node TEMP.
TEMP ->DATA = NEW_VALUE; TEMP->PREV = NULL; TEMP->NEXT = NULL;
STEP3:
if (HEAD ==NULL) Then, move the address of the new node TEMP into HEAD else, Traverse pointer until reached the last node, Assign HEAD to TEMP->prev and TEMP to Head->next.
#include <stdio.h>
#include <stdlib.h>
// Node in the linked list
struct node
{
struct node *prev;
int data;
struct node *next;
};
void node_at_end(struct node** root, int new_value);
void print (struct node* root);
int main()
{
struct node* head = NULL;
node_at_end(&head,10);
node_at_end(&head,20);
node_at_end(&head,30);
node_at_end(&head,40);
node_at_end(&head,50);
node_at_end(&head,60);
print(head);
return 0;
}
void node_at_end(struct node** root, int new_value)
{
struct node *temp;
temp=(struct node*)malloc(sizeof (struct node));
temp->data = new_value; //put data
temp->prev = NULL;
temp->next = NULL; //New node is add at the last, so we are putting NULL at node's next
//If the linked list is empty, and then makes the new node as the head
if (*root==NULL)
{
(*root)= temp;
}
else
{
struct node *ptr;
ptr = (*root);
// Traverse pointer until reached last node
while (ptr->next !=NULL)
{
ptr=ptr->next;
}
temp->prev=ptr;
ptr->next=temp;
}
}
void print(struct node* root)
{
struct node* temp1=root;
while (temp1!= NULL)
{
printf(" data=%d \n", temp1->data);
//temp1=root;
temp1 = temp1->next;
}
}
