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.