Create a Circular Singly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Circular Singly Linked List after insertions?

Consider a circular singly linked list where we insert nodes with values 10, 20, and 30 in that order. What is the printed state of the list after these insertions?

DSA Rust

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

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

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

    fn insert(&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!("(head)");
    }
}

fn main() {
    let mut list = CircularSinglyLinkedList::new();
    list.insert(10);
    list.insert(20);
    list.insert(30);
    list.print_list();
}

A 10 -> 20 -> 30 -> (head)

B 30 -> 10 -> 20 -> (head)

C 30 -> 20 -> 10 -> (head)

D 20 -> 30 -> 10 -> (head)

💡 Hint

Remember that new nodes are inserted at the head, and the list is circular.

Each new node is inserted at the head, so the last inserted node becomes the new head. The list is circular, so after the last node, it points back to the head.

🧠 Conceptual

intermediate

How does a circular singly linked list differ from a regular singly linked list?

Choose the correct statement that describes the main difference between a circular singly linked list and a regular singly linked list.

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

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

C In a circular singly linked list, the head node is always null.

D In a circular singly linked list, nodes are stored in an array instead of linked nodes.

💡 Hint

Think about what makes the list circular.

The key difference is that the last node's next pointer points back to the head, creating a loop.

🔧 Debug

advanced

What error occurs when running this circular singly linked list insertion code?

This Rust code attempts to insert nodes into a circular singly linked list but causes a compile-time error. What is the error?

DSA Rust

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

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

impl CircularSinglyLinkedList {
    fn insert(&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);
            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 Compile-time error: cannot move out of borrowed content

B Runtime error: stack overflow due to infinite recursion

C Runtime error: null pointer dereference

D No error, code runs correctly

💡 Hint

Look at how new_node is assigned to its own next field.

Assigning new_node.next = Some(new_node) tries to move new_node into itself, which is not allowed and causes a compile-time error.

📝 Syntax

advanced

Which option correctly implements insertion at the end of a circular singly linked list in Rust?

Select the code snippet that correctly inserts a new node at the end of a circular singly linked list.

A

fn insert_end(&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.clone();
        temp.next = Some(new_node);
    }
}

B

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

C

fn insert_end(&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.clone();
        temp.next = Some(new_node);
        self.head = Some(new_node);
    }
}

D

fn insert_end(&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 = None;
        temp.next = Some(new_node);
    }
}

💡 Hint

Remember the last node's next must point to head to keep the list circular.

Option A correctly sets new_node.next to head and updates the last node's next to new_node, preserving circularity.

🚀 Application

expert

What is the time complexity of searching for a value in a circular singly linked list of n nodes?

Assuming no additional data structures, what is the time complexity to find a node with a specific value in a circular singly linked list with n nodes?

A O(n^2), because each node points to the next causing nested traversal

B O(1), because the list is circular and you can jump to any node

C O(log n), because the circular structure allows binary search

D O(n), because you may need to traverse all nodes once

💡 Hint

Think about how you find a value in a linked list without extra indexing.

You must check nodes one by one until you find the value or return to the head, so time is linear in n.

Practice

1. What distinguishes a circular singly linked list from a regular singly linked list?

easy

A. Circular lists have two pointers per node

B. The last node's next pointer points back to the head instead of None

C. Circular lists store data in reverse order

D. Each node stores a reference to both its predecessor and successor

Solution

1. Step 1: Regular linked list

   In a regular singly linked list, the last node's next is None - marking the end.

2. Step 2: Circular difference

   In a circular singly linked list, the last node's next points back to the head. There is no None terminator - traversal wraps around.

3. Final Answer:

   Last node points back to head. -> Option B

4. Quick Check:

   Circular = last.next → head (not None). [OK]

Hint: Circular = last node's next points to head, not None. [OK]

Common Mistakes:

• Confusing with doubly linked list (two pointers per node)
• Thinking circular means reverse storage
• Confusing circular with bidirectional

2. What is the time complexity of inserting a node at the end of a circular singly linked list when you maintain a tail pointer?

easy

A. O(n)

B. O(log n)

C. O(1)

D. O(n²)

Solution

1. Step 1: With tail pointer

   tail.next = new_node (new last). new_node.next = head (circular link). tail = new_node. All O(1) pointer updates.

2. Step 2: Without tail pointer

   Would need O(n) traversal to find the last node.

3. Final Answer:

   O(1) with tail pointer maintained. -> Option C

4. Quick Check:

   Tail pointer = O(1) insert at end. Without tail = O(n). [OK]

Hint: Tail pointer = O(1) end insertion. Always maintain tail for circular lists. [OK]

Common Mistakes:

• Saying O(n) because traversal is needed without tail pointer
• Not knowing tail pointer eliminates the traversal
• Confusing with insertion at arbitrary position which is O(n)

3. In Rust, why is creating a circular linked list with safe Box<T> impossible without additional indirection?

medium

A. Box<T> doesn't support linked lists

B. Box<T> implies unique ownership - a circular structure requires the last node to own the first, creating a cycle that Box cannot express

C. Rust doesn't allow struct self-reference

D. Box<T> is only for heap allocation, not pointer structures

Solution

1. Step 1: Box ownership

   Box<T> gives unique ownership of heap data. The last node would need to own the head node.

2. Step 2: Circular ownership cycle

   But the head is also owned by the list itself. Two owners of the same node = illegal in Rust. Box cannot express shared or circular ownership.

3. Step 3: Solution

   Use Rc for shared ownership, or raw pointers with unsafe, or index-based representation with Vec.

4. Final Answer:

   Box implies unique ownership - circular structure needs shared ownership (Rc) or unsafe raw pointers. -> Option B

5. Quick Check:

   Circular = shared ownership. Box = unique ownership. Mismatch. [OK]

Hint: Circular needs shared ownership. Box=unique. Use Rc> or raw pointers. [OK]

Common Mistakes:

• Thinking Box can handle any heap structure
• Not knowing Rust's ownership applies to data structure design
• Confusing Box limitations with general Rust limitations

4. How do you detect that you've completed a full traversal of a circular singly linked list?

medium

A. Check if current.next is None

B. Check if current.next points to the head node

C. Count nodes until reaching n

D. Check if current equals the tail node

Solution

1. Step 1: No None terminator

   Circular lists have no None - checking next is None never terminates traversal.

2. Step 2: Termination condition

   Start at head. Advance. Stop when current.next == head (back at start). This means we've visited all nodes exactly once.

3. Final Answer:

   Stop when current.next points to head. -> Option B

4. Quick Check:

   Circular traversal: stop when next == head, not when next is None. [OK]

Hint: Circular traversal: loop until current.next == head. Never check for None. [OK]

Common Mistakes:

• Checking for None which never occurs in circular lists
• Using a fixed count which breaks for unknown lengths
• Stopping at tail instead of checking if next == head

5. When inserting a new node at the beginning of a circular singly linked list (given head and tail), what pointer update is critical?

hard

A. Update new_node.next to None

B. Update tail.next to point to new_node (the new head)

C. Update head.next to point to new_node

D. Set tail to new_node

Solution

1. Step 1: Current state

   tail.next → head (circular link). new_node will become the new head.

2. Step 2: Required updates

   new_node.next = old_head. tail.next = new_node (maintains circular link to new head). Update head = new_node.

3. Step 3: Critical update

   tail.next must point to new_node - otherwise the circular link points to the old head, breaking the list.

4. Final Answer:

   Update tail.next to new_node to maintain the circular link. -> Option B

5. Quick Check:

   Insert at front: new.next=old_head, tail.next=new (critical!), head=new. [OK]

Hint: Insert at front: tail.next must update to new head - the circular link must be maintained. [OK]

Common Mistakes:

• Forgetting to update tail.next, breaking the circular structure
• Setting tail to new_node (tail should stay at end)
• Setting new_node.next to None instead of old head