A doubly linked list or a two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the sequence. Therefore, it consists of three parts—data, a pointer to the next node, and a pointer to the previous node.
In C, the structure of a doubly linked list can be given as,
struct node
{
struct node *prev;
int data;
struct node *next;
};
The PREV field of the first node and the NEXT field of the last node will contain NULL. The PREV field is used to store the address of the preceding node, which enables us to traverse the list in the backward direction.
1.) Inserting a New Node in a Doubly Linked List :-
In this section, we will discuss how a new node is added into an already existing doubly linked list. We will take four cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.
1.1) Inserting a Node at the Beginning of a Doubly Linked List :-
**Algorithm to insert a new node at the beginning**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 9
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> PREV = NULL
Step 6: SET NEW_NODE -> NEXT = START
Step 7: SET START -> PREV = NEW_NODE
Step 8: SET START = NEW_NODE
Step 9: EXIT
1.2) Inserting a Node at the End end of a Doubly Linked List :-
**Algorithm to insert a new node at the end**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT != NULL
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: SET NEW_NODE -> PREV = PTR
Step 11: EXIT
1.3) Inserting a Node After a Given Node in a Doubly Linked List :-
**Algorithm to insert a new node after a given node**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR -> DATA != NUM
Step 7: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 8: SET NEW_NODE -> NEXT = PTR -> NEXT
Step 9: SET NEW_NODE -> PREV = PTR
Step 10: SET PTR -> NEXT = NEW_NODE
Step 11: SET PTR -> NEXT -> PREV = NEW_NODE
Step 12: EXIT
1.4) Inserting a Node Before a Given Node in a Doubly Linked List :-
**Algorithm to insert a new node before a given node**
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR -> DATA != NUM
Step 7: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 8: SET NEW_NODE -> NEXT = PTR
Step 9: SET NEW_NODE -> PREV = PTR -> PREV
Step 10: SET PTR -> PREV = NEW_NODE
Step 11: SET PTR -> PREV -> NEXT = NEW_NODE
Step 12: EXIT
2.) Deleting a Node from a Doubly Linked List :-
In this section, we will see how a node is deleted from an already existing doubly linked list. We will take four cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Case 4: The node before a given node is deleted.
2.1> Deleting the First Node from a Doubly Linked List :-
**Algorithm to delete the first node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 6
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START -> NEXT
Step 4: SET START -> PREV = NULL
Step 5: FREE PTR
Step 6: EXIT
2.2> Deleting the Last Node from a Doubly Linked List :-
**Algorithm to delete the last node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 7
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR -> NEXT != NULL
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: SET PTR -> PREV -> NEXT = NULL
Step 6: FREE PTR
Step 7: EXIT
2.3> Deleting the Node After a Given Node in a Doubly Linked List :-
**Algorithm to delete a node after a given node **
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR -> DATA != NUM
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: SET TEMP = PTR -> NEXT
Step 6: SET PTR -> NEXT = TEMP -> NEXT
Step 7: SET TEMP -> NEXT -> PREV = PTR
Step 8: FREE TEMP
Step 9: EXIT
2.4> Deleting the Node Before a Given Node in a Doubly Linked List :-
**Algorithm to delete a node before a given node**
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR -> DATA != NUM
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: SET TEMP = PTR -> PREV
Step 6: SET TEMP -> PREV -> NEXT = PTR
Step 7: SET PTR -> PREV = TEMP -> PREV
Step 8: FREE TEMP
Step 9: EXIT
*******************
Programming Example
*******************
1. Write a program to create a doubly linked list and perform insertions and deletions in all cases.
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
struct node *next;
int data;
struct node *prev;
};
struct node *start = NULL;
struct node *create_ll(struct node *);
struct node *display(struct node *);
struct node *insert_beg(struct node *);
struct node *insert_end(struct node *);
struct node *insert_before(struct node *);
struct node *insert_after(struct node *);
struct node *delete_beg(struct node *);
struct node *delete_end(struct node *);
struct node *delete_before(struct node *);
struct node *delete_after(struct node *);
struct node *delete_list(struct node *);
int main()
{
int option;
clrscr();
do
{
printf("\n\n *****MAIN MENU *****");
printf("\n 1: Create a list");
printf("\n 2: Display the list");
printf("\n 3: Add a node at the beginning");
printf("\n 4: Add a node at the end");
printf("\n 5: Add a node before a given node");
printf("\n 6: Add a node after a given node");
printf("\n 7: Delete a node from the beginning");
printf("\n 8: Delete a node from the end");
printf("\n 9: Delete a node before a given node");
printf("\n 10: Delete a node after a given node");
printf("\n 11: Delete the entire list");
printf("\n 12: EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start = create_ll(start);
printf("\n DOUBLY LINKED LIST CREATED");
break;
case 2: start = display(start);
break;
case 3: start = insert_beg(start);
break;
case 4: start = insert_end(start);
break;
case 5: start = insert_before(start);
break;
case 6: start = insert_after(start);
break;
case 7: start = delete_beg(start);
break;
case 8: start = delete_end(start);
break;
case 9: start = delete_before(start);
break;
case 10: start = delete_after(start);
break;
case 11: start = delete_list(start);
printf("\n DOUBLY LINKED LIST DELETED");
break;
}
}while(option != 12);
getch();
return 0;
}
struct node *create_ll(struct node *start)
{
struct node *new_node, *ptr;
int num;
printf("\n Enter –1 to end");
printf("\n Enter the data : ");
scanf("%d", &num);
while(num != –1)
{
if(start == NULL)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> prev = NULL;
new_node -> data = num;
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
new_node = (struct node*)malloc(sizeof(struct node));
new_node–>data=num;
while(ptr–>next!=NULL)
ptr = ptr–>next;
ptr–>next = new_node;
new_node–>prev=ptr;
new_node–>next=NULL;
}
printf("\n Enter the data : ");
scanf("%d", &num);
}
return start;
}
struct node *display(struct node *start)
{
struct node *ptr;
ptr=start;
while(ptr!=NULL)
{
printf("\t %d", ptr -> data);
ptr = ptr -> next;
}
return start;
}
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}
struct node *insert_end(struct node *start)
{
struct node *ptr, *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr=start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> prev = ptr;
new_node -> next = NULL;
return start;
}
struct node *insert_before(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value before which the data has to be inserted:");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> next = ptr;
new_node -> prev = ptr-> prev;
ptr -> prev -> next = new_node;
ptr -> prev = new_node;
return start;
}
struct node *insert_after(struct node *start)
{
struct node *new_node, *ptr;
int num, val;
printf("\n Enter the data : ");
scanf("%d", &num);
printf("\n Enter the value after which the data has to be inserted:");
scanf("%d", &val);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
new_node -> prev = ptr;
new_node -> next = ptr -> next;
ptr -> next -> prev = new_node;
ptr -> next = new_node;
return start;
}
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
start = start -> next;
start -> prev = NULL;
free(ptr);
return start;
}
struct node *delete_end(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
ptr -> prev -> next = NULL;
free(ptr);
return start;
}
struct node *delete_after(struct node *start)
{
struct node *ptr, *temp;
int val;
printf("\n Enter the value after which the node has to deleted : ");
scanf("%d", &val);
ptr = start;
while(ptr -> data != val)
ptr = ptr -> next;
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
return start;
}
struct node *delete_before(struct node *start)
{
struct node *ptr, *temp;
int val;
printf("\n Enter the value before which the node has to deleted:");
scanf("%d", &val);
ptr = start;
while(ptr -> data != val)
{
ptr = ptr -> next;
temp = ptr -> prev;
}
if(temp == start)
{
start = delete_beg(start);
}
else
{
ptr -> prev = temp -> prev;
temp -> prev -> next = ptr;
}
free(temp);
return start;
}
struct node *delete_list(struct node *start)
{
while(start != NULL)
start = delete_beg(start);
return start;
}
Output
*****MAIN MENU *****
1: Create a list
2: Display the list
––––––––––––––––––––––––––
11: Delete the entire list
12: EXIT
Enter your option : 1
Enter –1 to end
Enter the data: 1
Enter the data: 3
Enter the data: 4
Enter the data: –1
DOUBLY LINKED LIST CREATED
Enter your option : 12
All c programming & algorithm 