Insert at Beginning of Circular Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes at beginning in circular linked list

What is the printed state of the circular linked list after inserting 10, then 20, then 30 at the beginning?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

struct CircularLinkedList {
    head: Option<Box<Node>>,
}

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

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

    fn print_list(&self) {
        if self.head.is_none() {
            println!("List is empty");
            return;
        }
        let mut temp = self.head.as_ref();
        loop {
            print!("{} -> ", temp.unwrap().data);
            temp = temp.unwrap().next.as_ref();
            if temp.unwrap().data == self.head.as_ref().unwrap().data {
                break;
            }
        }
        println!("null");
    }
}

fn main() {
    let mut cll = CircularLinkedList::new();
    cll.insert_at_beginning(10);
    cll.insert_at_beginning(20);
    cll.insert_at_beginning(30);
    cll.print_list();
}

A 20 -> 30 -> 10 -> null

B 10 -> 20 -> 30 -> null

C 30 -> 20 -> 10 -> null

D 30 -> 10 -> 20 -> null

💡 Hint

Remember, inserting at beginning means the newest node becomes the head and the last node points to it.

Each new node is inserted before the current head, and the last node's next pointer is updated to point to the new head, maintaining circularity. So after inserting 30, 20, 10 in that order at beginning, the list is 30 -> 20 -> 10 -> null.

❓ Predict Output

intermediate

Output after inserting a single node in empty circular linked list

What is the printed state of the circular linked list after inserting only one node with value 5 at the beginning?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

struct CircularLinkedList {
    head: Option<Box<Node>>,
}

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

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

    fn print_list(&self) {
        if self.head.is_none() {
            println!("List is empty");
            return;
        }
        let mut temp = self.head.as_ref();
        loop {
            print!("{} -> ", temp.unwrap().data);
            temp = temp.unwrap().next.as_ref();
            if temp.unwrap().data == self.head.as_ref().unwrap().data {
                break;
            }
        }
        println!("null");
    }
}

fn main() {
    let mut cll = CircularLinkedList::new();
    cll.insert_at_beginning(5);
    cll.print_list();
}

A 5 -> null

B 5 -> 5 -> null

C null

D Error: infinite loop

💡 Hint

In a circular linked list with one node, the node points to itself.

When only one node exists, its next pointer points to itself, so printing it once and stopping when we reach the head again prints the node twice in the loop before breaking.

🔧 Debug

advanced

Identify the bug in insert_at_beginning method

Which option correctly describes the bug in this insert_at_beginning method for circular linked list?

DSA Rust

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

A The head pointer is not updated after insertion, so list is broken.

B The new_node.next is set incorrectly, breaking circularity.

C The loop to find last node may panic if list has only one node due to unwrap on None.

D The code clones new_node which causes infinite recursion and stack overflow.

💡 Hint

Look at the line where new_node.next is assigned when list is empty.

Cloning new_node inside its own initialization causes infinite recursion because Box does not implement Clone by default and cloning a Box containing itself is invalid, leading to stack overflow.

❓ Predict Output

advanced

Output after multiple insertions and one traversal

After inserting 1, 2, 3 at beginning in that order, what is the output of one traversal starting from head?

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

struct CircularLinkedList {
    head: Option<Box<Node>>,
}

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

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

    fn traverse_once(&self) -> Vec<i32> {
        let mut result = Vec::new();
        if self.head.is_none() {
            return result;
        }
        let mut temp = self.head.as_ref();
        loop {
            result.push(temp.unwrap().data);
            temp = temp.unwrap().next.as_ref();
            if temp.unwrap().data == self.head.as_ref().unwrap().data {
                break;
            }
        }
        result
    }
}

fn main() {
    let mut cll = CircularLinkedList::new();
    cll.insert_at_beginning(1);
    cll.insert_at_beginning(2);
    cll.insert_at_beginning(3);
    let output = cll.traverse_once();
    println!("{:?}", output);
}

A [3, 2, 1]

B [1, 2, 3]

C [2, 3, 1]

D [1, 3, 2]

💡 Hint

Inserting at beginning reverses the order of insertion.

Each new node becomes the head, so after inserting 1, 2, 3 at beginning, the list order is 3 -> 2 -> 1.

🧠 Conceptual

expert

Why update last node's next pointer when inserting at beginning?

In a circular linked list, why must we update the last node's next pointer when inserting a new node at the beginning?

A To maintain the circular link so the last node points to the new head, preserving the loop.

B To reverse the list order after insertion.

C To free the old head node and avoid memory leaks.

D To ensure the new node points to itself when list has multiple nodes.

💡 Hint

Think about what keeps the list circular after changing the head.

The last node's next pointer must point to the new head node to keep the list circular. Without this update, the last node would still point to the old head, breaking the circular structure.

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