Write a C program to create a doubly linked list and insert a new node in beginning, end or at any position in the list. How to insert a new node at beginning of a Doubly linked list. How to insert a new node at the end of a doubly linked list. How to insert a new node at any position of a doubly linked list in C. Algorithm to insert node in a doubly linked list.
Required knowledge
Basic C programming, Functions, Dynamic memory allocation, Doubly linked list
Algorithm to insert node at the beginning of a Doubly linked list
Algorithm to insert a node at the beginning of a Doubly linked list
%% Input : head {A pointer pointing to the first node of the list}
Begin:
alloc (newNode)
If (newNode == NULL) then
write ('Unable to allocate memory')
End if
Else then
read (data)
newNode.data ← data;
newNode.prev ← NULL;
newNode.next ← head;
head.prev ← newNode;
head ← newNode;
write('Node added successfully at the beginning of List')
End else
EndAlgorithm to insert node at the end of a Doubly linked list
Algorithm to insert a node at the end of Doubly linked list
%% Input : last {Pointer to the last node of doubly linked list}
Begin:
alloc (newNode)
If (newNode == NULL) then
write ('Unable to allocate memory')
End if
Else then
read (data)
newNode.data ← data;
newNode.next ← NULL;
newNode.prev ← last;
last.next ← newNode;
last ← newNode;
write ('Node added successfully at the end of List')
End else
EndAlgorithm to insert node at any position of a Doubly linked list
Algorithm to insert node at any position of doubly linked list
%% Input : head {Pointer to the first node of doubly linked list}
: last {Pointer to the last node of doubly linked list}
: N {Position where node is to be inserted}
Begin:
temp ← head
For i←1 to N-1 do
If (temp == NULL) then
break
End if
temp ← temp.next;
End for
If (N == 1) then
insertAtBeginning()
End if
Else If (temp == last) then
insertAtEnd()
End if
Else If (temp != NULL) then
alloc (newNode)
read (data)
newNode.data ← data;
newNode.next ← temp.next
newNode.prev ← temp
If (temp.next != NULL) then
temp.next.prev ← newNode;
End if
temp.next ← newNode;
write('Node added successfully')
End if
EndSteps to insert a new node in Doubly linked list
We have supposed that we want to insert a node at 3rd position.
- Traverse to N-1 node in the list. Where N is the position to insert. Say temp now points to N-1th node.
- Create a newNode that is to be inserted and assign some data to its data field.
- Connect the next address field of newNode with the node pointed by next address field of temp node.
- Connect the previous address field of newNode with the temp node.
- Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newNode.
- Connect the next address field of temp node to newNode i.e. temp->next will now point to newNode.
- Final list
Program to insert a node in doubly linked list
/**
* C program to insert a node in Doubly linked list
*/
#include <stdio.h>
#include <stdlib.h>
/*
* Basic structure of Node
*/
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
/*
* Function used in this program
*/
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtEnd(int data);
void insertAtN(int data, int position);
int main()
{
int n, data, choice=1;
head = NULL;
last = NULL;
/*
* Run forever until user chooses 0
*/
while(choice != 0)
{
/*
* Menu creation to use the program
*/
printf("============================================\n");
printf("DOUBLY LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Insert node - at beginning\n");
printf("3. Insert node - at end\n");
printf("4. Insert node - at N\n");
printf("5. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
/*
* Choose from different menu operation
*/
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("Enter data of first node : ");
scanf("%d", &data);
insertAtBeginning(data);
break;
case 3:
printf("Enter data of last node : ");
scanf("%d", &data);
insertAtEnd(data);
break;
case 4:
printf("Enter the position where you want to insert new node: ");
scanf("%d", &n);
printf("Enter data of %d node : ", n);
scanf("%d", &data);
insertAtN(data, n);
break;
case 5:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-5");
}
printf("\n\n\n\n\n");
}
return 0;
}
/**
* Creates a doubly linked list of n nodes.
* @n Number of nodes to be created
*/
void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
/*
* Create and link the head node
*/
head = (struct node *)malloc(sizeof(struct node));
printf("Enter data of 1 node: ");
scanf("%d", &data);
head->data = data;
head->prev = NULL;
head->next = NULL;
last = head;
/*
* Create and link rest of the n-1 nodes
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->prev = last; // Link new node with the previous node
newNode->next = NULL;
last->next = newNode; // Link previous node with the new node
last = newNode; // Make new node as last/previous node
}
printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");
}
}
/**
* Display content of the list from beginning to end
*/
void displayList()
{
struct node * temp;
int n = 1;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
printf("DATA IN THE LIST:\n");
while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);
n++;
/* Move the current pointer to next node */
temp = temp->next;
}
}
}
/**
* Inserts a new node at the beginning of the doubly linked list
* @data Data of the first node i.e. data of the new node
*/
void insertAtBeginning(int data)
{
struct node * newNode;
if(head == NULL)
{
printf("Error, List is Empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head; // Point to next node which is currently head
newNode->prev = NULL; // Previous node of first node is NULL
/* Link previous address field of head with newnode */
head->prev = newNode;
/* Make the new node as head node */
head = newNode;
printf("NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\n");
}
}
/**
* Inserts a new node at the end of the doubly linked list
* @data Data of the last node i.e data of the new node
*/
void insertAtEnd(int data)
{
struct node * newNode;
if(last == NULL)
{
printf("Error, List is empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = last;
last->next = newNode;
last = newNode;
printf("NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n");
}
}
/**
* Inserts a node at any position in the doubly linked list
* @data Data of the new node to be inserted
* @position Position where to insert the new node
*/
void insertAtN(int data, int position)
{
int i;
struct node * newNode, *temp;
if(head == NULL)
{
printf("Error, List is empty!\n");
}
else
{
temp = head;
i=1;
while(i<position-1 && temp!=NULL)
{
temp = temp->next;
i++;
}
if(position == 1)
{
insertAtBeginning(data);
}
else if(temp == last)
{
insertAtEnd(data);
}
else if(temp!=NULL)
{
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = temp->next; // Connect new node with n+1th node
newNode->prev = temp; // Connect new node with n-1th node
if(temp->next != NULL)
{
/* Connect n+1th node with new node */
temp->next->prev = newNode;
}
/* Connect n-1th node with new node */
temp->next = newNode;
printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position);
}
else
{
printf("Error, Invalid position\n");
}
}
}============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 1 Enter the total number of nodes in list: 3 Enter data of 1 node: 10 Enter data of 2 node: 20 Enter data of 3 node: 30DOUBLY LINKED LIST CREATED SUCCESSFULLY ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 5 DATA IN THE LIST: DATA of 1 node = 10 DATA of 2 node = 20 DATA of 3 node = 30 ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 2 Enter data of first node : 1 NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 5 DATA IN THE LIST: DATA of 1 node = 1 DATA of 2 node = 10 DATA of 3 node = 20 DATA of 4 node = 30 ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 3 Enter data of last node : 40 NODE INSERTED SUCCESSFULLY AT THE END OF LIST ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 5 DATA IN THE LIST: DATA of 1 node = 1 DATA of 2 node = 10 DATA of 3 node = 20 DATA of 4 node = 30 DATA of 5 node = 40 ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 4 Enter the position where you want to insert new node: 3 Enter data of 3 node : 15 NODE INSERTED SUCCESSFULLY AT 3 POSITION ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 5 DATA IN THE LIST: DATA of 1 node = 1 DATA of 2 node = 10 DATA of 3 node = 15 DATA of 4 node = 20 DATA of 5 node = 30 DATA of 6 node = 40 ============================================ DOUBLY LINKED LIST PROGRAM ============================================ 1. Create List 2. Insert node - at beginning 3. Insert node - at end 4. Insert node - at N 5. Display list 0. Exit -------------------------------------------- Enter your choice : 0