Create a Circular Singly Linked List in DSA Rust - Build from Scratch

Create a Circular Singly Linked List

📖 Scenario: Imagine you are building a simple music playlist app. The songs play in a loop, so after the last song, it goes back to the first song automatically. To do this, you need a circular list where the last song points back to the first.

🎯 Goal: You will create a circular singly linked list in Rust that holds three songs. Each node will have the song name and a pointer to the next song. The last song will point back to the first, making the list circular.

📋 What You'll Learn

Create a struct called Node with a song field of type String and a next field as an Option<Rc<RefCell<Node>>>.

Create three nodes with songs: "Song A", "Song B", and "Song C".

Link the nodes so that Song A points to Song B, Song B points to Song C, and Song C points back to Song A.

Print the songs in order by traversing the circular list starting from Song A, stopping after printing all three songs once.

💡 Why This Matters

🌍 Real World

Circular linked lists are used in applications where data repeats in a loop, like music playlists, round-robin scheduling, or buffering.

💼 Career

Understanding linked lists and pointers is fundamental for software developers working with low-level data structures, embedded systems, or performance-critical applications.

1

Create the Node struct and first node

Add the necessary use statements for Rc and RefCell. Create a struct called Node with a song field of type String and a next field as Option<Rc<RefCell<Node>>>. Then create a variable called song_a using Rc::new(RefCell::new(Node { ... })) with song set to "Song A" and next set to None.

DSA Rust

// Your code here

Hint

Import Rc and RefCell. Define the struct with next as Option<Rc<RefCell<Node>>>. Create song_a wrapped in Rc<RefCell<>> with song as "Song A" and next as None.

2

Create the other two nodes

Add two more variables called song_b and song_c like song_a, with song set to "Song B" and "Song C" respectively, and next set to None.

DSA Rust

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

struct Node {
    song: String,
    next: Option>>,
}

fn main() {
    let song_a = Rc::new(RefCell::new(Node {
        song: String::from("Song A"),
        next: None,
    }));
    // Your code here
}

Hint

Create song_b and song_c the same way as song_a, but with their respective song names.

3

Link the nodes to form a circular list

Now link the nodes to form the circle. Use borrow_mut() to mutate each node's next: set song_a.borrow_mut().next = Some(song_b.clone()); song_b.borrow_mut().next = Some(song_c.clone()); song_c.borrow_mut().next = Some(song_a.clone()).

DSA Rust

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

struct Node {
    song: String,
    next: Option>>,
}

fn main() {
    let song_a = Rc::new(RefCell::new(Node {
        song: String::from("Song A"),
        next: None,
    }));
    let song_b = Rc::new(RefCell::new(Node {
        song: String::from("Song B"),
        next: None,
    }));
    let song_c = Rc::new(RefCell::new(Node {
        song: String::from("Song C"),
        next: None,
    }));
    // Your code here
}

Hint

Use borrow_mut() on each song variable to set its next field to Some(... .clone()) pointing to the next song. Link back from C to A.

4

Print the songs by traversing the circular list

Write code to print the songs in order by starting from song_a and following the next pointers. Use a loop that runs exactly 3 times. Use borrow() to access song and next. Clone the Rc for the next current node.

DSA Rust

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

struct Node {
    song: String,
    next: Option>>,
}

fn main() {
    let song_a = Rc::new(RefCell::new(Node {
        song: String::from("Song A"),
        next: None,
    }));
    let song_b = Rc::new(RefCell::new(Node {
        song: String::from("Song B"),
        next: None,
    }));
    let song_c = Rc::new(RefCell::new(Node {
        song: String::from("Song C"),
        next: None,
    }));

    song_a.borrow_mut().next = Some(song_b.clone());
    song_b.borrow_mut().next = Some(song_c.clone());
    song_c.borrow_mut().next = Some(song_a.clone());
    // Your code here
}

Hint

Declare mut current = song_a.clone(). Loop 3 times: print current.borrow().song, then update current by cloning the next Rc if present.

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