Deletion in Circular Linked List

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

A Circular Linked List is a list that has all the nodes connected to form a cycle, i.e., the last node points towards the head node to complete the loop of the cycle. There is no node pointing to the NULL, indicating the absence of any end node.

In this article, we will learn about the way of deleting a node from a Circular Linked List.

Problem Statement

We are given a circular linked list and a node, and our task is to delete the node with a given value X from the given Circular Linked List i.e, after operating the deletion on the Circular Linked List, the given node must not be present in the Circular Linked List.

Note: Linked list do not contain duplicate nodes (nodes having same values).

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Let’s say if the given circular linked list is:

and X = 14.

  • So now, according to the problem statement, we need to delete the node with value X from the given circular linked list. Also linked list should maintain its property of being circular after deletion of the node.
  • If node with value X is not present in the given circular linked list, then we will have to simply print Given node is not present in the list and return the head node.
  • If node with value X is present, we will delete it from the list and return the modified list.
  • In this example, node with value X = 14 is present in the list, so we delete it and return the modified list.

  • Also, you must make sure that the modified list should still be a circular linked list after deletion i.e, all the nodes are still connected forming a cycle.

Taking another example, say, If the given circular linked list is:

and X = 7.

  • So we can see that X = 7 is not present in the given linked list, so we will print Given node is not present in the list.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach

Our approach will be simple:

  • The idea is to traverse the given circular linked list and find the position of the node which we have to delete.
  • To do a traversal of the given circular linked list, we will create a new Node pointer curr, which will start from the head and traverse through each node in the list until it reaches the head again.
    • If we reach head again without finding the key (the value of the node which we have to delete) then we will simply print Given node is not present in the list and return the original list.
    • While traversing, we will also keep the track of the previously visited node using a node pointer prev. The use of the prev pointer is that when we find the node we have to delete i.e, (curr == key), we can simply make prev.next point to next of the curr node (prev.next = curr.next).

  • Thus, breaking the bond between the prev and curr. But one thing to notice here is that curr.next will still point to the next node in the list. So to break this bond we make curr.next point to NULL.

  • In this way, we will successfully delete the node we were asked to delete in the problem.

Now let's move to the alogorithm section.

Algorithm

There can persist the following cases for the deletion operation:
a) The List is empty.

  • If the given list is empty, i.e., the head is assigned as NULL, then we will return NULL from the function.

b) The given node is not present in the Circular Linked List.

  • If we have completely traversed the list and are unable to find the given node to be deleted, we will simply print Given node is not present in the list and return the head node.

c) We have found the node.

  • So, in this case, we need to keep track of the node and its previous node and can perform the suitable operations from the following:
    • If the list has only one node, then we will assign the head as NULL and return the head node.
    • If the list has more than or equal to two nodes, we will perform the below operations:
      • First, make curr pointer point to the node which we want to delete and prev pointer point to the previous node of curr.
      • Now, we will make the prev pointer point to the next of curr pointer and assign the next of curr pointer as NULL.
      • Then, if the curr pointer is the head node, we need to update the head node with the next of the head node.
      • At last, we return the head representing the new Circular Linked List.

Let's see the dry run of the above algorithm.

Dry Run


Code Implementation

class Prepbytes {
    
    static class Node {
        int data;
        Node next;
    };
    
    /* This function is used to insert a new node at the beginning of the circular linked list. */
    static Node push(Node head_ptr, int data) {
        Node ptr = new Node();
        ptr.data = data;
        ptr.next = head_ptr;
        if (head_ptr != null) {
            Node temp = head_ptr;
            while (temp.next != head_ptr)
                temp = temp.next;
            temp.next = ptr;
        } else {
            ptr.next = ptr;
            }

        head_ptr = ptr;
        return head_ptr;
    }
    
    /* This is the main function which will delete the node which have value equal to key */
    static Node deleteNode(Node head, int key) {
        if (head == null)
            return null;

        Node curr = head, prev = new Node();
        while (curr.data != key) {
            if (curr.next == head) {
                System.out.printf("\nGiven node is not found" + " in the list!!!");
                break;
            }

            prev = curr;
            curr = curr.next;
        }
        if (curr == head && curr.next == head) {
            head = null;
            return head;
        }
        if (curr == head) {
            prev = head;
            while (prev.next != head)
                prev = prev.next;
            head = curr.next;
            prev.next = head;
        } else if (curr.next == head) {
            prev.next = head;
        } else {
            prev.next = curr.next;
        }
        return head;
    }
    
    /* Once we have successfully deleted the specified node, this function will be used to print the modified list. */
    static void printList(Node head) {
        Node temp = head;
        if (head != null) {
            do {
                System.out.printf("%d ", temp.data);
                temp = temp.next;
            } while (temp != head);
        }

        System.out.printf("\n");
    }

    public static void main(String args[]) {
        Node head = null;
        head = push(head, 5);
        head = push(head, 8);
        head = push(head, 3);
        head = push(head, 4);
        head = push(head, 7);
        head = push(head, 6);
        head = push(head, 9);
        System.out.printf("List Before Deletion: ");
        printList(head);

        head = deleteNode(head, 7);

        System.out.printf("List After Deletion: ");
        printList(head);
    }
}

Output

List Before Deletion: 9 6 7 4 3 8 5
List After Deletion: 9 6 4 3 8 5

Time Complexity: O(n), where n is the number of nodes in the circular linked list. Traversing the list takes a linear amount of time. Hence, the time complexity is O(n).

So, in this blog, we have tried to explain how you can delete a node from a Circular Linked List. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Merge K sorted linked lists | Set 1
Next post Find the first node of the loop in a Linked List

Leave a Reply

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