Doubly Circular Linked List – Deletion

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.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Singly linked list vs doubly linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs of deletion in circular doubly linked list

  1. How many null pointers are present in the circular doubly linked list?
  2. A circular doubly linked list contains two null pointers.

  3. How many null values are present in the circular doubly linked list?
  4. 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.

  5. What are the uses of circular linked list?
  6. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *