Close Menu
Data Structures

Deletion from a Circular Linked List: A Comprehensive Guide

By

A circular linked list is a fascinating data structure where the last node connects back to the first node, forming a loop. This structure has unique advantages, such as efficient traversal, as the end of the list naturally leads back to the beginning. However, it also introduces challenges, especially when performing deletion operations.

In this article, we delve into how to delete a node from a circular linked list in various scenarios while maintaining the circular nature of the list.

Deletion involves careful consideration of pointers to ensure the list remains connected correctly. There are three main types of deletion operations in a circular linked list:

  • Deletion at the beginning
  • Deletion at a specific position
  • Deletion at the end

1. Deletion at the Beginning of a Circular Linked List

When deleting the first node of a circular linked list, the most critical aspect is ensuring the list remains circular. If the list contains only one node, the deletion operation becomes a straightforward removal, leaving the list empty. For lists with multiple nodes, we adjust the last node’s next pointer to point to the second node, effectively bypassing the first node. This maintains the circular property while removing the unwanted node.

Delete the first node in circular linked list

Step-by-Step Process for Deletion at the Beginning

  • Check if the List is Empty
    • If the list is empty (i.e., last is nullptr), print a message like “List is empty” and return nullptr. This check ensures no undefined operations occur.
  • Get the Head Node
    • Retrieve the head node by setting head = last->next. The head is the first node following the last node in the circular list.
  • Check for a Single Node
    • If the head is equal to last, it indicates that there is only one node in the list. In this case:
      • Delete the head node.
      • Set last = nullptr, as the list is now empty.
  • Handle Multiple Nodes
    • For lists with more than one node:
      • Update last->next to point to head->next, effectively bypassing the first node.
      • Delete the head node to free up memory.
  • Return the Updated last Pointer
    • Return the pointer to the last node, which now connects directly to the new head node.

Code Implementation in Multiple Programming Languages

C Programming

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a node
struct Node {
    int data;
    struct Node* next;
};

// Function to delete the first node in the circular linked list
struct Node* deleteFirstNode(struct Node* last) {
    if (last == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    struct Node* head = last->next;
    if (head == last) {
        free(head);
        return NULL;
    }

    last->next = head->next;
    free(head);

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* head = last->next;
    do {
        printf("%d ", head->data);
        head = head->next;
    } while (head != last->next);

    printf("\n");
}

// Function to create a new node with the given value
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Main function
int main() {
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    struct Node* last = first->next->next;
    last->next = first;

    printf("Original list: ");
    printList(last);

    last = deleteFirstNode(last);

    printf("List after deleting first node: ");
    printList(last);

    return 0;
}

C++ Implementation

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

// Function to delete the first node
Node* deleteFirstNode(Node* last) {
    if (!last) {
        cout << "List is empty" << endl;
        return nullptr;
    }

    Node* head = last->next;
    if (head == last) {
        delete head;
        return nullptr;
    }

    last->next = head->next;
    delete head;

    return last;
}

// Function to print the list
void printList(Node* last) {
    if (!last) {
        cout << "List is empty." << endl;
        return;
    }

    Node* head = last->next;
    do {
        cout << head->data << " ";
        head = head->next;
    } while (head != last->next);

    cout << endl;
}

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// Main function
int main() {
    Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    last = deleteFirstNode(last);

    cout << "List after deleting first node: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;
    public Node Next;

    public Node(int data) {
        Data = data;
        Next = null;
    }
}

class CircularLinkedList {
    public Node Last;

    public void DeleteFirstNode() {
        if (Last == null) {
            Console.WriteLine("List is empty");
            return;
        }

        Node head = Last.Next;
        if (head == Last) {
            Last = null;
            return;
        }

        Last.Next = head.Next;
    }

    public void PrintList() {
        if (Last == null) {
            Console.WriteLine("List is empty.");
            return;
        }

        Node head = Last.Next;
        do {
            Console.Write(head.Data + " ");
            head = head.Next;
        } while (head != Last.Next);

        Console.WriteLine();
    }

    public void CreateNode(int[] values) {
        foreach (var value in values) {
            Node newNode = new Node(value);
            if (Last == null) {
                Last = newNode;
                Last.Next = Last;
            } else {
                newNode.Next = Last.Next;
                Last.Next = newNode;
                Last = newNode;
            }
        }
    }
}

class Program {
    static void Main() {
        CircularLinkedList list = new CircularLinkedList();
        list.CreateNode(new int[] { 2, 3, 4 });

        Console.WriteLine("Original list: ");
        list.PrintList();

        list.DeleteFirstNode();

        Console.WriteLine("List after deleting first node: ");
        list.PrintList();
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    Node last;

    // Delete the first node
    public void deleteFirstNode() {
        if (last == null) {
            System.out.println("List is empty");
            return;
        }

        Node head = last.next;
        if (head == last) {
            last = null;
            return;
        }

        last.next = head.next;
    }

    // Print the circular linked list
    public void printList() {
        if (last == null) {
            System.out.println("List is empty.");
            return;
        }

        Node head = last.next;
        do {
            System.out.print(head.data + " ");
            head = head.next;
        } while (head != last.next);

        System.out.println();
    }

    // Create a circular linked list from an array of values
    public void createList(int[] values) {
        for (int value : values) {
            Node newNode = new Node(value);
            if (last == null) {
                last = newNode;
                last.next = last;
            } else {
                newNode.next = last.next;
                last.next = newNode;
                last = newNode;
            }
        }
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.createList(new int[] { 2, 3, 4 });

        System.out.println("Original list:");
        list.printList();

        list.deleteFirstNode();

        System.out.println("List after deleting first node:");
        list.printList();
    }
}
  • Step-by-Step Explanation
    • Node Definition: A Node class is defined with two fields: data for storing the value and next for pointing to the next node.
    • CircularLinkedList Class:
      • last points to the last node in the circular linked list.
      • Methods like deleteFirstNode(), printList(), and createList() are provided to manage the list.
    • createList(): Creates the circular linked list from an array of integers.
    • deleteFirstNode():
      • Handles the cases where the list is empty, has only one node, or has multiple nodes.
      • Updates the last pointer to maintain the circular structure after deletion.
    • printList(): Prints all nodes in the list starting from the node after last.
    • Main Method: Creates the list, prints it, deletes the first node, and prints the updated list.

JavaScript Implementation

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class CircularLinkedList {
    constructor() {
        this.last = null;
    }

    deleteFirstNode() {
        if (this.last === null) {
            console.log("List is empty");
            return;
        }

        let head = this.last.next;
        if (head === this.last) {
            this.last = null;
            return;
        }

        this.last.next = head.next;
    }

    printList() {
        if (this.last === null) {
            console.log("List is empty.");
            return;
        }

        let head = this.last.next;
        let result = [];
        do {
            result.push(head.data);
            head = head.next;
        } while (head !== this.last.next);

        console.log(result.join(" "));
    }

    createList(values) {
        values.forEach(value => {
            const newNode = new Node(value);
            if (this.last === null) {
                this.last = newNode;
                this.last.next = this.last;
            } else {
                newNode.next = this.last.next;
                this.last.next = newNode;
                this.last = newNode;
            }
        });
    }
}

// Main program
const list = new CircularLinkedList();
list.createList([2, 3, 4]);

console.log("Original list:");
list.printList();

list.deleteFirstNode();

console.log("List after deleting first node:");
list.printList();
  • Step-by-Step Explanation
    • Node Class: A Node class is defined with properties data (to store value) and next (to store the reference to the next node).
    • CircularLinkedList Class:
      • last points to the last node.
      • Methods include deleteFirstNode(), printList(), and createList().
    • createList(): Iterates through the given array to build the circular linked list.
    • deleteFirstNode():
      • Checks if the list is empty.
      • If there’s only one node, sets last to null.
      • Otherwise, adjusts the last.next pointer to bypass the first node.
    • printList(): Uses a loop to traverse and print all node values.
    • Main Program: Creates a list, prints it, deletes the first node, and prints the updated list.

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.last = None

    def delete_first_node(self):
        if self.last is None:
            print("List is empty")
            return

        head = self.last.next
        if head == self.last:
            self.last = None
            return

        self.last.next = head.next

    def print_list(self):
        if self.last is None:
            print("List is empty.")
            return

        head = self.last.next
        result = []
        while True:
            result.append(head.data)
            head = head.next
            if head == self.last.next:
                break

        print(" ".join(map(str, result)))

    def create_list(self, values):
        for value in values:
            new_node = Node(value)
            if self.last is None:
                self.last = new_node
                self.last.next = self.last
            else:
                new_node.next = self.last.next
                self.last.next = new_node
                self.last = new_node

# Main program
list = CircularLinkedList()
list.create_list([2, 3, 4])

print("Original list:")
list.print_list()

list.delete_first_node()

print("List after deleting first node:")
list.print_list()
  • Step-by-Step Explanation
    • Node Class: Defines a node with data (value) and next (reference).
    • CircularLinkedList Class:
      • last stores the reference to the last node.
      • delete_first_node() handles deletion while maintaining the circular structure.
    • create_list(): Constructs the list from an array of values.
    • delete_first_node(): Deletes the first node while ensuring circularity.
    • print_list(): Traverses and prints the list in a circular manner.
    • Main Program: Creates, displays, deletes, and re-displays the list.

Output

Original list:
2 3 4
List after deleting first node:
3 4

Complexities

  • Time Complexity: O(1)
  • Auxiliary Space: O(1)

2. Deletion at a Specific Position in a Circular Linked List

Deleting a node at a specific position adds complexity, as we need to locate the node to delete and adjust the surrounding pointers carefully. The key is to ensure the list remains circular, even if the deleted node is the first or last node.

Delete a specific node in circular linked list

Step-by-Step Process for Deletion at a Specific Position

  • Check if the List is Empty
    • If last is nullptr, print “List is empty, nothing to delete” and return nullptr.
  • Set Initial Pointers
    • Initialize two pointers:
      • curr to point to the head (last->next).
      • prev to point to the last node (last).
  • Check for Single Node
    • If the list contains only one node and its data matches the key:
      • Delete the node.
      • Set last = nullptr, as the list becomes empty.
  • Handle Deletion of the First Node
    • If the data in the head matches the key:
      • Update last->next to point to head->next.
      • Delete the head node.
  • Traverse the List to Find the Target Node
    • Use a loop to find the node with the specified key:
      • If found, update prev->next to bypass the curr node.
      • If the node is the last node, update last to point to prev.
  • Handle Node Not Found
    • If no node with the specified key exists, print “Node with data [key] not found.”
  • Return the Modified last Pointer
    • Return the pointer to the last node, ensuring the list remains intact.

Code Implementation in Multiple Programming Languages

C Programming

#include <stdio.h>
#include <stdlib.h>

// Define the structure of a node
struct Node {
    int data;            // Data stored in the node
    struct Node* next;   // Pointer to the next node in the circular linked list
};

// Function to delete a specific node by value
struct Node* deleteNode(struct Node* last, int value) {
    if (last == NULL) { // Case 1: List is empty
        printf("List is empty.\n");
        return NULL;
    }

    struct Node *curr = last->next, *prev = last;

    // Case 2: If the node to delete is the first node
    if (curr->data == value) {
        if (curr == last) { // Single node in the list
            free(curr);
            return NULL;
        }
        last->next = curr->next; // Skip the head node
        free(curr);
        return last;
    }

    // Case 3: Traverse the list to find the node to delete
    do {
        if (curr->data == value) { // Node found
            prev->next = curr->next;
            if (curr == last) // Update last if last node is deleted
                last = prev;
            free(curr);
            return last;
        }
        prev = curr;
        curr = curr->next;
    } while (curr != last->next);

    printf("Value %d not found in the list.\n", value);
    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct Node* temp = last->next;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != last->next);
    printf("\n");
}

// Function to create a new node with the given value
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    struct Node* last = first->next->next;
    last->next = first;

    printf("Original list: ");
    printList(last);

    last = deleteNode(last, 3);

    printf("List after deleting node 3: ");
    printList(last);

    return 0;
}

C++ Implementation

#include <iostream>
using namespace std;

// Define the structure of a node
struct Node {
    int data;         // Data stored in the node
    Node* next;       // Pointer to the next node in the circular linked list
};

// Function to delete a specific node by value
Node* deleteNode(Node* last, int value) {
    if (last == nullptr) { // Case 1: List is empty
        cout << "List is empty." << endl;
        return nullptr;
    }

    Node *curr = last->next, *prev = last;

    // Case 2: If the node to delete is the first node
    if (curr->data == value) {
        if (curr == last) { // Single node in the list
            delete curr;
            return nullptr;
        }
        last->next = curr->next; // Skip the head node
        delete curr;
        return last;
    }

    // Case 3: Traverse the list to find the node to delete
    do {
        if (curr->data == value) { // Node found
            prev->next = curr->next;
            if (curr == last) // Update last if last node is deleted
                last = prev;
            delete curr;
            return last;
        }
        prev = curr;
        curr = curr->next;
    } while (curr != last->next);

    cout << "Value " << value << " not found in the list." << endl;
    return last;
}

// Function to print the circular linked list
void printList(Node* last) {
    if (last == nullptr) {
        cout << "List is empty." << endl;
        return;
    }

    Node* temp = last->next;
    do {
        cout << temp->data << " ";
        temp = temp->next;
    } while (temp != last->next);
    cout << endl;
}

// Function to create a new node with the given value
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

int main() {
    Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    last = deleteNode(last, 3);

    cout << "List after deleting node 3: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;       // Data stored in the node
    public Node Next;      // Pointer to the next node in the circular linked list
}

class CircularLinkedList {
    public static Node DeleteNode(Node last, int value) {
        if (last == null) { // Case 1: List is empty
            Console.WriteLine("List is empty.");
            return null;
        }

        Node curr = last.Next, prev = last;

        // Case 2: If the node to delete is the first node
        if (curr.Data == value) {
            if (curr == last) { // Single node in the list
                return null;
            }
            last.Next = curr.Next; // Skip the head node
            return last;
        }

        // Case 3: Traverse the list to find the node to delete
        do {
            if (curr.Data == value) {
                prev.Next = curr.Next;
                if (curr == last) // Update last if last node is deleted
                    last = prev;
                return last;
            }
            prev = curr;
            curr = curr.Next;
        } while (curr != last.Next);

        Console.WriteLine($"Value {value} not found in the list.");
        return last;
    }

    public static void PrintList(Node last) {
        if (last == null) {
            Console.WriteLine("List is empty.");
            return;
        }

        Node temp = last.Next;
        do {
            Console.Write(temp.Data + " ");
            temp = temp.Next;
        } while (temp != last.Next);
        Console.WriteLine();
    }

    public static Node CreateNode(int value) {
        return new Node { Data = value, Next = null };
    }

    public static void Main() {
        Node first = CreateNode(2);
        first.Next = CreateNode(3);
        first.Next.Next = CreateNode(4);
        Node last = first.Next.Next;
        last.Next = first;

        Console.WriteLine("Original list: ");
        PrintList(last);

        last = DeleteNode(last, 3);

        Console.WriteLine("List after deleting node 3: ");
        PrintList(last);
    }
}

Java Implementation

class Node {
    int data;        // Data stored in the node
    Node next;       // Pointer to the next node in the circular linked list

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    // Function to delete a specific node by value
    public static Node deleteNode(Node last, int value) {
        if (last == null) { // Case 1: List is empty
            System.out.println("List is empty.");
            return null;
        }

        Node curr = last.next, prev = last;

        // Case 2: If the node to delete is the first node
        if (curr.data == value) {
            if (curr == last) { // Single node in the list
                return null;
            }
            last.next = curr.next; // Skip the head node
            return last;
        }

        // Case 3: Traverse the list to find the node to delete
        do {
            if (curr.data == value) {
                prev.next = curr.next;
                if (curr == last) // Update last if last node is deleted
                    last = prev;
                return last;
            }
            prev = curr;
            curr = curr.next;
        } while (curr != last.next);

        System.out.println("Value " + value + " not found in the list.");
        return last;
    }

    // Function to print the circular linked list
    public static void printList(Node last) {
        if (last == null) {
            System.out.println("List is empty.");
            return;
        }

        Node temp = last.next;
        do {
            System.out.print(temp.data + " ");
            temp = temp.next;
        } while (temp != last.next);
        System.out.println();
    }

    // Function to create a new node
    public static Node createNode(int value) {
        return new Node(value);
    }

    public static void main(String[] args) {
        // Step 1: Create nodes and form a circular linked list
        Node first = createNode(2);
        first.next = createNode(3);
        first.next.next = createNode(4);
        Node last = first.next.next;
        last.next = first; // Complete the circular link

        // Step 2: Print the original list
        System.out.println("Original list:");
        printList(last);

        // Step 3: Delete a node with value 3
        last = deleteNode(last, 3);

        // Step 4: Print the list after deletion
        System.out.println("List after deleting node 3:");
        printList(last);
    }
}

JavaScript Implementation

class Node {
    constructor(data) {
        this.data = data;    // Data stored in the node
        this.next = null;    // Pointer to the next node in the circular linked list
    }
}

class CircularLinkedList {
    static deleteNode(last, value) {
        if (!last) { // Case 1: List is empty
            console.log("List is empty.");
            return null;
        }

        let curr = last.next, prev = last;

        // Case 2: If the node to delete is the first node
        if (curr.data === value) {
            if (curr === last) { // Single node in the list
                return null;
            }
            last.next = curr.next; // Skip the head node
            return last;
        }

        // Case 3: Traverse the list to find the node to delete
        do {
            if (curr.data === value) {
                prev.next = curr.next;
                if (curr === last) // Update last if last node is deleted
                    last = prev;
                return last;
            }
            prev = curr;
            curr = curr.next;
        } while (curr !== last.next);

        console.log(`Value ${value} not found in the list.`);
        return last;
    }

    static printList(last) {
        if (!last) {
            console.log("List is empty.");
            return;
        }

        let temp = last.next;
        let result = "";
        do {
            result += temp.data + " ";
            temp = temp.next;
        } while (temp !== last.next);
        console.log(result.trim());
    }

    static createNode(value) {
        return new Node(value);
    }
}

// Main program
let first = CircularLinkedList.createNode(2);
first.next = CircularLinkedList.createNode(3);
first.next.next = CircularLinkedList.createNode(4);
let last = first.next.next;
last.next = first; // Complete the circular link

console.log("Original list:");
CircularLinkedList.printList(last);

last = CircularLinkedList.deleteNode(last, 3);

console.log("List after deleting node 3:");
CircularLinkedList.printList(last);

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data  # Data stored in the node
        self.next = None  # Pointer to the next node in the circular linked list

def delete_node(last, value):
    if not last:  # Case 1: List is empty
        print("List is empty.")
        return None

    curr = last.next
    prev = last

    # Case 2: If the node to delete is the first node
    if curr.data == value:
        if curr == last:  # Single node in the list
            return None
        last.next = curr.next  # Skip the head node
        return last

    # Case 3: Traverse the list to find the node to delete
    while curr != last.next:
        if curr.data == value:
            prev.next = curr.next
            if curr == last:  # Update last if last node is deleted
                last = prev
            return last
        prev = curr
        curr = curr.next

    print(f"Value {value} not found in the list.")
    return last

def print_list(last):
    if not last:
        print("List is empty.")
        return

    temp = last.next
    result = []
    while True:
        result.append(temp.data)
        temp = temp.next
        if temp == last.next:
            break
    print(" ".join(map(str, result)))

def create_node(value):
    return Node(value)

# Main program
first = create_node(2)
first.next = create_node(3)
first.next.next = create_node(4)
last = first.next.next
last.next = first  # Complete the circular link

print("Original list:")
print_list(last)

last = delete_node(last, 3)

print("List after deleting node 3:")
print_list(last)

Output

Original list:
2 3 4
List after deleting node 3:
2 4

Complexities

  • Time Complexity: O(n) (in the worst case, traverse the list to find the node).
  • Space Complexity: O(1) (no additional memory used).

3. Deletion at the End of a Circular Linked List

Deleting the last node in a circular linked list requires careful traversal to locate the second last node, as this node’s pointer must be updated to point back to the head. The challenge lies in ensuring the list remains circular even after the last node is removed.

Deletion at the end of Circular linked list

Step-by-Step Process for Deletion at the End

  • Check if the List is Empty
    • If last is nullptr, print “List is empty, nothing to delete” and return nullptr.
  • Get the Head Node
    • Retrieve the head node by setting head = last->next.
  • Check for a Single Node
    • If the head equals the last, it indicates the list contains only one node:
      • Delete the last node.
      • Set last = nullptr, as the list becomes empty.
  • Find the Second Last Node
    • Traverse the list starting from the head until reaching the node where curr->next equals last.
  • Update the Pointer of the Second Last Node
    • Set curr->next to point back to the head, effectively bypassing and removing the last node.
  • Delete the Last Node
    • Free up memory by deleting the last node and updating last to point to curr, the new last node.
  • Return the Updated last Pointer
    • Return the pointer to the last node, ensuring the list is circular.

Code Implementation In Multiple Programming Languages

C Programming

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the circular linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to delete the last node in the circular linked list
struct Node* deleteLastNode(struct Node* last) {
    if (last == NULL) {
        // If the list is empty, print a message and return NULL
        printf("List is empty, nothing to delete.\n");
        return NULL;
    }
    
    struct Node* head = last->next;

    // If there is only one node in the list
    if (head == last) {
        free(last);
        last = NULL;  // The list becomes empty
        return last;
    }
    
    // Traverse the list to find the second last node
    struct Node* curr = head;
    while (curr->next != last) {
        curr = curr->next;
    }
    
    // Update the second last node's next pointer to point to the head
    curr->next = head;
    
    // Free the memory occupied by the last node
    free(last);
    
    // Update the last pointer to point to the second last node
    last = curr;

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        // If the list is empty, return
        printf("List is Empty\n");
        return;
    }

    struct Node* head = last->next;
    do {
        printf("%d ", head->data);
        head = head->next;
    } while (head != last->next);
    printf("\n");
}

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // Create a circular linked list: 2 -> 3 -> 4 -> 2
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    
    struct Node* last = first->next->next;
    last->next = first;  // Circular link: last node points to first

    printf("Original list: ");
    printList(last);

    // Delete the last node
    last = deleteLastNode(last);

    printf("List after deleting last node: ");
    printList(last);

    return 0;
}

Explanation of the Code

  • Struct Definition:
    • The struct Node defines the structure of a node in the circular linked list, containing an integer data and a pointer next to the next node.
  • createNode Function:
    • This function takes an integer value as input, creates a new node, assigns the value to data, and sets the next pointer to NULL.
  • deleteLastNode Function:
    • This function is responsible for deleting the last node in the circular linked list:
      • It first checks if the list is empty (last == NULL). If empty, it prints a message and returns NULL.
      • If the list contains only one node (i.e., the head is the same as the last node), it frees the memory of that node and sets last to NULL, effectively making the list empty.
      • If there are multiple nodes, it traverses the list to find the second last node (i.e., the node whose next pointer points to the last node).
      • Once the second last node is found, its next pointer is updated to point back to the head, removing the last node from the circular list.
      • The last node is then deleted (free(last)), and the last pointer is updated to point to the second last node.
  • printList Function:
    • This function prints all the nodes in the circular linked list:
      • If the list is empty (last == NULL), it prints “List is Empty”.
      • It starts from the head (i.e., last->next) and prints the data of each node until it loops back to the head.
  • main Function:
    • This function demonstrates the creation of a circular linked list and performs the operation of deleting the last node:
      • It first creates a list with values 2 -> 3 -> 4 and links the last node back to the first node to form a circular list.
      • It prints the original list using printList.
      • It then deletes the last node using deleteLastNode and prints the updated list.

C++ Implementation

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

// Function to delete the last node
Node* deleteLastNode(Node* last) {
    if (!last) {
        cout << "List is empty, nothing to delete.\n";
        return nullptr;
    }

    Node* head = last->next;

    if (head == last) {
        delete last;
        return nullptr;
    }

    Node* curr = head;
    while (curr->next != last) {
        curr = curr->next;
    }

    curr->next = head;
    delete last;
    return curr;
}

// Function to print the circular linked list
void printList(Node* last) {
    if (!last) {
        cout << "List is empty.\n";
        return;
    }

    Node* head = last->next;
    do {
        cout << head->data << " ";
        head = head->next;
    } while (head != last->next);
    cout << endl;
}

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

int main() {
    Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    last = deleteLastNode(last);

    cout << "List after deleting last node: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;
    public Node Next;
}

class CircularLinkedList {
    public static Node DeleteLastNode(Node last) {
        if (last == null) {
            Console.WriteLine("List is empty, nothing to delete.");
            return null;
        }

        Node head = last.Next;

        if (head == last) {
            last = null;
            return null;
        }

        Node curr = head;
        while (curr.Next != last) {
            curr = curr.Next;
        }

        curr.Next = head;
        last = curr;
        return last;
    }

    public static void PrintList(Node last) {
        if (last == null) {
            Console.WriteLine("List is empty.");
            return;
        }

        Node head = last.Next;
        do {
            Console.Write(head.Data + " ");
            head = head.Next;
        } while (head != last.Next);
        Console.WriteLine();
    }

    public static Node CreateNode(int value) {
        return new Node { Data = value, Next = null };
    }

    public static void Main() {
        Node first = CreateNode(2);
        first.Next = CreateNode(3);
        first.Next.Next = CreateNode(4);

        Node last = first.Next.Next;
        last.Next = first;

        Console.WriteLine("Original list: ");
        PrintList(last);

        last = DeleteLastNode(last);

        Console.WriteLine("List after deleting last node: ");
        PrintList(last);
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    static Node deleteLastNode(Node last) {
        if (last == null) {
            System.out.println("List is empty, nothing to delete.");
            return null;
        }

        Node head = last.next;

        if (head == last) {
            return null;
        }

        Node curr = head;
        while (curr.next != last) {
            curr = curr.next;
        }

        curr.next = head;
        last = curr;

        return last;
    }

    static void printList(Node last) {
        if (last == null) {
            System.out.println("List is empty.");
            return;
        }

        Node head = last.next;
        do {
            System.out.print(head.data + " ");
            head = head.next;
        } while (head != last.next);
        System.out.println();
    }

    public static void main(String[] args) {
        Node first = new Node(2);
        first.next = new Node(3);
        first.next.next = new Node(4);

        Node last = first.next.next;
        last.next = first;

        System.out.println("Original list: ");
        printList(last);

        last = deleteLastNode(last);

        System.out.println("List after deleting last node: ");
        printList(last);
    }
}

JavaScript Implementation

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

function deleteLastNode(last) {
    if (!last) {
        console.log("List is empty, nothing to delete.");
        return null;
    }

    const head = last.next;

    if (head === last) {
        return null;
    }

    let curr = head;
    while (curr.next !== last) {
        curr = curr.next;
    }

    curr.next = head;
    return curr;
}

function printList(last) {
    if (!last) {
        console.log("List is empty.");
        return;
    }

    const head = last.next;
    let temp = head;
    do {
        process.stdout.write(temp.data + " ");
        temp = temp.next;
    } while (temp !== head);
    console.log();
}

function createNode(value) {
    return new Node(value);
}

// Main logic
const first = createNode(2);
first.next = createNode(3);
first.next.next = createNode(4);

let last = first.next.next;
last.next = first;

console.log("Original list:");
printList(last);

last = deleteLastNode(last);

console.log("List after deleting last node:");
printList(last);

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def delete_last_node(last):
    if not last:
        print("List is empty, nothing to delete.")
        return None

    head = last.next

    if head == last:
        return None

    curr = head
    while curr.next != last:
        curr = curr.next

    curr.next = head
    return curr

def print_list(last):
    if not last:
        print("List is empty.")
        return

    head = last.next
    temp = head
    while True:
        print(temp.data, end=" ")
        temp = temp.next
        if temp == head:
            break
    print()

# Main logic
first = Node(2)
first.next = Node(3)
first.next.next = Node(4)

last = first.next.next
last.next = first

print("Original list:")
print_list(last)

last = delete_last_node(last)

print("List after deleting last node:")
print_list(last)

Output

Original list: 2 3 4
List after deleting last node: 2 3

Complexities

  • Time Complexity: O(1)
  • Auxiliary Space: O(1)

Applications of Deletion from a Circular Linked List

  • Task Scheduling Systems
    • In multitasking operating systems, tasks are often organized in a circular fashion, where each task is given a specific time slice for execution.
    • A circular linked list is ideal for managing these tasks because:
      • Tasks can be easily added or removed as needed.
      • Deleting a completed or faulty task involves updating pointers, ensuring seamless execution.
      • The circular structure ensures the scheduler loops back to the first task when it reaches the end.
  • Real-Time Applications
    • In systems requiring continuous monitoring or updates, such as traffic signal control or sensor networks, deletion operations in circular linked lists help:
      • Remove outdated or irrelevant data points.
      • Ensure efficient memory usage by maintaining only the latest relevant information.
      • Handle dynamic node removal without disrupting the loop.
  • Multiplayer Gaming
    • In multiplayer games, players can be organized in a circular list where each node represents a player. Deletion from the list is used when:
      • A player leaves the game.
      • A player is disqualified or eliminated. This operation ensures that the remaining players are still connected in the loop, facilitating fair gameplay.
  • Buffer Management
    • Circular linked lists are often used in buffers, such as:
      • Data stream buffering: Deleting old or consumed data allows continuous data flow.
      • Circular queues for resource allocation: Resources can be reclaimed dynamically by removing unused or expired nodes.
  • Polled Event Systems
    • In applications like printer spooling or network packet processing, circular linked lists manage a queue of tasks or events. Deletion operations help:
      • Remove completed tasks/events efficiently.
      • Dynamically adjust the queue size based on the system’s current needs.
  • Memory Management in Embedded Systems
    • Embedded systems, such as IoT devices, often use circular linked lists to manage memory allocations. Deletion operations:
      • Free unused memory blocks.
      • Ensure optimal memory usage in resource-constrained environments.

Advantages of Deletion from a Circular Linked List

  • Efficient Traversal and Deletion
    • The circular structure allows continuous traversal without reaching the end of the list, which is particularly useful for deletion operations. For example:
      • After deleting a node, traversal continues seamlessly to the next node.
      • There is no need for special handling of the end of the list.
  • Dynamic Size Management
    • Unlike arrays, circular linked lists allow nodes to be added or deleted dynamically, making them highly flexible:
      • Nodes can be removed without resizing or shifting elements.
      • Deletion operations are efficient, requiring only pointer updates rather than extensive memory operations.
  • Memory Efficiency
    • Nodes can be deleted to free up memory dynamically. This is particularly beneficial for:
      • Applications running on memory-constrained systems.
      • Systems requiring periodic cleanup of unused or outdated nodes.
  • Simplified Circular Logic
    • Deleting nodes in a circular linked list does not disrupt the loop, as the list inherently connects the last node to the first:
      • Even after deleting the first or last node, the circular nature is preserved by updating pointers.
      • This ensures continuity and avoids breaking the sequence of elements.
  • Fast Deletion of First and Last Nodes
    • Circular linked lists make deletion of the first and last nodes faster compared to singly or doubly linked lists:
      • The first node is directly accessible via the last->next pointer.
      • The last node can be managed by traversing to the second-last node and updating its pointer.
  • Useful in Round-Robin Algorithms
    • In applications like CPU scheduling, the deletion of nodes representing completed tasks is straightforward. This advantage ensures:
      • Smooth task rotation.
      • Proper cleanup of finished tasks without affecting the ongoing round-robin cycle.
  • Adaptive to Real-Time Changes
    • Circular linked lists adapt well to dynamic scenarios where nodes may need to be frequently added or removed:
      • Deletion operations ensure that the list reflects the current state of the system or data.
      • This adaptability makes them suitable for real-time systems.
  • Fault Tolerance
    • In systems where redundancy or fault tolerance is essential (e.g., network systems or distributed computing), circular linked lists allow nodes to be deleted without disrupting the loop:
      • Faulty or disconnected nodes can be removed, and the remaining nodes remain operational.
      • The circular structure helps maintain system integrity.

Why Circular Linked Lists Stand Out for Deletion Operations

While other data structures like arrays or doubly linked lists can also perform deletions, circular linked lists provide unique benefits:

  • Continuous Loop: Ensures the structure remains intact after deletion.
  • Pointer Efficiency: Requires only pointer updates for node removal, making it computationally efficient.
  • Dynamic Nature: Handles real-time additions and deletions with ease, unlike arrays that require resizing.

Key Takeaways

Understanding deletion operations in a circular linked list is crucial for mastering this data structure. By carefully managing pointers and ensuring the circular nature of the list, you can efficiently handle deletions at the beginning, a specific position, or the end. These methods showcase the elegance and utility of circular linked lists in various applications, from task scheduling to memory management.

Differences Between Insertion and Deletion Operations in a Circular Linked List

Here’s a detailed table highlighting the key differences between Insertion and Deletion operations in a Circular Linked List:

AspectInsertion in Circular Linked ListDeletion in Circular Linked List
ObjectiveTo add a new node to the circular linked list.To remove an existing node from the circular linked list.
Types of Operations– Insertion at the beginning- Insertion at a specific position- Insertion at the end– Deletion at the beginning- Deletion at a specific position- Deletion at the end
Impact on List SizeIncreases the number of nodes in the list.Decreases the number of nodes in the list.
Pointer AdjustmentsUpdates the next pointer of one or more nodes to link the new node into the list.Updates the next pointer of surrounding nodes to bypass the deleted node.
Circular Property HandlingEnsures the last node’s next pointer correctly points to the new head after insertion.Ensures the last node’s next pointer maintains the circular link after deletion.
ComplexityInsertion at the Beginning: O(1)Insertion at the End: O(n)Specific Position: O(n)Deletion at the Beginning: O(1)Deletion at the End: O(n)Specific Position: O(n)
Memory RequirementsRequires memory allocation for the new node.Frees up memory occupied by the deleted node.
Empty List Handling– Directly adds the new node.- Initializes last to point to the new node, creating a circular link.– Prints a message like “List is empty” if last is nullptr.- No deletion is performed.
Handling Single Node– Inserts the new node and updates last->next to maintain the circular link.– Deletes the single node and sets last = nullptr, leaving the list empty.
Traversal RequirementsTraversal is needed for insertion at a specific position or at the end.Traversal is needed for deletion at a specific position or to find the second last node.
Head Node OperationsFor insertion at the beginning:- New node becomes the head.- last->next updated accordingly.For deletion at the beginning:- The node after the head becomes the new head.- last->next updated.
End Node OperationsFor insertion at the end:- New node becomes the last node.- Updates its next to point to the head.For deletion at the end:- Updates the second last node to point to the head.- Frees the last node and updates last.
Error HandlingRarely encounters errors (e.g., invalid position for insertion).May encounter errors like attempting to delete a node from an empty list or an invalid position.
Resulting List StateThe circular property is preserved with an additional node.The circular property is preserved with one less node.

This table provides a clear comparison of Insertion and Deletion in terms of their purpose, steps, and outcomes within a Circular Linked List.

  1. Introduction to Circular Linked Lists: A Comprehensive Guide
  2. Understanding Circular Singly Linked Lists: A Comprehensive Guide
  3. Circular Doubly Linked List: A Comprehensive Guide
  4. Insertion in Circular Singly Linked List: A Comprehensive Guide
  5. Insertion in an Empty Circular Linked List: A Detailed Exploration
  6. Insertion at the Beginning in Circular Linked List: A Detailed Exploration
  7. Insertion at the End of a Circular Linked List: A Comprehensive Guide
  8. Insertion at a Specific Position in a Circular Linked List: A Detailed Exploration
  9. Deletion from a Circular Linked List: A Comprehensive Guide
  10. Deletion from the Beginning of a Circular Linked List: A Detailed Exploration
  11. Deletion at Specific Position in Circular Linked List: A Detailed Exploration
  12. Deletion at the End of a Circular Linked List: A Comprehensive Guide
  13. Searching in a Circular Linked List: A Comprehensive Exploration

Frequently Asked Questions (FAQs) on Deletion from a Circular Linked List

What is a Circular Linked List, and why is deletion in it unique?

A circular linked list is a data structure where the last node is connected to the first node, forming a continuous loop. This unique structure allows traversal of the entire list starting from any node without encountering a null pointer.

Deletion in a circular linked list is unique because:

  • The circular nature must be preserved after removing a node.
  • Unlike a singly or doubly linked list, the last node’s next pointer plays a crucial role in maintaining the circular connection.
  • Edge cases such as deleting the first node, the last node, or the only node in the list require careful pointer management.

What are the different types of deletion operations in a Circular Linked List?

Deletion in a circular linked list can be categorized into three types:

  • Deletion at the Beginning:
    • Removes the first node.
    • Updates the last->next pointer to skip the deleted node and point to the new head.
  • Deletion at a Specific Position:
    • Removes a node at a given position or with a specific key.
    • Adjusts the surrounding nodes’ pointers to maintain the circular connection.
  • Deletion at the End:
    • Removes the last node.
    • Updates the second last node’s next pointer to point back to the head.

Each type requires a tailored approach to ensure the circular property is preserved.

How do you handle deletion when the Circular Linked List is empty?

When the circular linked list is empty (i.e., last == nullptr):

  • Deletion cannot be performed because there are no nodes in the list.
  • In this case, it is common to print an error message such as “List is empty, nothing to delete”.
  • The function should return nullptr to indicate that no changes were made to the list.

What happens if you delete the only node in a Circular Linked List?

If the circular linked list contains only one node:

  • The last pointer points to the only node, and last->next points back to itself.
  • Deleting this node involves:
    • Freeing the memory allocated for the node.
    • Setting last = nullptr, indicating that the list is now empty.
  • After this operation, both the circular nature and the node itself are removed.

How is deletion at the beginning of a Circular Linked List performed?

Deletion at the beginning removes the head node and updates the circular structure. Here’s the step-by-step process:

  • Check if the List is Empty:
    • If last == nullptr, print an error message and return nullptr.
  • Handle Single Node:
    • If the list contains only one node (last == last->next), delete the node and set last = nullptr.
  • Handle Multiple Nodes:
    • Set head = last->next to identify the first node.
    • Update last->next to point to head->next, bypassing the deleted node.
    • Free the memory allocated for the head.

This ensures the circular property is preserved.

How is deletion at a specific position handled in a Circular Linked List?

Deletion at a specific position involves removing the node at a given index or with a specific key. Here’s how it works:

  • Empty List Check:
    • If last == nullptr, print “List is empty, nothing to delete”.
  • Single Node Check:
    • If the list contains only one node and it matches the key, delete it and set last = nullptr.
  • Deleting the Head:
    • If the node to be deleted is the head (last->next), update last->next to skip the head and delete the head node.
  • Traversing the List:
    • Use two pointers, curr (current node) and prev (previous node), to find the target node.
    • Update prev->next to bypass curr, then delete curr.
  • Adjusting the Last Node:
    • If the deleted node is the last node, update last = prev.
  • Node Not Found:
    • If no matching node is found, print a message such as “Node with data [key] not found.”

How is deletion at the end of a Circular Linked List performed?

Deletion at the end involves removing the last node. Here’s the procedure:

  • Empty List Check:
    • If last == nullptr, print “List is empty, nothing to delete”.
  • Single Node Check:
    • If the list contains only one node, delete it and set last = nullptr.
  • Find the Second Last Node:
    • Start from the head and traverse the list until reaching the node where curr->next == last.
  • Update the Pointer:
    • Set curr->next to point to the head (last->next).
  • Delete the Last Node:
    • Free the memory for the last node and update last = curr.

This ensures the second last node becomes the new last node.

What are the common edge cases when performing deletion operations?

Deletion operations in a circular linked list may encounter several edge cases:

  • Empty List:
    • Deletion attempts on an empty list should print an error message and return without changes.
  • Single Node List:
    • When deleting the only node, ensure the list is marked empty by setting last = nullptr.
  • Invalid Position or Key:
    • If the specified position or key does not exist, print an appropriate message.
  • Circular Property Maintenance:
    • Ensure the last->next pointer remains valid after deletion.
  • Multiple Nodes with the Same Key:
    • Handle cases where multiple nodes have the same data if required by the application.

Why is deletion more complex in a Circular Linked List compared to other linked lists?

Deletion in a circular linked list is more complex due to its cyclic nature:

  • Pointer Maintenance:
    • The last node’s next pointer must always point to the new head.
    • Special care is needed when deleting the first or last node.
  • Traversal Challenges:
    • The traversal involves a loop back to the starting point, which complicates operations.
  • Edge Cases:
    • Deleting the only node or handling empty lists adds complexity.
  • Preserving Circularity:
    • Ensuring the list remains circular after deletion requires meticulous pointer adjustments.

What are the practical applications of deletion in Circular Linked Lists?

Deletion operations in circular linked lists are vital for various real-world applications:

  • Task Scheduling:
    • Remove completed or faulty tasks in round-robin schedulers.
  • Gaming:
    • Handle player elimination or disqualification in multiplayer games.
  • Buffer Management:
    • Remove consumed or outdated data in circular buffers.
  • Real-Time Systems:
    • Delete irrelevant data points in sensor networks or traffic systems.
  • Memory Management:
    • Reclaim memory by removing unused or expired blocks in embedded systems.

These applications rely on efficient deletion operations to maintain the functionality and performance of the system.

Share.
Examsmeta Logo

Examsmeta serves as a comprehensive hub for educational resources across diverse disciplines. Designed to deliver high-quality, topic-wise notes and articles, it caters to students, educators, and lifelong learners. The goal is to make learning accessible, engaging, and effective for all. With a focus on providing detailed, accurate, and up-to-date content, Examsmeta fosters a passion for learning and supports both academic and professional growth. Whether it's exam preparation, research, or knowledge expansion, this platform offers guidance every step of the way.