Creating a Singly Linked List from Scratch in DSA Rust - Step-by-Step

Mental Model

A singly linked list is a chain of boxes where each box holds a value and a pointer to the next box. We build it by linking boxes one after another.

Analogy: Imagine a treasure hunt where each clue points to the next clue. Each clue is a box with a message and a pointer to the next clue location.

head -> [value | next] -> [value | next] -> [value | null]
↑

Dry Run Walkthrough

Input: Create a singly linked list with values 1, 2, 3 in that order

Goal: Build a linked list where each node points to the next, ending with null

Step 1: Create first node with value 1 and next null

head -> [1 | null]
↑

Why: We start the list with the first node, which points to nothing yet

Step 2: Create second node with value 2 and next null; link first node's next to second node

head -> [1 | next] -> [2 | null]
↑

Why: Link first node to second node to extend the chain

Step 3: Create third node with value 3 and next null; link second node's next to third node

head -> [1 | next] -> [2 | next] -> [3 | null]
↑

Why: Link second node to third node to complete the list

Result:

head -> 1 -> 2 -> 3 -> null

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 a SinglyLinkedList struct with head pointer
struct SinglyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    // Append a value to the end of the list
    fn append(&mut self, value: i32) {
        let new_node = Rc::new(RefCell::new(Node { value, next: None }));

        match self.head.clone() {
            None => {
                // List empty, new node becomes head
                self.head = Some(new_node);
            }
            Some(head_node) => {
                // Traverse to the last node
                let mut current = head_node;
                loop {
                    let next_opt = current.borrow().next.clone();
                    match next_opt {
                        Some(next_node) => {
                            current = next_node;
                        }
                        None => {
                            // Found last node, link new node
                            current.borrow_mut().next = Some(new_node.clone());
                            break;
                        }
                    }
                }
            }
        }
    }

    // Print the list values
    fn print_list(&self) {
        let mut current_opt = self.head.clone();
        while let Some(current) = current_opt {
            print!("{} -> ", current.borrow().value);
            current_opt = current.borrow().next.clone();
        }
        println!("null");
    }
}

fn main() {
    let mut list = SinglyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.print_list();
}

let new_node = Rc::new(RefCell::new(Node { value, next: None }));

Create a new node with given value and no next node

match self.head.clone() {

Check if list is empty by looking at head

self.head = Some(new_node);

If empty, new node becomes head

let mut current = head_node;

Start traversal from head to find last node

let next_opt = current.borrow().next.clone();

Check next node of current to see if at end

current = next_node;

Move current forward to next node

current.borrow_mut().next = Some(new_node.clone());

Link last node's next to new node to extend list

while let Some(current) = current_opt {

Traverse list nodes to print values

print!("{} -> ", current.borrow().value);

Print current node's value

current_opt = current.borrow().next.clone();

Advance to next node

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because appending requires traversing all n nodes to find the end

Space: O(n) because each node stores one value and a pointer

vs Alternative: Compared to using a tail pointer, this approach is slower for append since it traverses the list; tail pointer allows O(1) append

Edge Cases

Empty list

The first appended node becomes the head

DSA Rust

self.head = Some(new_node);

Single element list

Appending adds a second node linked from the first

DSA Rust

current.borrow_mut().next = Some(new_node.clone());

When to Use This Pattern

When you need a simple, dynamic list where elements link one after another, reach for singly linked list creation to manage data without fixed size.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new node
Fix: Ensure to set current.borrow_mut().next = Some(new_node.clone()) when at the last node

Mistake: Not handling empty list case when head is None
Fix: Check if head is None and assign new node as head in that case

Summary

Build a chain of nodes where each node points to the next, forming a singly linked list.

Use when you want a flexible list that can grow dynamically without fixed size.

Remember the first node is the head, and each node links to the next until the end points to null.

Practice

1. What is the main purpose of a Singly Linked List in data structures?

easy

A. To store elements in a random order without any links

B. To store elements in a tree-like hierarchical structure

C. To store elements with direct access by index like an array

D. To store elements in a linear order where each element points to the next

Solution

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

   A singly linked list stores elements in nodes where each node points to the next node, forming a chain.

2. Step 2: Compare with other data structures

   Unlike arrays, singly linked lists do not provide direct index access and unlike trees, they have a single linear chain of nodes.

3. Final Answer:

   To store elements in a linear order where each element points to the next -> Option D

4. Quick Check:

   Singly Linked List = Linear chain with next pointers [OK]

Hint: Remember: singly linked list nodes point only forward [OK]

Common Mistakes:

• Confusing linked lists with arrays having direct index access
• Thinking linked lists are hierarchical like trees
• Assuming nodes can point backward in singly linked lists

2. Which of the following is the correct way to define a node struct for a singly linked list in Rust?

easy

A. struct Node { value: i32, next: &Node }

B. struct Node { value: i32, next: Node }

C. struct Node { value: i32, next: Option }

D. struct Node { value: i32, next: Vec<Node> }

Solution

1. Step 1: Understand Rust ownership and pointers

   Rust requires heap allocation for recursive types like linked lists, so Box is used to own the next node.

2. Step 2: Analyze each option

   struct Node { value: i32, next: Option } uses Option allowing for a nullable next pointer, which is correct. struct Node { value: i32, next: Node } is invalid because it causes infinite size. struct Node { value: i32, next: &Node } uses a reference without lifetime, which is invalid. struct Node { value: i32, next: Vec<Node> } uses a vector which is not suitable for singly linked list next pointer.

3. Final Answer:

   struct Node { value: i32, next: Option } -> Option C

4. Quick Check:

   Use Option for next pointer in Rust [OK]

Hint: Use Option for nullable next node in Rust [OK]

Common Mistakes:

• Using direct Node type causes infinite size error
• Using references without lifetimes for next pointer
• Using Vec<Node> instead of a single next node pointer

3. What will be the printed output after running this Rust code that creates a singly linked list with values 1, 2, 3 and prints them?

struct Node {
    value: i32,
    next: Option,
}

fn main() {
    let third = Node { value: 3, next: None };
    let second = Node { value: 2, next: Some(Box::new(third)) };
    let first = Node { value: 1, next: Some(Box::new(second)) };

    let mut current = &first;
    while let Some(ref next_node) = current.next {
        println!("{} ->", current.value);
        current = next_node;
    }
    println!("{} -> null", current.value);
}

medium

A. 1 -> 2 -> null

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

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

D. Compilation error due to borrowing

Solution

1. Step 1: Trace the linked list creation

   Nodes are created in reverse order: third (3, None), second (2, Some(third)), first (1, Some(second)). So the list is 1 -> 2 -> 3 -> null.

2. Step 2: Follow the print loop

   The loop prints current.value followed by '->' while current.next is Some. It prints 1 ->, then 2 ->, then exits loop at 3 (next is None) and prints 3 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Prints nodes in order from first to last [OK]

Hint: Trace node links from first to last for output [OK]

Common Mistakes:

• Printing nodes in reverse order by mistake
• Missing the last node print with 'null'
• Confusing Option with direct node causing errors

4. Identify the error in this Rust code snippet that tries to create a singly linked list node:

struct Node {
    value: i32,
    next: Option,
}

fn main() {
    let node1 = Node { value: 1, next: None };
    let node2 = Node { value: 2, next: node1 };
}

medium

A. next field must be Option, but node1 is Node type

B. Missing semicolon after node2 declaration

C. Cannot move node1 because it is not boxed inside Option

D. No error, code compiles fine

Solution

1. Step 1: Check the type of next field

   The next field expects an Option, but node1 is a Node, not wrapped in Box or Option.

2. Step 2: Understand Rust type requirements

   Rust requires the next pointer to be boxed and wrapped in Option to handle ownership and nullability. Directly assigning node1 causes a type mismatch.

3. Final Answer:

   next field must be Option, but node1 is Node type -> Option A

4. Quick Check:

   next must be Option not Node [OK]

Hint: Match next field type exactly: Option [OK]

Common Mistakes:

• Assigning Node directly instead of Option
• Ignoring Rust ownership rules for recursive types
• Assuming semicolon missing causes error here

5. You want to implement a method append to add a new node at the end of a singly linked list in Rust. Which approach correctly handles ownership and mutability to traverse and append the node?

hard

A. Use a mutable reference to Option and loop until next is None, then set next to Some(new_node)

B. Use an immutable reference to Node and assign next directly without mutability

C. Clone the entire list and add the new node at the front

D. Use unsafe pointers to bypass Rust ownership rules

Solution

1. Step 1: Understand Rust ownership and mutability for linked lists

   To modify the list, you need a mutable reference to the next pointer (Option) to traverse and update it safely.

2. Step 2: Analyze each option

   Use a mutable reference to Option and loop until next is None, then set next to Some(new_node) correctly uses mutable references to traverse until the end and then sets next to Some(new_node). Use an immutable reference to Node and assign next directly without mutability uses immutable reference which cannot modify. Clone the entire list and add the new node at the front clones the list which is inefficient and not appending at end. Use unsafe pointers to bypass Rust ownership rules uses unsafe code which is discouraged.

3. Final Answer:

   Use a mutable reference to Option and loop until next is None, then set next to Some(new_node) -> Option A

4. Quick Check:

   Mutable reference to next pointer needed for append [OK]

Hint: Traverse with mutable Option reference to append [OK]

Common Mistakes:

• Using immutable references preventing modification
• Trying to assign next without Option or Box
• Using unsafe code unnecessarily