.png)
Data Structure Class Notes: Doubly Linked List
- Anshika Vishwakarma
- Jun 9, 2022
- 6 min read
Mobiprep has created last-minute notes for all topics of Doubly Linked List to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Doubly Linked List.
Data Structure
Linked List
Doubly Linked List
Circular Linked List
Queues
Stacks
Hashing and Searching
Sorting
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Explain Insertion operation at the beginning of doubly linked list.
Explain Insertion operation at nth position before a node of doubly linked list.
Explain Insertion operation at nth position after a node of doubly linked list.
Explain deletion operation at nth position after a node of doubly linked list.
Explain deletion operation at nth position before a node of doubly linked list.
Explain deletion operation at the end of doubly linked list.
A doubly linked list is a linked list data structure that includes a link back to the previous node in each node in the structure. This is contrasted with a singly linked list where each node only has a link to the next node in the list. Doubly linked lists also include a field and a link to the next node in the list.
Question 1 - Explain Insertion operation at the beginning of doubly linked list.
Answer - Pseudo code:
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
Question 2 - Explain Insertion operation at nth position before a node of doubly linked list.
Answer - Pseudo code:
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
Question 3 - Explain Insertion operation at nth position after a node of doubly linked list.
Answer - Pseudo code:
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
Question 4 - Insertion operation at the end of doubly linked list.
Answer - Pseudo code:
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
Question 5 - Deletion operation at the beginning of doubly linked list.
Answer - Pseudo code:
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
Question 6 - Explain deletion operation at nth position after a node of doubly linked list.
Answer - Pseudo code:
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
Question 7 - Explain deletion operation at nth position before a node of doubly linked list.
Answer - Pseudo code:
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
Question 8 - Explain deletion operation at the end of doubly linked list.
Answer - Pseudo code:
To delete the node from the last assign null to the next of second 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
Code Implementation:
#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;
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;
}
Comments