Delete a Node from Circular Linked List in DSA Java - Execution Trace

Concept Flow - Delete a Node from Circular Linked List

Start at head

↓

Check if list empty?

Yes→Stop: Nothing to delete

No↓

Find node to delete

↓

Node found?

No→Stop: Node not found

Yes↓

If node is head

↓

Find last node to update its next

↓

Update pointers to remove node

↓

Delete node and fix circular links

↓

Done

The flow starts at the head, checks if the list is empty, searches for the node to delete, updates pointers to remove it, and maintains the circular link.

Execution Sample

DSA Java

class Node {
  int data;
  Node next;
}

// Delete node with value 3 from circular list

Node class definition for circular linked list deletion example.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1->2->3->4->1	head points to 1	1 -> 2 -> 3 -> 4 -> (back to 1)
2	Check if list empty	1->2->3->4->1	No change	1 -> 2 -> 3 -> 4 -> (back to 1)
3	Find node with data=3	1->2->3->4->1	Traverse: current=1->2->3	1 -> 2 -> 3 -> 4 -> (back to 1)
4	Node found (3)	1->2->3->4->1	prev=2, current=3	1 -> 2 -> 3 -> 4 -> (back to 1)
5	Node is not head	1->2->4->1	prev.next = current.next (2.next=4)	1 -> 2 -> 4 -> (back to 1)
6	Delete node 3	1->2->4->1	current removed	1 -> 2 -> 4 -> (back to 1)
7	Done	1->2->4->1	No change	1 -> 2 -> 4 -> (back to 1)

💡 Node with data=3 deleted, circular links maintained

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
head	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)
current	Node(1)	Node(3)	Node(3)	Node(3)	null (deleted)
prev	null	Node(2)	Node(2)	Node(2)	Node(2)
list size	4	4	4	3	3

Key Moments - 3 Insights

Why do we need to find the previous node before deleting the current node?

Because in a singly linked circular list, to remove a node, we must update the previous node's next pointer to skip the current node. See step 5 in execution_table where prev.next is updated.

What happens if the node to delete is the head?

We must find the last node to update its next pointer to the new head. This keeps the circular link intact. This is shown in the concept_flow but not in this example since the deleted node is not head.

Why does the list remain circular after deletion?

Because we update the previous node's next pointer to point to the node after the deleted node, maintaining the loop. See step 5 and 6 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of 'current'?

A Node with data 3

B Node with data 2

C Node with data 4

D null

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table

At which step does the list size decrease?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at variable_tracker row for 'list size' after each step

If the node to delete was the head, what extra step is needed?

A No extra step needed

B Find last node to update its next pointer

C Delete all nodes

D Change head to null

💡 Hint

Refer to concept_flow where deleting head requires finding last node

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check empty
- Traverse to find node and previous
- If node found:
  - If head, update last node's next
  - Else, prev.next = node.next
- Remove node, maintain circular link
- List size decreases by one

Full Transcript

To delete a node from a circular linked list, start at the head and check if the list is empty. Then traverse the list to find the node to delete and keep track of the previous node. If the node is found and it is not the head, update the previous node's next pointer to skip the node to delete. If the node is the head, find the last node and update its next pointer to the new head. This maintains the circular structure. Finally, remove the node and decrease the list size. The execution table shows each step with pointer changes and the list's visual state. Key moments clarify why the previous node is needed and how the circular link is preserved.

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