Insert at Beginning of Circular Linked List in DSA Rust

Mental Model

A circular linked list loops back to the start, so inserting at the beginning means adding a new node before the current head and updating the last node to point to this new node.

Analogy: Imagine people standing in a circle holding hands. To add a new person at the start, you place them before the first person and make sure the last person now holds hands with the new person, keeping the circle unbroken.

head -> 1 -> 2 -> 3 -> back to head (1)
new node to insert: 0

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> back to 1, insert value 0 at beginning

Goal: Add a new node with value 0 at the start and keep the list circular

Step 1: Create new node with value 0

new_node(0), list: 1 -> 2 -> 3 -> back to 1

Why: We need a new node to insert at the beginning

Step 2: Find last node (3) that points back to head (1)

1 -> 2 -> 3 -> [points to head 1], new_node(0)

Why: We must update last node's pointer to new node to keep circular

Step 3: Set new_node.next to current head (1)

new_node(0) -> 1 -> 2 -> 3 -> back to 1

Why: New node should point to old head to become new start

Step 4: Update last node (3) next pointer to new_node (0)

1 -> 2 -> 3 -> new_node(0) -> 1

Why: Last node must point to new node to maintain circular link

Step 5: Update head pointer to new_node (0)

head -> 0 -> 1 -> 2 -> 3 -> back to 0

Why: Head must point to new node as it is now the first node

Result:

head -> 0 -> 1 -> 2 -> 3 -> back to 0

Annotated Code

DSA Rust

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

#[derive(Debug)]
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 }))
    }
}

struct CircularLinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

impl CircularLinkedList {
    fn new() -> Self {
        CircularLinkedList { head: None }
    }

    fn insert_at_beginning(&mut self, val: i32) {
        let new_node = Node::new(val);

        if self.head.is_none() {
            // Empty list: new node points to itself
            new_node.borrow_mut().next = Some(Rc::clone(&new_node));
            self.head = Some(new_node);
            return;
        }

        // Find last node
        let head = self.head.as_ref().unwrap();
        let mut tail = Rc::clone(head);
        loop {
            let next = tail.borrow().next.as_ref().unwrap().clone();
            if Rc::ptr_eq(&next, head) {
                break;
            }
            tail = next;
        }

        // Link new node to head
        new_node.borrow_mut().next = Some(Rc::clone(head));
        // Link last node to new node
        tail.borrow_mut().next = Some(Rc::clone(&new_node));
        // Update head to new node
        self.head = Some(new_node);
    }

    fn print_list(&self) {
        if self.head.is_none() {
            println!("List is empty");
            return;
        }

        let head = self.head.as_ref().unwrap();
        let mut curr = Rc::clone(head);
        loop {
            print!("{} -> ", curr.borrow().val);
            let next = curr.borrow().next.as_ref().unwrap().clone();
            if Rc::ptr_eq(&next, head) {
                break;
            }
            curr = next;
        }
        println!("back to {}", head.borrow().val);
    }
}

fn main() {
    let mut cll = CircularLinkedList::new();
    // Create initial list 3 -> 2 -> 1 -> back to 3
    cll.insert_at_beginning(3);
    cll.insert_at_beginning(2);
    cll.insert_at_beginning(1);

    println!("Before insertion:");
    cll.print_list();

    // Insert 0 at beginning
    cll.insert_at_beginning(0);

    println!("After insertion at beginning:");
    cll.print_list();
}

let new_node = Node::new(val);

Create new node with given value

if self.head.is_none() { ... }

Handle empty list by pointing new node to itself and setting head

let mut tail = Rc::clone(head); loop { ... }

Find last node that points back to head

new_node.borrow_mut().next = Some(Rc::clone(head));

Set new node's next to current head

tail.borrow_mut().next = Some(Rc::clone(&new_node));

Update last node's next to new node

self.head = Some(new_node);

Update head pointer to new node

Output

Before insertion:

1 -> 2 -> 3 -> back to 1

After insertion at beginning:

0 -> 1 -> 2 -> 3 -> back to 0

Complexity Analysis

Time: O(n) because we must traverse the list to find the last node before insertion

Space: O(1) because insertion uses a fixed amount of extra space for the new node

vs Alternative: Compared to a singly linked list, circular list requires updating the last node's pointer, adding traversal cost; singly linked list insertion at head is O(1)

Edge Cases

Empty circular linked list

New node points to itself and becomes head

DSA Rust

if self.head.is_none() { ... }

Single node circular list

New node inserted before the single node, last node updated correctly

DSA Rust

loop { ... if Rc::ptr_eq(&next, head) { break; } }

When to Use This Pattern

When you see a circular linked list and need to add a node at the start, use the insert at beginning pattern that updates the last node's pointer to maintain the circle.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new node, breaking the circular link
Fix: Always find the last node and update its next pointer to the new node before changing head

Mistake: Forgetting to handle empty list case where head is None
Fix: Check if list is empty and make new node point to itself and set head

Summary

Inserts a new node at the start of a circular linked list and updates pointers to keep the circle intact.

Use when you need to add elements quickly at the beginning of a circular linked list.

The key is to update the last node's pointer to the new node and then update head to the new node.

Practice

1. What happens when you insert a new node at the beginning of a circular linked list?

easy

A. The new node is added at the end and does not affect the head.

B. The new node replaces the last node in the list.

C. The list breaks and becomes a linear linked list.

D. The new node becomes the head and points to the old head, maintaining the circular link.

Solution

1. Step 1: Understand circular linked list structure

   In a circular linked list, the last node points back to the head node, forming a circle.

2. Step 2: Insert new node at beginning

   The new node is linked to the current head, and the last node's next pointer is updated to this new node, making it the new head.

3. Final Answer:

   The new node becomes the head and points to the old head, maintaining the circular link. -> Option D

4. Quick Check:

   New head points to old head, circle intact [OK]

Hint: New head points to old head; last node links to new head [OK]

Common Mistakes:

• Forgetting to update last node's next pointer
• Breaking the circular link accidentally
• Replacing the last node instead of adding new head

2. Which Rust code snippet correctly creates a new node and inserts it at the beginning of a circular linked list?

easy

A. let new_node = Node { data: val, next: head.clone() }; last.next = Some(new_node.clone()); head = Some(new_node);

B. let new_node = Node { data: val, next: None }; head = Some(new_node);

C. let new_node = Node { data: val, next: last.clone() }; head = Some(new_node);

D. let new_node = Node { data: val, next: head.clone() }; head = Some(new_node);

Solution

1. Step 1: Create new node pointing to current head

   The new node's next pointer should point to the current head to maintain the list.

2. Step 2: Update last node's next to new node and update head

   Since it's circular, last node's next must point to new node, then head is updated to new node.

3. Final Answer:

   let new_node = Node { data: val, next: head.clone() }; last.next = Some(new_node.clone()); head = Some(new_node); -> Option A

4. Quick Check:

   New node next = head, last next = new node, head updated [OK]

Hint: New node next = head; last.next updated; head = new node [OK]

Common Mistakes:

• Not updating last node's next pointer
• Setting new node's next to None
• Not cloning nodes properly causing ownership errors

3. Given the following Rust code for inserting at the beginning of a circular linked list, what will be the printed list after insertion?

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

fn print_list(head: &Option) {
    if head.is_none() { return; }
    let mut temp = head.as_ref();
    loop {
        if let Some(node) = temp {
            print!("{} -> ", node.data);
            temp = node.next.as_ref();
            if temp == head.as_ref() { break; }
        }
    }
    println!("null");
}

fn insert_beginning(head: &mut Option, val: i32) {
    let mut new_node = Box::new(Node { data: val, next: None });
    if head.is_none() {
        new_node.next = Some(new_node.clone());
        *head = Some(new_node);
        return;
    }
    let mut temp = head.as_mut().unwrap();
    while temp.next.as_ref().unwrap().as_ref() != head.as_ref().unwrap().as_ref() {
        temp = temp.next.as_mut().unwrap();
    }
    new_node.next = head.take();
    temp.next = Some(new_node);
    *head = temp.next.clone();
}

fn main() {
    let mut head = None;
    insert_beginning(&mut head, 10);
    insert_beginning(&mut head, 20);
    insert_beginning(&mut head, 30);
    print_list(&head);
}

medium

A. 30 -> 10 -> 20 -> null

B. 30 -> 20 -> 10 -> null

C. 10 -> 20 -> 30 -> null

D. 20 -> 30 -> 10 -> null

Solution

1. Step 1: Trace insertions in order

   Insert 10 first: list is 10 -> 10 (single node points to itself). Insert 20: new node 20 points to 10, last node (10) points to 20, head updated to 20. Insert 30: new node 30 points to 20, last node (10) points to 30, head updated to 30.

2. Step 2: Print list starting from head

   Starting at 30, next is 20, then 10, then back to 30 (stop). So printed: 30 -> 20 -> 10 -> null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option B

4. Quick Check:

   New nodes inserted at head, order reversed [OK]

Hint: New insertions become head, list order reverses [OK]

Common Mistakes:

• Confusing order of nodes after insertion
• Not updating last node's next pointer correctly
• Incorrect loop condition in print function

4. Identify the bug in this Rust function that inserts a node at the beginning of a circular linked list:

fn insert_beginning(head: &mut Option, val: i32) {
    let mut new_node = Box::new(Node { data: val, next: None });
    if head.is_none() {
        new_node.next = Some(new_node.clone());
        *head = Some(new_node);
        return;
    }
    let mut temp = head.as_mut().unwrap();
    while temp.next.as_ref().unwrap().as_ref() != head.as_ref().unwrap().as_ref() {
        temp = temp.next.as_mut().unwrap();
    }
    new_node.next = head.take();
    temp.next = Some(new_node);
    *head = temp.next.clone();
}

medium

A. head.take() removes the list causing loss of nodes.

B. The while loop condition never terminates causing infinite loop.

C. Cloning new_node causes infinite recursion and stack overflow.

D. temp.next is not updated correctly to point to new_node.

Solution

1. Step 1: Analyze cloning of new_node

   Cloning new_node inside new_node.next = Some(new_node.clone()) causes recursive cloning because new_node contains next which contains new_node again, leading to infinite recursion.

2. Step 2: Understand Rust cloning behavior

   Rust's clone on a Box<Node> will recursively clone the entire structure, so cloning a node that points to itself causes stack overflow.

3. Final Answer:

   Cloning new_node causes infinite recursion and stack overflow. -> Option C

4. Quick Check:

   Self-referential clone causes infinite recursion [OK]

Hint: Avoid cloning self-referential nodes to prevent recursion [OK]

Common Mistakes:

• Ignoring cloning impact on self-referential structures
• Assuming head.take() deletes nodes permanently
• Misreading loop condition as infinite

5. You want to insert a new node at the beginning of a circular linked list that may be empty or non-empty. Which approach correctly handles both cases in Rust without cloning self-referential nodes?

fn insert_beginning(head: &mut Option, val: i32) {
    let mut new_node = Box::new(Node { data: val, next: None });
    if head.is_none() {
        // Case 1: Empty list
        new_node.next = Some(new_node); // Problem here
        *head = Some(new_node);
        return;
    }
    // Case 2: Non-empty list
    let mut temp = head.as_mut().unwrap();
    while temp.next.as_ref().unwrap().as_ref() != head.as_ref().unwrap().as_ref() {
        temp = temp.next.as_mut().unwrap();
    }
    new_node.next = head.take();
    temp.next = Some(new_node);
    *head = temp.next.clone();
}

What is the correct fix for Case 1 to avoid cloning and infinite recursion?

hard

A. Use a raw pointer or Rc to create self-reference safely.

B. Set new_node.next = None and update last node later.

C. Create a temporary node and assign new_node.next to it.

D. Use unsafe code to manually set new_node.next to itself.

Solution

1. Step 1: Understand self-referential node problem

   Assigning new_node.next = Some(new_node) tries to move new_node into itself, which is invalid and causes infinite recursion if cloned.

2. Step 2: Use Rc or raw pointers

   Rust's safe way to handle self-references is using Rc (reference counting) and RefCell (interior mutability) to create cyclic references without cloning issues.

3. Step 3: Avoid unsafe code unless necessary

   Using unsafe code is error-prone; Rc<RefCell> is the recommended safe approach.

4. Final Answer:

   Use a raw pointer or Rc to create self-reference safely. -> Option A

5. Quick Check:

   Safe self-reference needs Rc/RefCell or raw pointers [OK]

Hint: Use Rc<RefCell> for safe self-referential nodes [OK]

Common Mistakes:

• Assigning node to itself directly causing move errors
• Using None breaks circular property
• Using unsafe code without understanding risks