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

Concept Flow - Delete a Node from Circular Linked List

Start at head

↓

Check if list empty?

Yes→Stop: Nothing to delete

No↓

Traverse nodes to find target

↓

Found node to delete?

No→Stop: Node not found

Yes↓

If node is head

↓

Adjust head and last node's next

↓

Else

↓

Adjust previous node's next

↓

Delete node

↓

Done

Start from head, check if list is empty, traverse to find node, adjust pointers depending on node position, then delete node.

Execution Sample

DSA Python

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

def delete_node(head, key):
    # Deletes node with value key from circular linked list
    pass

Deletes a node with given value from a circular linked list, adjusting pointers to maintain circularity.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1 -> 2 -> 3 -> 4 -> (back to 1)	head points to node 1	1 -> 2 -> 3 -> 4 -> (head)
2	Check if list empty	1 -> 2 -> 3 -> 4 -> (back to 1)	No change	1 -> 2 -> 3 -> 4 -> (head)
3	Traverse to find node with data=3	1 -> 2 -> 3 -> 4 -> (back to 1)	current moves: 1->2->3	1 -> 2 -> [3] -> 4 -> (head)
4	Found node to delete (3)	1 -> 2 -> 3 -> 4 -> (back to 1)	prev.next updated from 3 to 4	1 -> 2 -> 4 -> (head)
5	Delete node 3	1 -> 2 -> 4 -> (back to 1)	Node 3 removed	1 -> 2 -> 4 -> (head)
6	End	1 -> 2 -> 4 -> (back to 1)	No change	1 -> 2 -> 4 -> (head)

💡 Node with data=3 deleted, pointers adjusted to maintain circular list

Variable Tracker

Variable	Start	After Step 3	After Step 4	Final
head	Node 1	Node 1	Node 1	Node 1
current	Node 1	Node 3	Node 3	Node 1
prev	None	Node 2	Node 2	Node 2
list size	4	4	3	3

Key Moments - 3 Insights

Why do we need to track the previous node (prev) when deleting?

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

What happens if the node to delete is the head?

We must update the head pointer and also the last node's next pointer to the new head to keep the list circular. This is a special case not shown in this example but important to handle.

Why does traversal stop when current.data == key?

Because we found the node to delete. Continuing would risk infinite loop in circular list. See execution_table step 3 and 4.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'current' after step 3?

A Node 2

B Node 4

C Node 3

D Node 1

💡 Hint

Check the 'current' variable in variable_tracker after step 3.

At which step is the node with data=3 removed from the list?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table.

If the node to delete was the head, what pointer must be updated besides 'prev.next'?

A Only the head pointer

B The head pointer and last node's next pointer

C Only the last node's next pointer

D No pointers need updating

💡 Hint

Refer to key_moments about deleting the head node.

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check if list empty
- Traverse to find node with target data
- Keep track of previous node
- If node found:
  - If head, update head and last node's next
  - Else, update prev.next to skip node
- Delete node and maintain circular link

Full Transcript

To delete a node from a circular linked list, start at the head and check if the list is empty. If not, traverse the list to find the node with the target value, keeping track of the previous node. When found, if the node is the head, update the head pointer and the last node's next pointer to maintain circularity. Otherwise, update the previous node's next pointer to skip the node to be deleted. Finally, remove the node and ensure the list remains circular.

Practice

1. What happens when you delete the head node from a circular linked list with multiple nodes?

easy

A. The head moves to the next node and the list remains circular

B. The list becomes empty

C. The last node is deleted instead

D. The list breaks and becomes linear

Solution

1. Step 1: Understand the head deletion in circular linked list

   When the head node is deleted, the next node becomes the new head.

2. Step 2: Maintain circular link

   The last node's next pointer is updated to point to the new head, keeping the list circular.

3. Final Answer:

   The head moves to the next node and the list remains circular -> Option A

4. Quick Check:

   Head deletion updates head and keeps circular [OK]

Hint: Deleting head shifts head to next, list stays circular [OK]

Common Mistakes:

• Assuming list becomes empty after head deletion
• Not updating last node's next pointer
• Breaking circular link accidentally

2. Which of the following is the correct syntax to delete a node with value `key` from a circular linked list in Python?

easy

A. def deleteNode(head, key):
if head.data == key:
# delete head logic

B. def deleteNode(head, key):
while head.data != key:
head = head.next

C. def deleteNode(head, key):
if head is None:
return None

D. def deleteNode(head, key):
head = None
return head

Solution

1. Step 1: Check for empty list

   Before deleting, check if the list is empty (head is None) to avoid errors.

2. Step 2: Return None if list is empty

   If head is None, return None as there is nothing to delete.

3. Final Answer:

   def deleteNode(head, key): if head is None: return None -> Option C

4. Quick Check:

   Empty list check is essential before deletion [OK]

Hint: Always check if list is empty before deleting [OK]

Common Mistakes:

• Not checking if head is None before deletion
• Incorrectly looping without exit condition
• Setting head to None without condition

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

medium

A. 1 -> 5 -> 7 -> 3 -> (back to 1)

B. 1 -> 5 -> 7 -> (back to 1)

C. 1 -> 3 -> 5 -> 7 -> (back to 1)

D. 3 -> 5 -> 7 -> (back to 3)

Solution

1. Step 1: Locate node with value 3

   Traverse the list to find node with value 3 between 1 and 5.

2. Step 2: Remove node 3 and link 1 to 5

   Update node 1's next pointer to node 5, skipping node 3.

3. Final Answer:

   1 -> 5 -> 7 -> (back to 1) -> Option B

4. Quick Check:

   Deleted 3, linked 1 to 5 [OK]

Hint: Skip the node with key, link previous to next [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting wrong node or not deleting at all
• Breaking circular link after deletion

4. Given this code snippet to delete a node from a circular linked list, what is the bug?

def deleteNode(head, key):
    if head is None:
        return None
    curr = head
    while curr.next != head:
        if curr.next.data == key:
            curr.next = curr.next.next
            return head
        curr = curr.next
    return head

medium

A. Does not handle deletion if head node contains the key

B. Infinite loop due to missing break

C. Deletes all nodes instead of one

D. Returns None instead of head

Solution

1. Step 1: Analyze deletion logic

   The code checks nodes after head but never checks if head itself has the key.

2. Step 2: Identify missing head deletion handling

   If head contains the key, this code will not delete it, causing incorrect behavior.

3. Final Answer:

   Does not handle deletion if head node contains the key -> Option A

4. Quick Check:

   Head node deletion must be handled separately [OK]

Hint: Always check if head node matches key before loop [OK]

Common Mistakes:

• Ignoring head node in deletion logic
• Assuming loop covers all nodes including head
• Not updating head pointer after deletion

5. You have a circular linked list with only one node containing value 10. What should be the list after deleting node with value 10?

hard

A. List with node 10 pointing to None

B. List with node 10 pointing to itself

C. List unchanged

D. Empty list (None)

Solution

1. Step 1: Identify single node list condition

   When the list has only one node, head.next points to head itself.

2. Step 2: Delete the only node

   Deleting this node means the list becomes empty, so head should be None.

3. Final Answer:

   Empty list (None) -> Option D

4. Quick Check:

   Single node deletion empties the list [OK]

Hint: Deleting sole node results in empty list (None) [OK]

Common Mistakes:

• Leaving node pointing to itself after deletion
• Not setting head to None
• Assuming list still has one node