Deletion from a Circular Linked List

Read

Discuss(30+)

We have already discussed circular linked list and traversal in a circular linked list in the below articles:
Introduction to circular linked list
Traversal in a circular linked list
In this article, we will learn about deleting a node from a circular linked list. Consider the linked list as shown below:

cll_inserted

We will be given a node and our task is to delete that node from the circular linked list.

Examples:

Input : 2->5->7->8->10->(head node)
        data = 5
Output : 2->7->8->10->(head node)

Input : 2->5->7->8->10->(head node)
         7
Output : 2->5->8->10->(head node)

Algorithm
Case 1: List is empty.

If the list is empty we will simply return.

Case 2:List is not empty

If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.
Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.
If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr).
If the list has more than one node, check if it is the first node of the list. Condition to check this( curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.
If curr is not the first node, we check if it is the last node in the list. Condition to check this is (curr -> next == head).
If curr is the last node. Set prev -> next = head and delete the node curr by free(curr).
If the node to be deleted is neither the first node nor the last node, then set prev -> next = curr -> next and delete curr.

Complete program to demonstrate deletion in Circular Linked List:

C++14

// C++ program to delete a given key from 
// linked list. 
#include <bits/stdc++.h> 
using namespace std; 
  
/* structure for a node */
class Node { 
public: 
    int data; 
    Node* next; 
}; 
  
/* Function to insert a node at the beginning of  
a Circular linked list */
void push(Node** head_ref, int data) 
{ 
    // Create a new node and make head as next 
    // of it. 
    Node* ptr1 = new Node(); 
    ptr1->data = data; 
    ptr1->next = *head_ref; 
  
    /* If linked list is not NULL then set the  
    next of last node */
    if (*head_ref != NULL)  
    { 
        // Find the node before head and update 
        // next of it. 
        Node* temp = *head_ref; 
        while (temp->next != *head_ref) 
            temp = temp->next; 
        temp->next = ptr1; 
    } 
    else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1; 
} 
  
/* Function to print nodes in a given  
circular linked list */
void printList(Node* head) 
{ 
    Node* temp = head; 
    if (head != NULL) { 
        do { 
            cout << temp->data << " "; 
            temp = temp->next; 
        } while (temp != head); 
    } 
  
    cout << endl; 
} 
  
/* Function to delete a given node from the list */
void deleteNode(Node** head, int key)  
{ 
      
    // If linked list is empty 
    if (*head == NULL) 
        return; 
          
    // If the list contains only a single node 
    if((*head)->data==key && (*head)->next==*head) 
    { 
        free(*head); 
        *head=NULL; 
        return; 
    } 
      
    Node *last=*head,*d; 
      
    // If head is to be deleted 
    if((*head)->data==key)  
    { 
          
        // Find the last node of the list 
        while(last->next!=*head) 
            last=last->next; 
              
        // Point last node to the next of head i.e.  
        // the second node of the list 
        last->next=(*head)->next; 
        free(*head); 
        *head=last->next; 
      return; 
    } 
      
    // Either the node to be deleted is not found  
    // or the end of list is not reached 
    while(last->next!=*head&&last->next->data!=key)  
    { 
        last=last->next; 
    } 
      
    // If node to be deleted was found 
    if(last->next->data==key)  
    { 
        d=last->next; 
        last->next=d->next; 
        free(d); 
    } 
    else
        cout<<"no such keyfound"; 
    } 
  
/* Driver code */
int main() 
{ 
    /* Initialize lists as empty */
    Node* head = NULL; 
  
    /* Created linked list will be 2->5->7->8->10 */
    push(&head, 2); 
    push(&head, 5); 
    push(&head, 7); 
    push(&head, 8); 
    push(&head, 10); 
  
    cout << "List Before Deletion: "; 
    printList(head); 
  
    deleteNode(&head, 7); 
  
    cout << "List After Deletion: "; 
    printList(head); 
  
    return 0; 
} 
  
// This is code is contributed by rathbhupendra 

C

// C program to delete a given key from 
// linked list. 
#include <stdio.h> 
#include <stdlib.h> 
  
/* structure for a node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* Function to insert a node at the beginning of 
   a Circular linked list */
void push(struct Node** head_ref, int data) 
{ 
    // Create a new node and make head as next 
    // of it. 
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); 
    ptr1->data = data; 
    ptr1->next = *head_ref; 
  
    /* If linked list is not NULL then set the 
       next of last node */
    if (*head_ref != NULL) { 
        // Find the node before head and update 
        // next of it. 
        struct Node* temp = *head_ref; 
        while (temp->next != *head_ref) 
            temp = temp->next; 
        temp->next = ptr1; 
    } 
    else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1; 
} 
  
/* Function to print nodes in a given 
  circular linked list */
void printList(struct Node* head) 
{ 
    struct Node* temp = head; 
    if (head != NULL) { 
        do { 
            printf("%d ", temp->data); 
            temp = temp->next; 
        } while (temp != head); 
    } 
  
    printf("\n"); 
} 
  
/* Function to delete a given node from the list */
void deleteNode(struct Node* head, int key) 
{ 
    if (head == NULL) 
        return; 
  
    // Find the required node 
    struct Node *curr = head, *prev; 
    while (curr->data != key)  
    { 
        if (curr->next == head) 
        { 
            printf("\nGiven node is not found"
                   " in the list!!!"); 
            break; 
        } 
  
        prev = curr; 
        curr = curr->next; 
    } 
  
    // Check if node is only node 
    if (curr->next == head)  
    { 
        head = NULL; 
        free(curr); 
        return; 
    } 
  
    // If more than one node, check if 
    // it is first node 
    if (curr == head)  
    { 
        prev = head; 
        while (prev->next != head) 
            prev = prev->next; 
        head = curr->next; 
        prev->next = head; 
        free(curr); 
    } 
  
    // check if node is last node 
    else if (curr->next == head && curr == head)  
    { 
        prev->next = head; 
        free(curr); 
    } 
    else 
    { 
        prev->next = curr->next; 
        free(curr); 
    } 
} 
  
/* Driver code */
int main() 
{ 
    /* Initialize lists as empty */
    struct Node* head = NULL; 
  
    /* Created linked list will be 2->5->7->8->10 */
    push(&head, 2); 
    push(&head, 5); 
    push(&head, 7); 
    push(&head, 8); 
    push(&head, 10); 
  
    printf("List Before Deletion: "); 
    printList(head); 
  
    deleteNode(head, 7); 
  
    printf("List After Deletion: "); 
    printList(head); 
  
    return 0; 
} 

Java

// Java program to delete a given key from 
// linked list. 
import java.util.*; 
import java.io.*; 
  
public class GFG { 
  
    /* ure for a node */
    static class Node { 
        int data; 
        Node next; 
    }; 
  
    /* Function to insert a node at the beginning of  
a Circular linked list */
    static Node push(Node head_ref, int data) 
    { 
        // Create a new node and make head as next 
        // of it. 
        Node ptr1 = new Node(); 
        ptr1.data = data; 
        ptr1.next = head_ref; 
  
        /* If linked list is not null then set the  
    next of last node */
        if (head_ref != null) { 
            // Find the node before head and update 
            // next of it. 
            Node temp = head_ref; 
            while (temp.next != head_ref) 
                temp = temp.next; 
            temp.next = ptr1; 
        } 
        else
            ptr1.next = ptr1; /*For the first node */
  
        head_ref = ptr1; 
        return head_ref; 
    } 
  
    /* Function to print nodes in a given  
circular linked 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"); 
    } 
  
    /* Function to delete a given node from the list */
    static Node deleteNode(Node head, int key) 
    { 
        if (head == null) 
            return null; 
  
        // Find the required node 
        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; 
        } 
  
        // Check if node is only node 
        if (curr == head && curr.next == head) { 
            head = null; 
            return head; 
        } 
  
        // If more than one node, check if 
        // it is first node 
        if (curr == head) { 
            prev = head; 
            while (prev.next != head) 
                prev = prev.next; 
            head = curr.next; 
            prev.next = head; 
        } 
  
        // check if node is last node 
        else if (curr.next == head) { 
            prev.next = head; 
        } 
        else { 
            prev.next = curr.next; 
        } 
        return head; 
    } 
  
    /* Driver code */
    public static void main(String args[]) 
    { 
        /* Initialize lists as empty */
        Node head = null; 
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2); 
        head = push(head, 5); 
        head = push(head, 7); 
        head = push(head, 8); 
        head = push(head, 10); 
  
        System.out.printf("List Before Deletion: "); 
        printList(head); 
  
        head = deleteNode(head, 7); 
  
        System.out.printf("List After Deletion: "); 
        printList(head); 
    } 
} 
  
// This code is contributed by Arnab Kundu 
// This code is updated by Susobhan Akhuli

Python

# Python program to delete a given key from 
# linked list. 
  
# Node of a doubly linked list  
class Node:  
    def __init__(self, next = None, data = None):  
        self.next = next
        self.data = data  
  
# Function to insert a node at the beginning of  
# a Circular linked list  
def push(head_ref, data): 
  
    # Create a new node and make head as next 
    # of it. 
    ptr1 = Node() 
    ptr1.data = data 
    ptr1.next = head_ref 
  
    # If linked list is not None then set the  
    # next of last node  
    if (head_ref != None) : 
          
        # Find the node before head and update 
        # next of it. 
        temp = head_ref 
        while (temp.next != head_ref): 
            temp = temp.next
        temp.next = ptr1 
      
    else: 
        ptr1.next = ptr1 # For the first node  
  
    head_ref = ptr1 
    return head_ref 
  
# Function to print nodes in a given  
# circular linked list  
def printList( head): 
  
    temp = head 
    if (head != None) : 
        while(True) : 
            print( temp.data, end = " ") 
            temp = temp.next
            if (temp == head): 
                break
    print() 
  
# Function to delete a given node from the list  
def deleteNode( head, key) : 
  
    # If linked list is empty 
    if (head == None): 
        return
          
    # If the list contains only a single node 
    if((head).data == key and (head).next == head): 
      
        head = None
      
    last = head 
    d = None
      
    # If head is to be deleted 
    if((head).data == key) : 
          
        # Find the last node of the list 
        while(last.next != head): 
            last = last.next
              
        # Point last node to the next of head i.e.  
        # the second node of the list 
        last.next = (head).next
        head = last.next
      
    # Either the node to be deleted is not found  
    # or the end of list is not reached 
    while(last.next != head and last.next.data != key) : 
        last = last.next
  
    # If node to be deleted was found 
    if(last.next.data == key) : 
        d = last.next
        last.next = d.next
      
    else: 
        print("no such keyfound") 
      
    return head 
  
# Driver code 
  
# Initialize lists as empty  
head = None
  
# Created linked list will be 2.5.7.8.10  
head = push(head, 2) 
head = push(head, 5) 
head = push(head, 7) 
head = push(head, 8) 
head = push(head, 10) 
  
print("List Before Deletion: ") 
printList(head) 
  
head = deleteNode(head, 7) 
  
print( "List After Deletion: ") 
printList(head) 
  
# This code is contributed by Arnab Kundu 

C#

// C# program to delete a given key from 
// linked list. 
using System; 
  
class GFG { 
  
    /* structure for a node */
    public class Node { 
        public int data; 
        public Node next; 
    }; 
  
    /* Function to insert a node at the beginning of  
a Circular linked list */
    static Node push(Node head_ref, int data) 
    { 
        // Create a new node and make head as next 
        // of it. 
        Node ptr1 = new Node(); 
        ptr1.data = data; 
        ptr1.next = head_ref; 
  
        /* If linked list is not null then set the  
         next of last node */
        if (head_ref != null)  
        { 
            // Find the node before head and update 
            // next of it. 
            Node temp = head_ref; 
            while (temp.next != head_ref) 
                temp = temp.next; 
            temp.next = ptr1; 
        } 
        else
            ptr1.next = ptr1; /*For the first node */
  
        head_ref = ptr1; 
        return head_ref; 
    } 
  
    /* Function to print nodes in a given  
       circular linked list */
    static void printList(Node head) 
    { 
        Node temp = head; 
        if (head != null)  
        { 
            do 
            { 
                Console.Write("{0} ", temp.data); 
                temp = temp.next; 
            } while (temp != head); 
        } 
  
        Console.Write("\n"); 
    } 
  
    /* Function to delete a given node from the list */
    static Node deleteNode(Node head, int key) 
    { 
        if (head == null) 
            return null; 
  
        // Find the required node 
        Node curr = head, prev = new Node(); 
        while (curr.data != key) 
        { 
            if (curr.next == head)  
            { 
                Console.Write("\nGiven node is not found"
                              + " in the list!!!"); 
                break; 
            } 
  
            prev = curr; 
            curr = curr.next; 
        } 
  
        // Check if node is only node 
        if (curr.next == head && curr == head)  
        { 
            head = null; 
            return head; 
        } 
  
        // If more than one node, check if 
        // it is first node 
        if (curr == head)  
        { 
            prev = head; 
            while (prev.next != head) 
                prev = prev.next; 
            head = curr.next; 
            prev.next = head; 
        } 
  
        // check if node is last node 
        else if (curr.next == head)  
        { 
            prev.next = head; 
        } 
        else
        { 
            prev.next = curr.next; 
        } 
        return head; 
    } 
  
    /* Driver code */
    public static void Main(String[] args) 
    { 
        /* Initialize lists as empty */
        Node head = null; 
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2); 
        head = push(head, 5); 
        head = push(head, 7); 
        head = push(head, 8); 
        head = push(head, 10); 
  
        Console.Write("List Before Deletion: "); 
        printList(head); 
  
        head = deleteNode(head, 7); 
  
        Console.Write("List After Deletion: "); 
        printList(head); 
    } 
} 
  
// This code has been contributed by 29AjayKumar 

Javascript

<script> 
// javascript program to delete a given key from 
// linked list.    /* ure for a node */ 
class Node { 
    constructor() { 
        this.data = 0; 
        this.next = null; 
    } 
} 
    /* 
     * Function to insert a node at the beginning of a Circular linked list 
     */
    function push(head_ref , data) { 
        // Create a new node and make head as next 
        // of it. 
        var ptr1 = new Node(); 
        ptr1.data = data; 
        ptr1.next = head_ref; 
  
        /* 
         * If linked list is not null then set the next of last node 
         */
        if (head_ref != null) { 
            // Find the node before head and update 
            // next of it. 
            var temp = head_ref; 
            while (temp.next != head_ref) 
                temp = temp.next; 
            temp.next = ptr1; 
        } else
            ptr1.next = ptr1; /* For the first node */
  
        head_ref = ptr1; 
        return head_ref; 
    } 
  
    /* 
     * Function to print nodes in a given circular linked list 
     */
    function printList(head) { 
    var temp = head; 
        if (head != null) { 
            do { 
                document.write( temp.data+" "); 
                temp = temp.next; 
            } while (temp != head); 
        } 
  
        document.write("<br/>"); 
    } 
  
    /* Function to delete a given node from the list */
    function deleteNode(head , key) { 
        if (head == null) 
            return null; 
  
        // Find the required node 
        var curr = head, prev = new Node(); 
        while (curr.data != key) { 
            if (curr.next == head) { 
                document.write("<br/>Given node is not found" + " in the list!!!"); 
                break; 
            } 
  
            prev = curr; 
            curr = curr.next; 
        } 
  
        // Check if node is only node 
        if (curr == head && curr.next == head) { 
            head = null; 
            return head; 
        } 
  
        // If more than one node, check if 
        // it is first node 
        if (curr == head) { 
            prev = head; 
            while (prev.next != head) 
                prev = prev.next; 
            head = curr.next; 
            prev.next = head; 
        } 
  
        // check if node is last node 
        else if (curr.next == head) { 
            prev.next = head; 
        } else { 
            prev.next = curr.next; 
        } 
        return head; 
    } 
  
        /* Driver code */
      
        /* Initialize lists as empty */
        var head = null; 
  
        /* Created linked list will be 2.5.7.8.10 */
        head = push(head, 2); 
        head = push(head, 5); 
        head = push(head, 7); 
        head = push(head, 8); 
        head = push(head, 10); 
  
        document.write("List Before Deletion: "); 
        printList(head); 
  
        head = deleteNode(head, 7); 
  
        document.write("List After Deletion: "); 
        printList(head); 
  
// This code contributed by umadevi9616  
</script> 

Output

List Before Deletion: 10 8 7 5 2 
List After Deletion: 10 8 5 2

Time Complexity: O(n), Worst case occurs when the element to be deleted is the last element and we need to move through the whole list.
Auxiliary Space: O(1), As constant extra space is used.

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 13 Sep, 2023