Delete a Node from Circular Linked List in DSA Java

Mental Model

A circular linked list loops back to the start, so deleting a node means adjusting links without breaking the circle.

Analogy: Imagine people sitting in a circle holding hands. Removing one person means the two neighbors hold hands directly, keeping the circle unbroken.

1 -> 2 -> 3 -> 4 -> (back to 1)
↑head

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 (circular), delete node with value 3

Goal: Remove node 3 and keep the list circular without breaking links

Step 1: start at head (1), look for node with value 3

1 -> [curr->2] -> 3 -> 4 -> (back to 1)
↑head

Why: We need to find the node before the one to delete to change its next pointer

Step 2: move curr to node 2, check next node value (3)

1 -> 2 -> [curr->3] -> 4 -> (back to 1)
↑head

Why: Found node before target (2), ready to remove node 3

Step 3: change curr.next from 3 to 4, skipping node 3

1 -> 2 -> 4 -> (back to 1)
↑head

Why: By skipping node 3, we remove it and keep the circle intact

Result:

1 -> 2 -> 4 -> (back to 1)
↑head

Annotated Code

DSA Java

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

public class CircularLinkedList {
    Node head;

    // Delete node with given key
    public void deleteNode(int key) {
        if (head == null) return; // empty list

        // If head is to be deleted and only one node
        if (head.data == key && head.next == head) {
            head = null;
            return;
        }

        Node curr = head;
        Node prev = null;

        // If head needs to be deleted and list has multiple nodes
        if (head.data == key) {
            // Find last node to update its next pointer
            while (curr.next != head) {
                curr = curr.next; // advance to last node
            }
            curr.next = head.next; // last node points to second node
            head = head.next; // update head
            return;
        }

        // Search for node to delete
        prev = head;
        curr = head.next;
        while (curr != head && curr.data != key) {
            prev = curr; // move prev forward
            curr = curr.next; // move curr forward
        }

        // If node found, remove it
        if (curr != head && curr.data == key) {
            prev.next = curr.next; // skip curr node
        }
    }

    // Print circular list
    public void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(back to " + head.data + ")");
    }

    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        Node fourth = new Node(4);

        cll.head.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = cll.head; // circular link

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

        cll.deleteNode(3);
        System.out.println("After deleting 3:");
        cll.printList();
    }
}

if (head == null) return;

handle empty list edge case

if (head.data == key && head.next == head) { head = null; return; }

delete only node in list

if (head.data == key) { while (curr.next != head) { curr = curr.next; } curr.next = head.next; head = head.next; return; }

delete head node by updating last node's next and head pointer

while (curr != head && curr.data != key) { prev = curr; curr = curr.next; }

search for node to delete

if (curr != head && curr.data == key) { prev.next = curr.next; }

remove node by skipping it in the list

Output

Original list:

1 -> 2 -> 3 -> 4 -> (back to 1)

After deleting 3:

1 -> 2 -> 4 -> (back to 1)

Complexity Analysis

Time: O(n) because in worst case we traverse all nodes once to find the node to delete

Space: O(1) because we use only a few pointers regardless of list size

vs Alternative: Compared to singly linked list deletion, circular list requires careful handling of the last node to maintain the circle, but time complexity remains similar

Edge Cases

empty list

function returns immediately without changes

DSA Java

if (head == null) return;

list with one node which is to be deleted

head becomes null, list becomes empty

DSA Java

if (head.data == key && head.next == head) { head = null; return; }

deleting the head node in a list with multiple nodes

last node's next pointer updated to new head, head pointer updated

DSA Java

if (head.data == key) { while (curr.next != head) { curr = curr.next; } curr.next = head.next; head = head.next; return; }

deleting a node not present in the list

list remains unchanged

DSA Java

while (curr != head && curr.data != key) { prev = curr; curr = curr.next; }

When to Use This Pattern

When you see a problem asking to remove an element from a circular linked list, use pointer updates carefully to maintain the loop without breaking the circle.

Common Mistakes

Mistake: Not updating the last node's next pointer when deleting the head node
Fix: Traverse to the last node and update its next pointer to the new head before deleting

Mistake: Assuming the list is linear and forgetting the circular condition in loops
Fix: Use conditions that check for returning to head to avoid infinite loops

Summary

Deletes a node from a circular linked list by adjusting pointers to keep the circle intact.

Use when you need to remove elements from a circular linked list without breaking its circular nature.

The key is to update the previous node's next pointer and handle the special case when deleting the head.

Practice

1. What happens when you delete the only node in a circular linked list?

easy

A. The list becomes empty (head points to null)

B. The list still contains the deleted node

C. The list forms a linear linked list

D. The list throws an error automatically

Solution

1. Step 1: Understand single node deletion

   When the only node is deleted, no nodes remain in the list.

2. Step 2: Resulting list state

   The head pointer is set to null, indicating an empty list.

3. Final Answer:

   The list becomes empty (head points to null) -> Option A

4. Quick Check:

   Deleting last node empties list [OK]

Hint: Deleting last node empties list, head = null [OK]

Common Mistakes:

• Assuming list still has nodes after deletion
• Not setting head to null
• Confusing circular with linear list after deletion

2. Which of the following is the correct way to update the head when deleting the head node in a circular linked list?

easy

A. head = tail; tail.next = null;

B. head = null; tail = null;

C. head = head.prev; tail.next = head;

D. head = head.next; tail.next = head;

Solution

1. Step 1: Update head pointer

   When deleting the head node, move head to next node.

2. Step 2: Maintain circular link

   Update tail's next pointer to new head to keep circular structure.

3. Final Answer:

   head = head.next; tail.next = head; -> Option D

4. Quick Check:

   Head moves forward, tail links to new head [OK]

Hint: After deleting head, point tail.next to new head [OK]

Common Mistakes:

• Setting tail.next to null breaks circular link
• Setting head to null incorrectly
• Using head.prev which doesn't exist in singly circular list

3. What will be the output after deleting node with value 3 from this circular linked list: 1 -> 2 -> 3 -> 4 -> (back to 1)?

Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
head.next = n2; n2.next = n3; n3.next = n4; n4.next = head;
// Delete node with value 3
// After deletion, print list starting from head

medium

A. 1 -> 2 -> 4 -> (back to 1)

B. 1 -> 2 -> 3 -> 4 -> (back to 1)

C. 1 -> 4 -> (back to 1)

D. 2 -> 4 -> (back to 2)

Solution

1. Step 1: Locate node with value 3

   Traverse list: 1 -> 2 -> 3 found.

2. Step 2: Remove node 3 by linking 2 to 4

   Set n2.next = n3.next (which is n4), skipping node 3.

3. Final Answer:

   1 -> 2 -> 4 -> (back to 1) -> Option A

4. Quick Check:

   Node 3 removed, list links 2 to 4 [OK]

Hint: Skip node by linking previous to next [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Breaking circular link by missing tail update
• Deleting wrong node or skipping nodes

4. Identify the error in this code snippet that deletes a node with value 'key' from a circular linked list:

Node current = head;
while(current.next != head && current.next.data != key) {
    current = current.next;
}
if(current.next.data == key) {
    current.next = current.next.next;
}

medium

A. Does not handle deletion when list has only one node

B. Infinite loop if key not found

C. Does not update tail pointer when deleting last node

D. Deletes head node incorrectly

Solution

1. Step 1: Check tail update on deletion

   If deleted node is tail, tail pointer must update to current node.

2. Step 2: Code misses tail update

   Code only changes current.next, tail remains pointing to deleted node.

3. Final Answer:

   Does not update tail pointer when deleting last node -> Option C

4. Quick Check:

   Tail pointer must update if last node deleted [OK]

Hint: Update tail if deleting last node [OK]

Common Mistakes:

• Ignoring tail pointer update
• Assuming tail auto-updates
• Not checking if deleted node is tail

5. Given a circular linked list with nodes 10 -> 20 -> 30 -> 40 -> (back to 10), how would you delete the node with value 10 (head node) and maintain the circular structure? Choose the correct sequence of operations.

hard

A. Set head = null; tail = null;

B. Set head = head.next; tail.next = head; delete old head;

C. Set tail.next = head.next; head = head.next;

D. Set tail = head; head = head.next; tail.next = null;

Solution

1. Step 1: Move head to next node

   Set head = head.next to remove old head from start.

2. Step 2: Update tail's next pointer

   Set tail.next = head to maintain circular link.

3. Step 3: Delete old head node properly

   Remove old head node from memory if needed.

4. Final Answer:

   Set head = head.next; tail.next = head; delete old head; -> Option B

5. Quick Check:

   Head moves forward, tail links to new head [OK]

Hint: Update head and tail.next to new head when deleting head [OK]

Common Mistakes:

• Breaking circular link by setting tail.next to null
• Not moving head pointer
• Deleting head without updating tail.next