Creating a Singly Linked List from Scratch in DSA Rust - Visual Walkthrough

Concept Flow - Creating a Singly Linked List from Scratch

Start

↓

Create empty list with head = None

↓

Create new node with data

↓

Is list empty?

Yes No↓

Set head = new node

↓

Set last node.next = new node

↓

Done

This flow shows how to create a singly linked list by starting empty, then adding nodes either as the head if empty or at the end by traversing.

Execution Sample

DSA Rust

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

let mut head: Option<Box<Node>> = None;
// Add node with data 10
// Add node with data 20

This code creates an empty singly linked list and adds two nodes with data 10 and 20.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize empty list	None	head = None	head -> None
2	Create node with data=10	None	new_node.next = None	head -> None
3	List empty? Yes, set head = new_node	Node(10)	head points to Node(10)	head -> Node(10) -> None
4	Create node with data=20	Node(10)	new_node.next = None	head -> Node(10) -> None
5	List empty? No, traverse to last node	Node(10)	current points to Node(10)	head -> Node(10) -> None
6	Set last node.next = new_node	Node(10) -> Node(20)	Node(10).next = Node(20)	head -> Node(10) -> Node(20) -> None
7	Done	Node(10) -> Node(20)	No pointer changes	head -> Node(10) -> Node(20) -> None

💡 All nodes added, list construction complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	Final
head	None	None	Points to Node(10)	Points to Node(10)	Points to Node(10)	Points to Node(10)
new_node	N/A	Node(10)	N/A	Node(20)	N/A	N/A
current	N/A	N/A	N/A	N/A	Points to Node(10)	N/A

Key Moments - 3 Insights

Why do we set head to new_node only when the list is empty?

Because when the list is empty (head is None), the new node becomes the first node, so head must point to it. See execution_table step 3 where head changes from None to Node(10).

Why do we traverse to the last node before adding a new node when the list is not empty?

Because in a singly linked list, we can only add at the end by finding the last node whose next is None. See execution_table step 5 where current points to Node(10) before adding Node(20).

What does new_node.next = None mean when creating a new node?

It means the new node does not point to any other node yet, so it is the last node. This is shown in steps 2 and 4 where new_node.next is None.

Visual Quiz - 3 Questions

Look at the execution_table, what does head point to after step 3?

A Node(20)

B None

C Node(10)

D New node with data 20

💡 Hint

Check the 'Pointer Changes' column in step 3 where head points to Node(10)

At which step does the list stop being empty?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'List empty?' decision and pointer changes in steps 2 and 3

If we add a third node with data=30, what will be the pointer change at the last step?

A head = Node(30)

B Node(20).next = Node(30)

C Node(10).next = Node(30)

D No pointer changes

💡 Hint

Adding at the end means last node's next points to new node, see step 6 for similar pointer change

Concept Snapshot

Creating a Singly Linked List:
- Start with head = None (empty list)
- Create new node with data and next = None
- If list empty, set head = new node
- Else, traverse to last node and set last.next = new node
- Repeat to add more nodes
- List nodes link forward only

Full Transcript

We start by creating an empty singly linked list where head points to None. When we create a new node, its next pointer is None because it does not link to any node yet. If the list is empty, we set head to this new node, making it the first node. If the list is not empty, we traverse from head to the last node, which is the node whose next pointer is None. We then set this last node's next pointer to the new node, adding it at the end. This process repeats for each new node added. The singly linked list grows by linking nodes forward only, starting from head.

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