Insert at End of Circular Linked List in DSA Rust

Mental Model

A circular linked list connects the last node back to the first, forming a loop. Inserting at the end means adding a new node just before the first node, then updating the last node's pointer to this new node.

Analogy: Imagine people sitting in a circle holding hands. Adding a new person at the end means placing them just before the first person and making sure the last person now holds the new person's hand, keeping the circle unbroken.

head -> 1 -> 2 -> 3 -> head (circle)
Insert new node 4 at end:
head -> 1 -> 2 -> 3 -> 4 -> head (circle)

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 4 at end

Goal: Add node with value 4 at the end so the list remains circular

Step 1: start at head node 1

head -> [1] -> 2 -> 3 -> head

Why: We begin traversal from the head to find the last node

Step 2: move to node 2

head -> 1 -> [2] -> 3 -> head

Why: Traverse to next node to find the last node

Step 3: move to node 3

head -> 1 -> 2 -> [3] -> head

Why: Node 3 points back to head, so it is the last node

Step 4: create new node 4 and link it after node 3

head -> 1 -> 2 -> 3 -> [4] -> head

Why: Insert new node after last node to add at end

Step 5: update node 3's next pointer to new node 4

head -> 1 -> 2 -> 3 -> 4 -> head

Why: Maintain circular link by pointing last node to new node

Result:

head -> 1 -> 2 -> 3 -> 4 -> head

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 }))
    }
}

fn insert_at_end(head: Option<Rc<RefCell<Node>>>, val: i32) -> Option<Rc<RefCell<Node>>> {
    let new_node = Node::new(val);
    if head.is_none() {
        // Empty list: new node points to itself
        new_node.borrow_mut().next = Some(Rc::clone(&new_node));
        return Some(new_node);
    }

    let head_ref = head.as_ref().unwrap();
    let mut curr = Rc::clone(head_ref);

    // Traverse to last node (node whose next is head)
    loop {
        let next_node = curr.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&next_node, head_ref) {
            break;
        }
        curr = next_node;
    }

    // Insert new_node after last node
    new_node.borrow_mut().next = Some(Rc::clone(head_ref));
    curr.borrow_mut().next = Some(Rc::clone(&new_node));

    head
}

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

fn main() {
    // Create circular list 1 -> 2 -> 3 -> head
    let node1 = Node::new(1);
    let node2 = Node::new(2);
    let node3 = Node::new(3);

    node1.borrow_mut().next = Some(Rc::clone(&node2));
    node2.borrow_mut().next = Some(Rc::clone(&node3));
    node3.borrow_mut().next = Some(Rc::clone(&node1));

    let head = Some(node1);

    println!("Before insertion:");
    print_circular_list(head.clone());

    let head = insert_at_end(head, 4);

    println!("After insertion:");
    print_circular_list(head);
}

if head.is_none() { new_node.borrow_mut().next = Some(Rc::clone(&new_node)); return Some(new_node); }

handle empty list by making new node point to itself

loop { let next_node = curr.borrow().next.as_ref().unwrap().clone(); if Rc::ptr_eq(&next_node, head_ref) { break; } curr = next_node; }

traverse until we find last node pointing back to head

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

insert new node after last node and link back to head

Output

Before insertion:

1 -> 2 -> 3 -> head

After insertion:

1 -> 2 -> 3 -> 4 -> head

Complexity Analysis

Time: O(n) because we traverse all n nodes once to find the last node

Space: O(1) because insertion uses constant extra space

vs Alternative: Compared to singly linked list without circular link, circular list requires traversal to last node to maintain loop, but insertion is still O(n)

Edge Cases

empty list

new node points to itself, forming a single-node circular list

DSA Rust

if head.is_none() {
        new_node.borrow_mut().next = Some(Rc::clone(&new_node));
        return Some(new_node);
    }

single node list

new node inserted after the single node, and last node points to head

DSA Rust

loop {
        let next_node = curr.borrow().next.as_ref().unwrap().clone();
        if Rc::ptr_eq(&next_node, head_ref) {
            break;
        }
        curr = next_node;
    }

When to Use This Pattern

When you see a linked list where the last node points back to the first, and you need to add a node at the end, use the circular linked list insertion pattern to maintain the loop.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new node, breaking the circular link
Fix: After inserting the new node, always update the last node's next pointer to point to the new node

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if the list is empty and create a self-pointing node as the new head

Summary

Adds a new node at the end of a circular linked list while keeping the list circular.

Use when you want to append data to a circular linked list without breaking its loop structure.

The key is to find the last node that points back to head and insert the new node just before head.

Practice

1. What is the main difference between a circular linked list and a regular singly linked list?

easy

A. In a circular linked list, the last node points back to the first node.

B. In a circular linked list, nodes have two pointers instead of one.

C. In a circular linked list, nodes are stored in an array.

D. In a circular linked list, nodes cannot be inserted at the end.

Solution

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

   A circular linked list connects the last node back to the first node, forming a circle.

2. Step 2: Compare with a regular singly linked list

   A regular singly linked list ends with a node pointing to null, not back to the first node.

3. Final Answer:

   In a circular linked list, the last node points back to the first node. -> Option A

4. Quick Check:

   Circular linked list last node points to head [OK]

Hint: Remember: circular means last node loops to first [OK]

Common Mistakes:

• Thinking circular lists have two pointers per node
• Confusing circular linked list with doubly linked list
• Assuming circular lists cannot have end insertions

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

easy

A. let new_node = Node::new(data); new_node.next = None; tail.next = Some(new_node); tail = new_node;

B. let new_node = Node::new(data); new_node.next = head; tail.next = Some(new_node); tail = new_node;

C. let new_node = Node::new(data); new_node.next = tail; head.next = Some(new_node); tail = new_node;

D. let new_node = Node::new(data); new_node.next = head; head.next = Some(new_node); tail = new_node;

Solution

1. Step 1: Create new node and link to head

   In a circular linked list, the new node's next should point to head to maintain the circle.

2. Step 2: Update tail's next and tail pointer

   Tail's next should point to the new node, and tail should be updated to new node.

3. Final Answer:

   let new_node = Node::new(data); new_node.next = head; tail.next = Some(new_node); tail = new_node; -> Option B

4. Quick Check:

   New node points to head, tail updated [OK]

Hint: New node's next must point to head in circular list [OK]

Common Mistakes:

• Setting new node's next to None breaks the circle
• Linking new node to tail instead of head
• Not updating tail pointer after insertion

3. Given the following Rust code for inserting at the end of a circular linked list, what will be the printed output after inserting 4 into the list 1 -> 2 -> 3 -> (back to 1)?

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

// After insertion of 4 at end
// List structure: 1 -> 2 -> 3 -> 4 -> (back to 1)

medium

A. 1 -> 2 -> 3 -> 4 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 1 -> 2 -> 3 -> 4 -> null

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

Solution

1. Step 1: Understand the print loop logic

   The loop prints nodes until it reaches the head again, then breaks to avoid infinite loop.

2. Step 2: Trace the list after insertion

   After inserting 4 at end, list is 1 -> 2 -> 3 -> 4 -> back to 1. The print stops before repeating head.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option C

4. Quick Check:

   Print stops before repeating head [OK]

Hint: Print stops before repeating head node [OK]

Common Mistakes:

• Printing the head node twice causing infinite loop
• Not breaking loop on head node detection
• Confusing order of nodes after insertion

4. The following Rust code attempts to insert a new node at the end of a circular linked list but causes a runtime error. What is the error?

fn insert_end(tail: &mut Option, data: i32) {
    let mut new_node = Box::new(Node::new(data));
    new_node.next = None;
    if tail.is_none() {
        *tail = Some(new_node);
        tail.as_mut().unwrap().next = tail.clone();
    } else {
        new_node.next = tail.as_ref().unwrap().next.clone();
        tail.as_mut().unwrap().next = Some(new_node);
        *tail = tail.as_mut().unwrap().next.clone();
    }
}

medium

A. Using tail.clone() causes ownership issues leading to runtime panic.

B. Setting new_node.next to None breaks the circular link causing infinite loop.

C. Assigning *tail = tail.as_mut().unwrap().next.clone() causes borrow checker error.

D. Not updating tail pointer after insertion causes stale tail reference.

Solution

1. Step 1: Analyze tail.clone() usage

   Cloning tail (which is an Option) duplicates ownership, which Rust forbids at runtime for Box.

2. Step 2: Understand Rust ownership rules

   Box pointers cannot be cloned freely; this causes runtime panic or compile error due to ownership violation.

3. Final Answer:

   Using tail.clone() causes ownership issues leading to runtime panic. -> Option A

4. Quick Check:

   Cloning Box without proper ownership causes error [OK]

Hint: Avoid cloning Box pointers; use references or Rc instead [OK]

Common Mistakes:

• Setting next to None breaking circularity
• Ignoring Rust ownership and cloning rules
• Not updating tail pointer correctly

5. You have a circular linked list with nodes containing values [10, 20, 30]. You want to insert a new node with value 25 at the end, but also maintain a sorted order in the circular list. Which approach correctly inserts 25 while keeping the list sorted?

hard

A. Replace the last node's value with 25 without changing links.

B. Insert 25 at the end and then sort the entire list.

C. Insert 25 at the head and update tail to new node.

D. Traverse the list to find the correct position and insert 25 there, updating links accordingly.

Solution

1. Step 1: Understand sorted circular linked list insertion

   To keep the list sorted, find the correct position where 25 fits between nodes.

2. Step 2: Insert node at correct position and update links

   Traverse nodes until finding node with value less than 25 and next node greater than 25, then insert new node there.

3. Step 3: Update tail if inserted at end

   If inserted after the current tail, update tail pointer to new node to maintain list integrity.

4. Final Answer:

   Traverse the list to find the correct position and insert 25 there, updating links accordingly. -> Option D

5. Quick Check:

   Insert at sorted position to keep order [OK]

Hint: Insert at correct sorted position, not just at end [OK]

Common Mistakes:

• Inserting at end without sorting breaks order
• Replacing node value loses data integrity
• Not updating tail when inserting at end