Last Updated on December 14, 2022 by Prepbytes
In this article, we will discuss the deletion in a doubly linked list in c. If you would like to ace the data structures and algorithms easily, then you are at the right place! Deletion and Insertion are the two important functions in the implementation of a doubly linked list in C.
Definition Of Doubly Linked List
Doubly linked is basically a kind of linked list that can be traversed in both directions easily as there is one more pointer that holds the address of the previous node of the linked list. The insertion and deletion process in a doubly linked list is easier as compared to a singly linked list. Even if we know the place where we have to insert or delete then that process can be done in O(1) time complexity.
Let’s Discuss deletion in a doubly linked list in c.
Test your data structure skills by taking this Data Structure and Algorithm Mock Test designed by experienced mentors at PrepBytes.
Deletion in DLL:
Similar to insertion, deletion can be done from the three positions in the doubly linked list.
- Delete from the front end
- Deletion of the inner node
- Delete from the last end
1. Delete from the front end
If the node to be deleted (i.e. del_node) is at the beginning
Change the head to the next of the del_node
Finally, free the memory of del_node. And, the linked list will look like this
Here is the implementation of deleting a node from the front end of the doubly linked list:
if (*head == del_node)
*head = del_node->next;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
free(del_node);
2. Deletion of the inner node
If del_node is an inner node (second node), we have to reset the value of the next and prev of the nodes before and after the del_node.
For the node before the del_node (i.e. first node)
Assign the value of the next of del_node to the next of the first node.
For the node after the del_node (i.e. third node)
Assign the value of prev of del_node to the prev of the third node.
Finally, we will free the memory of del_node. And, the final doubly linked list looks like this.
Here is the implementation of the deletion of an in-between node:
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
free(del_node);
3. Delete from the last end
In this case, we are deleting the last node with value D of the doubly linked list.
Here, we can simply delete the del_node and make the next node before del_node point to NULL.
The final doubly linked list looks like this.
Here is the implementation of the deletion of node at last in the doubly linked list in C:
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
Below is the complete program to test the above functions:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->prev = NULL;
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
void insertAfter(struct Node* prev_node, int new_data)
{
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
new_node->prev = prev_node;
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
void append(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
new_node->prev = last;
return;
}
void deleteNode(struct Node** head, struct Node* del_node) {
if (*head == NULL || del_node == NULL)
return;
if (*head == del_node)
*head = del_node->next;
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
free(del_node);
}
void printList(struct Node* node)
{
struct Node* last;
printf("\nTraversal in forward direction \n");
while (node != NULL) {
printf(" %d ", node->data);
last = node;
node = node->next;
}
printf("\nTraversal in reverse direction \n");
while (last != NULL) {
printf(" %d ", last->data);
last = last->prev;
}
}
int main()
{
struct Node* head = NULL;
append(&head, 2);
push(&head, 4);
push(&head, 6);
append(&head, 8);
insertAfter(head->next, 10);
printf("Created DLL is: ");
printList(head);
deleteNode(&head, head->next);
deleteNode(&head, head);
printf("\n DLL After Deletion is: ");
printList(head);
getchar();
return 0;
}
Complexity Analysis:
Time Complexity: O(1).
Since traversal of the linked list is not required, the time complexity is constant.
Auxiliary Space: O(1).
As no extra space is required, the space complexity is constant.
FAQ Related to Doubly Linked List In C
1. Where is the doubly linked list used?
Doubly linked lists can be used in navigation systems where both forward and backward traversal is required. It can be used to implement different tree data structures. It can be used to implement undo/redo operations.
2. Why is deletion easier in doubly linked lists?
If you know the node to remove in advance, the doubly-linked list lets you remove it in time O(1) while a singly-linked list would require time O(n). If you don’t know the node in advance, then it’s O(n) in both cases.
3. Is a doubly linked list linear or circular?
The doubly linked list is a linear structure but a circular doubly linked list that has its tail pointed to the head and head pointed to tail. Hence it’s a circular list.
We tried to discuss deletion in Doubly Linked List in C in this article. We hope this article gives you a better understanding of the doubly linked list. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.