Deletion in Circular Linked List

Java Program to Delete a Node of a Circular Linked List

In this Deletion in Circular Linked List in Java Programming article, we will explore deletion operations in a circular singly linked list (CSLL) using Java. We’ll examine all possible deletion scenarios, analyze time and space complexity, provide complete code examples, and highlight important and interesting facts about circular linked lists.

Circular linked list is a variation of the linked list in which the last node points back to the head instead of null. This circular nature offers certain advantages, especially in applications where continuous traversal is desired, such as in scheduling algorithms, real time applications, and buffering data structures.

Deletion in Circular Linked List In Java

Types of Deletion in Circular Linked List

In a circular linked list, deletion can be categorized into the following types:

  1. Deletion at the Beginning (Head Node)
  2. Deletion at the End (Tail Node)
  3. Deletion at a Given Position (Index-based)

Structure of a Circular Linked List

Each node in a singly circular linked list has:

  • data: the value it stores

  • next: a reference to the next node

In the last node, instead of next = null (as in a regular singly linked list), we set next = head, completing the circle.

1. Deletion from beginning of a circular linked list

  • The first node (head) is removed.
  • We need to update the last node’s next pointer to the new head.
  • Special case: Only one node? Just set head = null.

Use Cases:

  1. Removing the oldest or highest priority element.
  2. Rotating buffers or schedules.

Algorithm:

  • deleteFirst()
  • IF head == null
    • return
  • ELSE IF head != tail
    • head = head -> next
    • tail -> next = head
  • ELSE
    • head = tail = null
Deletion in circular Linked List from Beginning

Code Snippet:

public void deleteFirst() {  
        if(head == null) {  
            return;  
        }  
        else {  
            if(head != tail ) {  
                head = head.next;  
                tail.next = head;  
            }  
            else {  
                head = tail = null;  
            }  
        }  
    }  

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

2. Deletion from last of a circular linked list

  • Traverse the list to find the second last node.
  • Change its next to point to the head.
  • Special case: If there’s only one node, list becomes empty.

Use Cases:

Useful when removing the most recent entry in circular stacks or logs.

Algorithm:

  • deleteLast()
  • IF head == null
    • return
  • ELSE IF head != tail
    • Node current = head
    • WHILE current->next != tail
      • current = current-> next
      • tail = current;
      • tail -> next = head
  • ELSE
    • head = tail = null
Deletion from last in Singly Linked List

Code Snippet:

public void deleteLast() {
        if(head == null) {
            return;
        }
        else {
            if(head != tail ) {
                Node current = head;
                while(current.next != tail) {
                    current = current.next;
                }
                tail = current;
                tail.next = head;
            }
            else {
                head = tail = null;
            }
        }
    }

3. Deletion at a Given Position of a circular linked list

  • Locate the node just before the target position.
  • Adjust the pointer to skip the target node.
  • Validate index boundaries.

Use Cases:

Random access deletion in non-linear data flows.

Optimized deletion in network packet queues.

Algorithm:

  • deleteLast()
  • IF head == null
    • return
  • ELSE
    • WHILE (–n>0)
      • previous = temp;
      • temp = temp.next;
    • previous.next = temp.next;
Deletion in circular Linked List from Nth node

Code Snippet:

public void deleteAtPosition(int position) {
    if (head == null) {
        return;
    }

    if (position == 1) {
        deleteFirst();
        return;
    }

    Node current = head;
    Node previous = null;
    int count = 1;

    while (count < position && current.next != head) {
        previous = current;
        current = current.next;
        count++;
    }

    if (count != position) {
        return;
    }

    if (current == tail) {
        deleteLast();
        return;
    }

    previous.next = current.next;
    current.next = null;
}

Code for deletion of a node in circular Linked List in Java

Code 1: Singly Circular Linked List

Method Types:

  1. deleteFirst()
    Type: Deletion at the beginning (head)
    List Type: Singly Circular Linked List
  2. deleteLast()
    Type: Deletion at the end (tail)
    List Type: Singly Circular Linked List
  3. deleteNthNode(int n)
    Type: Deletion at a specific position (Nth node)
    List Type: Singly Circular Linked List

Code 2: Doubly Circular Linked List

Method Types:

  1. deleteFirst()
    Type: Deletion at the beginning (head)
    List Type: Doubly Circular Linked List
    (Although it doesn’t update head.prev explicitly, the structure supports doubly linked list behavior.)
  2. deleteLast()
    Type: Deletion at the end (tail)
    List Type: Doubly Circular Linked List
    (Includes head.prev = tail to maintain backward linkage.)
  3. deletenth(int n)
    Type: Deletion at a specific position (Nth node)
    List Type: Doubly Circular Linked List
    (Uses both prev and next pointers to unlink the node.)

Learn DSA

FAQ's Related to Circular Linked List

Answer:

  1. Circular linked list is a variation of a linked list in which the last node points back to the first node, forming a loop.
  2. It can be singly (only next pointers) or doubly (with both next and prev pointers).

Answer:

In a circular linked list, special care must be taken to maintain the circular reference (i.e., last node’s next should point to the head). In deletion, we must update links carefully to keep the circular structure intact.

Answer:

  • Singly Circular: Move head to head.next and update tail.next = head.

  • Doubly Circular: Move head to head.next, update tail.next = head, and head.prev = tail.

Answer:

  1. Singly Circular: Traverse until the second-last node, make it the new tail, and set tail.next = head.
  2. Doubly Circular: Set tail = tail.prev, and update tail.next = head, head.prev = tail.

Answer:

Traverse to the required position and unlink the node by updating the next (and prev if doubly circular) pointers of the surrounding nodes.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription