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

Concept Flow - Delete a Node from Circular Linked List

Start at head node

↓

Check if list is empty?

Yes→Stop: Nothing to delete

No↓

Traverse nodes until node with target value found or back to head

↓

If node found

↓

If node is head

↓

Find last node to update its next pointer

↓

Update head to next node

↓

Else

↓

Update previous node's next pointer to skip deleted node

↓

Node deleted

↓

Done

Start at head, check if list is empty, traverse to find node, update pointers to remove node, handle special case if node is head.

Execution Sample

DSA Rust

fn delete_node(head: &mut Option<Box<Node>>, key: i32) {
    if head.is_none() { return; }
    let mut curr = head.as_mut().unwrap();
    // traversal and deletion logic
}

Deletes a node with given key from a circular linked list, updating pointers accordingly.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Check if list is empty	None or head node	No change	head -> 1 -> 2 -> 3 -> 1 (circular)
2	Start traversal at head	Node 1	No change	head -> 1 -> 2 -> 3 -> 1 (circular)
3	Check if current node data == key (2)?	Node 1	No change	head -> 1 -> 2 -> 3 -> 1 (circular)
4	Move to next node	Node 2	No change	head -> 1 -> 2 -> 3 -> 1 (circular)
5	Check if current node data == key (2)?	Node 2	No change	head -> 1 -> 2 -> 3 -> 1 (circular)
6	Node found, update previous node's next	Node 2	Node 1.next = Node 3	head -> 1 -> 3 -> 1 (circular)
7	Delete node 2	Node 2 removed	No dangling pointers	head -> 1 -> 3 -> 1 (circular)
8	End	N/A	N/A	head -> 1 -> 3 -> 1 (circular)

💡 Node with key found and deleted; traversal stops.

Variable Tracker

Variable	Start	After Step 4	After Step 6	Final
head	Node 1	Node 1	Node 1	Node 1
curr	Node 1	Node 2	Node 2	N/A (deleted)
prev	Node 1	Node 1	Node 1	Node 1
list_size	3	3	3	2

Key Moments - 3 Insights

Why do we need to update the previous node's next pointer when deleting a node?

Because the circular linked list nodes point to each other, skipping the deleted node requires changing the previous node's next pointer to the deleted node's next. See execution_table step 6.

What happens if the node to delete is the head node?

We must find the last node to update its next pointer to the new head, then update head to head.next. This special case ensures the list remains circular. This is implied in concept_flow.

Why does traversal stop when we come back to the head node?

Because the list is circular, reaching the head again means we've checked all nodes without finding the key. See concept_flow traversal step.

Visual Quiz - 3 Questions

Look at the execution_table, what is the 'curr' node at step 4?

A Node 2

B Node 3

C Node 1

D None

💡 Hint

Check the 'Current Node' column at step 4 in execution_table.

At which step does the list size decrease?

A Step 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look at variable_tracker row 'list_size' changes.

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

A Update head to None

B Update last node's next to new head

C No pointer update needed

D Update head's next to itself

💡 Hint

Refer to concept_flow step about deleting head node.

Concept Snapshot

Delete Node in Circular Linked List:
- Start at head, check empty list
- Traverse nodes until target found or back to head
- If node found:
  - If head, update last node's next and head pointer
  - Else, update previous node's next to skip node
- Node removed, list remains circular

Full Transcript

To delete a node from a circular linked list, start at the head node. If the list is empty, stop. Otherwise, traverse nodes checking each node's data against the key. If the node is found, update pointers to remove it. If the node is the head, find the last node to update its next pointer to the new head, then update the head pointer. If the node is not the head, update the previous node's next pointer to skip the deleted node. This keeps the list circular. The traversal stops when the node is deleted or when we return to the head without finding the node.

Practice

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

easy

A. The list points to itself indefinitely.

B. The list still contains the deleted node.

C. The list becomes empty (null).

D. The list throws an error.

Solution

1. Step 1: Understand the structure of a single-node circular linked list

   In a circular linked list with one node, the node's next pointer points to itself.

2. Step 2: Delete the only node

   Removing this node means no nodes remain, so the list becomes empty (null).

3. Final Answer:

   The list becomes empty (null). -> Option C

4. Quick Check:

   Single node deleted = empty list [OK]

Hint: Deleting the only node empties the list [OK]

Common Mistakes:

• Assuming the list still contains the deleted node
• Thinking the list points to itself after deletion
• Expecting an error instead of empty list

2. Which Rust syntax correctly declares a mutable circular linked list node struct with a next pointer?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: &Node }

C. struct Node { data: i32, next: Node }

D. struct Node { data: i32, next: Option> }

Solution

1. Step 1: Understand Rust ownership for circular references

   Rust disallows direct cyclic ownership. Using Rc allows multiple owners and interior mutability.

2. Step 2: Identify correct syntax for mutable circular linked list node

   struct Node { data: i32, next: Option> } uses Option> which supports cycles and mutability safely.

3. Final Answer:

   struct Node { data: i32, next: Option> } -> Option D

4. Quick Check:

   Use Rc for circular mutable nodes [OK]

Hint: Use Rc and RefCell for mutable circular references in Rust [OK]

Common Mistakes:

• Using plain Box<Node> causes ownership errors
• Using references (&Node) disallows ownership
• Using Node directly causes infinite size error

3. Given this Rust code snippet deleting a node with value 3 from a circular linked list:

let mut head = create_circular_list(vec![1, 2, 3, 4]); delete_node(&mut head, 3); print_list(&head);

What is the printed output?

medium

A. 1 -> 2 -> 4 -> 1 (circular)

B. 1 -> 2 -> 3 -> 4 -> 1 (circular)

C. 2 -> 3 -> 4 -> 2 (circular)

D. 1 -> 2 -> 4 -> null

Solution

1. Step 1: Understand the initial list

   The list is circular with nodes 1, 2, 3, 4 linked in a loop.

2. Step 2: Delete node with value 3

   Node 3 is removed, so the list becomes 1 -> 2 -> 4, then back to 1.

3. Final Answer:

   1 -> 2 -> 4 -> 1 (circular) -> Option A

4. Quick Check:

   Deleted 3, list loops 1-2-4 [OK]

Hint: Deleting node removes it, links neighbors circularly [OK]

Common Mistakes:

• Forgetting to link node 2 to node 4
• Printing null instead of circular loop
• Not deleting the correct node

4. Identify the bug in this Rust function snippet for deleting a node from a circular linked list:

fn delete_node(head: &mut Option>, key: i32) { let mut curr = head.clone().unwrap(); while curr.borrow().data != key { curr = curr.borrow().next.clone().unwrap(); } let next_node = curr.borrow().next.clone(); curr.borrow_mut().next = next_node.unwrap().borrow().next.clone(); }

medium

A. It causes infinite loop if key not found.

B. It does not handle deleting the head node correctly.

C. It leaks memory by not freeing nodes.

D. It uses unwrap() unsafely causing panic.

Solution

1. Step 1: Analyze the while loop condition

   The loop continues until curr's data equals key, but no check if key exists, so it loops infinitely if key missing.

2. Step 2: Check for missing exit condition

   Without a break or stop when full circle is done, infinite loop occurs if key not found.

3. Final Answer:

   It causes infinite loop if key not found. -> Option A

4. Quick Check:

   No key check = infinite loop risk [OK]

Hint: Always check for key existence to avoid infinite loops [OK]

Common Mistakes:

• Assuming key always exists
• Not checking for full circle traversal
• Ignoring unwrap() panic risks

5. How would you delete the head node from a circular linked list in Rust while maintaining the circular structure?

hard

A. Replace head data with next node data and delete next node.

B. Find the last node, set its next to head's next, then update head to head's next.

C. Delete head and leave the last node pointing to old head.

D. Set head to None directly without updating other nodes.

Solution

1. Step 1: Locate the last node in the circular list

   The last node points back to head; find it by traversing until next points to head.

2. Step 2: Update last node's next pointer and head

   Set last node's next to head's next node, then update head to head's next to maintain circularity.

3. Final Answer:

   Find last node, link it to head's next, update head to head's next. -> Option B

4. Quick Check:

   Update last node and head to delete head safely [OK]

Hint: Link last node to new head, then update head [OK]

Common Mistakes:

• Setting head to None breaks circularity
• Not updating last node's next pointer
• Deleting head without adjusting links