Delete a Node from Circular Linked List in DSA Java - Time & Space Complexity

Time Complexity: Delete a Node from Circular Linked List

O(n)

Understanding Time Complexity

When deleting a node from a circular linked list, we want to know how the time needed changes as the list grows.

We ask: How many steps does it take to find and remove the node?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Delete node with given key from circular linked list
Node deleteNode(Node head, int key) {
    if (head == null) return null;
    Node curr = head, prev = null;
    do {
        if (curr.data == key) {
            if (prev != null) prev.next = curr.next;
            else {
                // If only one node in the list
                if (curr.next == head) {
                    return null;
                }
                head = curr.next;
            }
            break;
        }
        prev = curr;
        curr = curr.next;
    } while (curr != head);
    return head;
}
    

This code searches the circular linked list for a node with the given key and removes it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through nodes to find the target node.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the number of nodes to check grows too.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The steps grow roughly in direct proportion to the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting a node in a circular linked list always takes constant time because we just change pointers."

[OK] Correct: You must first find the node, which can take time proportional to the list size, so it is not always constant time.

Interview Connect

Understanding this helps you explain how linked lists work and how searching affects performance, a key skill in many coding challenges.

Self-Check

"What if the list was doubly linked? How would the time complexity change when deleting a node?"

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