Last Updated on November 18, 2022 by Prepbytes
As we know that circular doubly linked list is also a two way list which makes the implementation easy and efficient except for the extra space as it contains three parts of node. In the below article lets just see how circular doubly linked list deletion happens.
Problem Statement of deletion in circular doubly linked list
In this question, we are given a doubly circular linked list and a ‘Key’. We have to delete the first occurrence of this ‘Key’ in the list.
Problem Statement Understanding of circular doubly linked list deletion
Suppose the given circular doubly linked list is:
and the key is 2. So, we have to find the node with the value 2 and delete it.
The final linked list will be:
Input
The given Doubly Circular Linked List.
Key** – 2
Output
The final Doubly Circular Linked List after deletion:
Explanation: As we can see, the first occurrence of key – 2 is deleted from the doubly circular linked list.
This question is not a very complex one. We just have to keep in mind that this is a circular as well as a doubly-linked list. During the deletion, we have to take special care of the link changing part. Let us have a glance at the approach.
Approach of circular doubly linked list deletion
Firstly, we will check if the given list is empty or not. If it is empty, then we will simply return it.
Now, we will create two pointers current and previous. The current pointer will point to the head of the list and the previous pointer will point to NULL. Now, we are going to traverse through the list using the current pointer till we find the node that is to be deleted.
If the node is found, then we have three cases:
1) If the node is the head node, then we will delete it, make the second node as head and the last node will now point to the new head.
2) If the node is the last node, then we will remove the tail node, and make the second last node the tail node. Now, the new tail node will point to the head node.
3) If the node is neither the head nor the tail of the list, then we will simply delete the node by changing links.
Algorithm of deletion in circular doubly linked list
- If the list is empty, return.
- If the list is not empty, create two nodes, say, current and previous. Current will point to the head and previous will point to NULL.
- Traverse using the current pointer to find the node that is to be deleted. In every traversal, we have to make the current as previous as this is a doubly circular linked list.
- Now, if the node is found but is the only node present in the list, then we will make the head NULL and return.
- If the found node is the head node i.e. if ( current==head ), move previous to the last node. Now, do head = head -> next. The node has been deleted successfully, but now, the last node will point to the new head and to do so make prev -> next = head and head -> prev = previous. By doing this, all the required links have been changed. In the end, free the node pointed by the current.
- If the found node is the tail node i.e. if ( current -> next == head ), then the second last node will now point to the head node and to do so make previous -> next = head and head ->prev = previous. By doing this, the links have been successfully changed. In the end, free the node pointed by the current.
- If the found node is neither the first nor the last, then we will simply store the next of current in temp. Now, the previous will point to the temp and the prev of temp will point to the previous. In the end, free the node pointed by the current.
Dry Run of circular doubly linked list deletion
Code Implementation of deletion in circular doubly linked list
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void insert(struct Node** start, int value)
{
if (*start == NULL) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
struct Node* last = (*start)->prev;
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
void deleteNode(struct Node** start, int key)
{
if (*start == NULL)
return;
struct Node *curr = *start, *prev_1 = NULL;
while (curr->data != key) {
if (curr->next == *start) {
printf("\nList doesn't have node with value = %d", key);
return;
}
prev_1 = curr;
curr = curr->next;
}
if (curr->next == *start && prev_1 == NULL) {
(*start) = NULL;
free(curr);
return;
}
if (curr == *start) {
prev_1 = (*start)->prev;
*start = (*start)->next;
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
else if (curr->next == *start) {
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
else {
struct Node* temp = curr->next;
prev_1->next = temp;
temp->prev = prev_1;
free(curr);
}
}
void display(struct Node* start)
{
struct Node* temp = start;
while (temp->next != start) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
int main()
{
struct Node* start = NULL;
insert(&start, 1);
insert(&start, 2);
insert(&start, 3);
insert(&start, 4);
printf("List Before Deletion: ");
display(start);
deleteNode(&start, 2);
printf("\nList After Deletion: ");
display(start);
return 0;
}
#include <bits stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void insert(struct Node** start, int value)
{
if (*start == NULL) {
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
Node* last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
void deleteNode(struct Node** start, int key)
{
if (*start == NULL)
return;
struct Node *curr = *start, *prev_1 = NULL;
while (curr->data != key) {
if (curr->next == *start) {
printf("\nList doesn't have node with value = %d", key);
return;
}
prev_1 = curr;
curr = curr->next;
}
if (curr->next == *start && prev_1 == NULL) {
(*start) = NULL;
free(curr);
return;
}
if (curr == *start) {
prev_1 = (*start)->prev;
*start = (*start)->next;
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
else if (curr->next == *start) {
prev_1->next = *start;
(*start)->prev = prev_1;
free(curr);
}
else {
struct Node* temp = curr->next;
prev_1->next = temp;
temp->prev = prev_1;
free(curr);
}
}
void display(struct Node* start)
{
struct Node* temp = start;
while (temp->next != start) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
int main()
{
struct Node* start = NULL;
insert(&start, 1);
insert(&start, 2);
insert(&start, 3);
insert(&start, 4);
printf("List Before Deletion: ");
display(start);
deleteNode(&start, 2);
printf("\nList After Deletion: ");
display(start);
return 0;
}
public class PrepBytes {
static class Node {
int data;
Node next;
Node prev;
};
static Node insert(Node start, int value)
{
if (start == null) {
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return start;
}
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
return start;
}
static Node deleteNode(Node start, int key)
{
if (start == null)
return null;
Node curr = start, prev_1 = null;
while (curr.data != key) {
if (curr.next == start) {
System.out.printf("\nList doesn't have node with value = %d", key);
return start;
}
prev_1 = curr;
curr = curr.next;
}
if (curr.next == start && prev_1 == null) {
(start) = null;
return start;
}
if (curr == start) {
prev_1 = (start).prev;
start = (start).next;
prev_1.next = start;
(start).prev = prev_1;
}
else if (curr.next == start) {
prev_1.next = start;
(start).prev = prev_1;
}
else {
Node temp = curr.next;
prev_1.next = temp;
temp.prev = prev_1;
}
return start;
}
static void display(Node start)
{
Node temp = start;
while (temp.next != start) {
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("%d ", temp.data);
}
public static void main(String args[])
{
Node start = null;
start = insert(start, 1);
start = insert(start, 2);
start = insert(start, 3);
start = insert(start, 4);
System.out.printf("List Before Deletion: ");
display(start);
start = deleteNode(start, 2);
System.out.printf("\nList After Deletion: ");
display(start);
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
def insert( start, value):
if (start == None):
new_node = Node(0)
new_node.data = value
new_node.next = new_node.prev = new_node
start = new_node
return start
last = (start).prev
new_node = Node(0)
new_node.data = value
new_node.next = start
(start).prev = new_node
new_node.prev = last
last.next = new_node
return start
def deleteNode(start, key):
if (start == None):
return None
curr = start
prev_1 = None
while (curr.data != key) :
if (curr.next == start) :
print ("List doesn't have node",
"with value = ", key)
return start
prev_1 = curr
curr = curr.next
if (curr.next == start and prev_1 == None) :
(start) = None
return start
if (curr == start) :
prev_1 = (start).prev
start = (start).next
prev_1.next = start
(start).prev = prev_1
elif (curr.next == start) :
prev_1.next = start
(start).prev = prev_1
else :
temp = curr.next
prev_1.next = temp
temp.prev = prev_1
return start
def display(start):
temp = start
while (temp.next != start) :
print (temp.data, end = " ")
temp = temp.next
print (temp.data)
if __name__=='__main__':
start = None
start = insert(start, 1)
start = insert(start, 2)
start = insert(start, 3)
start = insert(start, 4)
print ("List Before Deletion: ")
display(start)
start = deleteNode(start, 2)
print ("List After Deletion: ")
display(start)
Output
List Before Deletion: 1 2 3 4
List After Deletion: 1 3 4
Space Complexity: O(1), as only temporary variables are being created.
Conclusion
So, in this article, We understood how circular doubly linked list deletion happens. The question isn’t a complex one, but the link changing part is a bit tricky. Hence, it is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.
FAQs of deletion in circular doubly linked list
- How many null pointers are present in the circular doubly linked list?
- How many null values are present in the circular doubly linked list?
- What are the uses of circular linked list?
A circular doubly linked list contains two null pointers.
As the circular doubly linked list’s last node points to the head of the first node, it is not possible to have null values in the list.
A circular doubly linked list is used to manage the resources of a computer. Data structures such as stacks and queues are generally implemented using circular linked lists.