Delete a Node from Circular Linked List in DSA Rust

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 ->
↑                 ↓
←-----------------

Dry Run Walkthrough

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

Goal: Remove node 3 and keep the list circular with nodes 1->2->4

Step 1: start at head (1), check if head is node to delete

1 -> 2 -> 3 -> 4 ->
↑                 ↓
←-----------------

Why: We must find the node to delete; head is not 3, so continue

Step 2: move to next node (2), check if next is node to delete

1 -> 2 -> 3 -> 4 ->
    ↑             ↓
←-----------------

Why: Check if node after current (2) is 3 to delete

Step 3: found node 3 after current (2), adjust 2's next to 4, skipping 3

1 -> 2 -> 4 ->
↑         ↓
←---------

Why: By linking 2 directly to 4, node 3 is removed from the circle

Step 4: confirm circle intact by checking 4's next points back to 1

1 -> 2 -> 4 ->
↑         ↓
←---------

Why: Ensures the circular structure remains after deletion

Result:

1 -> 2 -> 4 ->
↑         ↓
←---------

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

fn delete_node(head: Option<Rc<RefCell<Node>>>, key: i32) -> Option<Rc<RefCell<Node>>> {
    if head.is_none() {
        return None;
    }
    let head = head.unwrap();
    // If list has only one node
    if Rc::ptr_eq(&head, head.borrow().next.as_ref().unwrap()) && head.borrow().val == key {
        return None;
    }
    let mut curr = head.clone();
    // If head is node to delete
    if head.borrow().val == key {
        // Find last node to update its next
        let mut last = head.clone();
        while !Rc::ptr_eq(&last.borrow().next.as_ref().unwrap(), &head) {
            let next = last.borrow().next.as_ref().unwrap().clone();
            last = next;
        }
        let new_head = head.borrow().next.as_ref().unwrap().clone();
        last.borrow_mut().next = Some(new_head.clone());
        return Some(new_head);
    }
    // Otherwise, find node before the one to delete
    loop {
        let next_node = curr.borrow().next.as_ref().unwrap().clone();
        if next_node.borrow().val == key {
            let next_next = next_node.borrow().next.as_ref().unwrap().clone();
            curr.borrow_mut().next = Some(next_next);
            break;
        }
        curr = next_node;
        if Rc::ptr_eq(&curr, &head) {
            break; // key not found
        }
    }
    Some(head)
}

fn print_circular_list(head: Option<Rc<RefCell<Node>>>) {
    if head.is_none() {
        println!("List is empty");
        return;
    }
    let head = head.unwrap();
    let mut curr = head.clone();
    loop {
        print!("{} -> ", curr.borrow().val);
        curr = curr.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&curr, &head) {
            break;
        }
    }
    println!("(back to head)");
}

fn main() {
    // Create circular list 1->2->3->4-> back to 1
    let n1 = Node::new(1);
    let n2 = Node::new(2);
    let n3 = Node::new(3);
    let n4 = Node::new(4);
    n1.borrow_mut().next = Some(n2.clone());
    n2.borrow_mut().next = Some(n3.clone());
    n3.borrow_mut().next = Some(n4.clone());
    n4.borrow_mut().next = Some(n1.clone());

    println!("Original list:");
    print_circular_list(Some(n1.clone()));

    let new_head = delete_node(Some(n1.clone()), 3);

    println!("After deleting 3:");
    print_circular_list(new_head);
}

if head.is_none() { return None; }

handle empty list case

if Rc::ptr_eq(&head, head.borrow().next.as_ref().unwrap()) && head.borrow().val == key { return None; }

handle single node list where node matches key

if head.borrow().val == key { ... }

if head is node to delete, find last node and update its next to new head

loop { let next_node = curr.borrow().next.as_ref().unwrap().clone(); if next_node.borrow().val == key { curr.borrow_mut().next = Some(next_node.borrow().next.as_ref().unwrap().clone()); break; } curr = next_node; if Rc::ptr_eq(&curr, &head) { break; } }

traverse to find node before target and adjust links to remove target

Output

Original list:

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

After deleting 3:

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

Complexity Analysis

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

Space: O(n) due to Rc and RefCell overhead for shared ownership and mutability

vs Alternative: Compared to singly linked list deletion which is O(n), circular list deletion is similar but requires careful handling of the circular link

Edge Cases

empty list

function returns None immediately

DSA Rust

if head.is_none() { return None; }

single node list where node matches key

list becomes empty (None)

DSA Rust

if Rc::ptr_eq(&head, head.borrow().next.as_ref().unwrap()) && head.borrow().val == key { return None; }

deleting head node in multi-node list

head is updated to next node and last node's next updated to new head

DSA Rust

if head.borrow().val == key { ... }

key not found in list

list remains unchanged

DSA Rust

if Rc::ptr_eq(&curr, &head) { break; }

When to Use This Pattern

When you see a problem asking to delete a node in a circular linked list, use pointer traversal with careful link updates to maintain the circle.

Common Mistakes

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

Mistake: Breaking the circular link by setting next to None
Fix: Always keep next pointers linking back to head to maintain circularity

Summary

Deletes a node from a circular linked list while keeping the list circular.

Use when you need to remove a specific value from a circular linked list.

The key is to adjust the previous node's next pointer to skip the deleted node without breaking the circle.

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