Bird
Raised Fist0
DSA Rustprogramming

Create a Circular Singly Linked List in DSA Rust

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Mental Model
A circular singly linked list is a chain of nodes where the last node points back to the first node, forming a circle.
Analogy: Imagine a group of friends holding hands in a circle, so no one is left out and you can keep going around forever.
head -> 1 -> 2 -> 3 ->
ā†‘                   ā†“
ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†ā†
Dry Run Walkthrough
Input: Create a circular singly linked list with values 1, 2, 3 in order
Goal: Build a circular list where last node points back to head, forming a loop
Step 1: Create first node with value 1; point its next to itself
head -> [1 -> head]
Why: Start the circle with one node pointing to itself
Step 2: Create second node with value 2; link first node's next to second node; second node's next points to head
head -> 1 -> [2 -> head]
Why: Add second node and keep circle intact by pointing last node back to head
Step 3: Create third node with value 3; link second node's next to third node; third node's next points to head
head -> 1 -> 2 -> [3 -> head]
Why: Add third node and complete the circle
Result: 
head -> 1 -> 2 -> 3 -> head (circle formed)
Annotated Code
DSA Rust
use std::rc::Rc;
use std::cell::RefCell;

// Define a Node struct with value and next pointer
struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
}

// Define CircularSinglyLinkedList struct with head pointer
struct CircularSinglyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

impl CircularSinglyLinkedList {
    // Create a new empty list
    fn new() -> Self {
        CircularSinglyLinkedList { head: None }
    }

    // Insert a new node at the end, maintaining circular link
    fn insert(&mut self, value: i32) {
        let new_node = Rc::new(RefCell::new(Node { value, next: None }));

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

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

        // Link last node to new node
        curr.borrow_mut().next = Some(Rc::clone(&new_node));
        // New node points to head to keep circle
        new_node.borrow_mut().next = Some(Rc::clone(head));
    }

    // Print list values once starting from head
    fn print(&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().value);
            let next = curr.borrow().next.as_ref().unwrap().clone();
            if Rc::ptr_eq(&next, head) {
                break;
            }
            curr = next;
        }
        println!("head");
    }
}

fn main() {
    let mut list = CircularSinglyLinkedList::new();
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.print();
}
if self.head.is_none() {
check if list is empty to start circle
new_node.borrow_mut().next = Some(Rc::clone(&new_node));
point new node to itself to form single-node circle
let mut curr = Rc::clone(head);
start from head to find last node
if Rc::ptr_eq(&next, head) { break; }
stop when next node is head, meaning last node found
curr.borrow_mut().next = Some(Rc::clone(&new_node));
link last node to new node
new_node.borrow_mut().next = Some(Rc::clone(head));
link new node back to head to keep circle
print!("{} -> ", curr.borrow().value);
print current node value
if Rc::ptr_eq(&next, head) { break; }
stop printing when circle completes
OutputSuccess
1 -> 2 -> 3 -> head
Complexity Analysis
Time: O(n) because inserting requires traversing the list to find the last node
Space: O(n) because each inserted value creates a new node stored in memory
vs Alternative: Compared to a singly linked list without circle, circular list requires extra step to link last node back to head, but allows continuous traversal
Edge Cases
empty list
inserting first node points it to itself to form a circle
DSA Rust
if self.head.is_none() {
single node list
new node is linked after the single node and points back to head
DSA Rust
if Rc::ptr_eq(&next, head) { break; }
When to Use This Pattern
When you need a list where you can loop endlessly without null, use a circular singly linked list to keep going around the nodes.
Common Mistakes
Mistake: Not linking the last node's next pointer back to the head, breaking the circle
Fix: Always set the new node's next to head and last node's next to new node
Mistake: Infinite loop when printing because stopping condition is missing
Fix: Stop printing when next node is head to avoid infinite loop
Summary
Creates a linked list where last node points back to the first, forming a circle.
Use when you want to cycle through elements repeatedly without end.
The key is making the last node's next pointer link back to the head node.

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard