Insert at End Tail Insert in DSA Rust - Execution Trace

Concept Flow - Insert at End Tail Insert

Create new node with data

↓

Is list empty?

↓

Set head = new

↓

Traverse until current.next == None

↓

Set current.next = new node

↓

Done

This flow shows how to add a new node at the end of a linked list by checking if the list is empty, then either setting the head or traversing to the last node and linking the new node.

Execution Sample

DSA Rust

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

fn insert_at_end(head: &mut Option<Box<Node>>, val: i32) {
    // Insert val at list end
}

This code inserts a new node with value val at the end of a singly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	None	new_node = Node(10, None)	∅ (empty list)
2	Check if list is empty	None	head is None	∅ (empty list)
3	Set head = new_node	Node(10)	head → new_node	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
4	Create new node with data=20	Node(10)	new_node = Node(20, None)	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
5	Check if list is empty	Node(10)	head is not None	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head
6	Traverse to last node (current = head)	Node(10)	current = head	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head/current
7	current.next is None? Yes	Node(10)	current.next = None	┌────────┐ │ data:10│ │ next:∅ │ └────────┘ head/current
8	Set current.next = new_node	Node(10) → Node(20)	current.next → new_node	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head new tail
9	Create new node with data=30	Node(10) → Node(20)	new_node = Node(30, None)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head tail
10	Traverse to last node (current = head)	Node(10) → Node(20)	current = head	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head/current tail
11	current.next is None? No (points to Node(20))	Node(10) → Node(20)	current = current.next	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
12	current.next is None? Yes	Node(10) → Node(20)	current.next = None	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head current
13	Set current.next = new_node	Node(10) → Node(20) → Node(30)	current.next → new_node	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head new tail
14	End of insertions	Node(10) → Node(20) → Node(30)	No pointer changes	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail

💡 Insertion ends after linking new node at the last node's next pointer.

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
head	None	Node(10)	Node(10)	Node(10)	Node(10)
new_node	None	Node(10)	Node(20)	Node(30)	Node(30)
current	None	None	Node(10)	Node(20)	Node(20)
list_size	0	1	2	3	3

Key Moments - 3 Insights

Why do we check if the list is empty before inserting?

Because if the list is empty (head is None), we must set head to the new node directly. This is shown in execution_table step 2 and 3 where head changes from None to the new node.

Why do we traverse until current.next is None, not current itself?

Because current.next being None means current is the last node. We want to link the new node to current.next. This is shown in steps 6-8 and 10-13 where traversal moves until current.next is None.

What happens to the old last node's next pointer when inserting?

It changes from None to point to the new node, linking the new node at the end. See pointer changes in steps 8 and 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is current.next?

A None

B Points to new node

C Points to head

D Undefined

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 7 in execution_table.

At which step does the list first have two nodes?

A Step 3

B Step 13

C Step 8

D Step 14

💡 Hint

Look at the 'Nodes in List' column in execution_table to see when it changes from one to two nodes.

If we insert a node with value 40 after step 14, what will be the new tail's data?

A 10

B 40

C 20

D 30

💡 Hint

New nodes are always inserted at the end, so the new tail will have the inserted value.

Concept Snapshot

Insert at End (Tail Insert) in Linked List:
- Create new node with data and next = None
- If list empty, set head = new node
- Else traverse to last node (current.next == None)
- Set last node's next = new node
- New node becomes new tail
- Time complexity: O(n) for singly linked list

Full Transcript

To insert a node at the end of a singly linked list, first create a new node with the given data and next pointer set to None. Check if the list is empty by seeing if head is None. If empty, set head to the new node. Otherwise, start from head and traverse nodes until you find the last node where current.next is None. Then set current.next to the new node, linking it at the end. This process is repeated for each insertion. The visual pointer diagrams show how the list grows step by step. The traversal stops at the last node before insertion. This method ensures the new node is always added at the tail of the list.

Practice

1. What does the "Insert at End (Tail Insert)" operation do in a linked list?

easy

A. Deletes the last node of the list

B. Removes the first node of the list

C. Adds a new node at the end of the list

D. Adds a new node at the beginning of the list

Solution

1. Step 1: Understand the operation name

   "Insert at End" means adding a new element at the tail (last position) of the list.

2. Step 2: Compare with other operations

   Adding at the beginning is different; removing nodes is deletion, not insertion.

3. Final Answer:

   Adds a new node at the end of the list -> Option C

4. Quick Check:

   Insert at End = Add node at tail [OK]

Hint: Tail insert always adds node at the list's end [OK]

Common Mistakes:

• Confusing insert at end with insert at beginning
• Thinking it removes nodes instead of adding
• Mixing insertion with deletion operations

2. Which of the following Rust code snippets correctly inserts a new node with value 10 at the end of a singly linked list?

easy

A. let mut current = &mut head;
while current.is_some() {
current = &mut current.as_mut().unwrap().next;
}
*current = Some(Box::new(Node { value: 10, next: None }));

B. head = Some(Box::new(Node { value: 10, next: head }));

C. head = None;

D. let mut current = &head;
while current.is_some() {
current = ¤t.unwrap().next;
}
current = Some(Box::new(Node { value: 10, next: None }));

Solution

1. Step 1: Analyze code for tail insertion

   let mut current = &mut head; while current.is_some() { current = &mut current.as_mut().unwrap().next; } *current = Some(Box::new(Node { value: 10, next: None })); traverses the list using mutable references until it finds None, then inserts the new node.

2. Step 2: Check other options for correctness

   head = Some(Box::new(Node { value: 10, next: head })); inserts at the head, not tail. head = None; clears the list. let mut current = &head; while current.is_some() { current = ¤t.unwrap().next; } current = Some(Box::new(Node { value: 10, next: None })); uses immutable references, causing compilation errors on unwrap() and rebinding, and doesn't modify the list.

3. Final Answer:

   The mutable reference traversal code correctly inserts at the end -> Option A

4. Quick Check:

   Mutable traversal + insert at None = tail insert [OK]

Hint: Use mutable references to find None and insert [OK]

Common Mistakes:

• Using immutable references when mutability is needed
• Inserting at head instead of tail
• Assigning to immutable references causing errors

3. What will be the output of the following Rust code that inserts values 1, 2, 3 at the end of an empty linked list and then prints it?

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

fn main() {
    let mut head: Option = None;
    for val in [1, 2, 3] {
        let mut current = &mut head;
        while current.is_some() {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = Some(Box::new(Node { value: val, next: None }));
    }
    let mut current = &head;
    while let Some(node) = current {
        print!("{} -> ", node.value);
        current = &node.next;
    }
    print!("null\n");
}

medium

A. 3 -> 2 -> 1 -> null

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

C. null

D. Compilation error

Solution

1. Step 1: Trace insertion loop

   The insertion loop correctly adds 1, then 2, then 3 at the tail, building 1 -> 2 -> 3 -> None.

2. Step 2: Trace print loop

   The print loop uses `let mut current = &head;` and `while let Some(node) = current` which causes a type mismatch because `current` is a reference to an Option, not an Option itself. To fix this, the code should use `current = current.as_ref().map(|node| &node.next)` or `while let Some(node) = current.as_ref()` to correctly traverse the list immutably. However, as given, the code will not compile due to this mismatch.

3. Step 3: Correction

   Assuming the print loop is fixed to use `while let Some(node) = current.as_ref()`, the output will be `1 -> 2 -> 3 -> null`.

4. Final Answer:

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

5. Quick Check:

   Tail insertion preserves order; print loop needs as_ref() for immutable traversal [OK]

Hint: Use `as_ref()` chain for immutable print traversal [OK]

Common Mistakes:

• Type mismatch between `&Option` and `Option` in pattern matching
• Forgetting `as_ref()` for immutable list traversal
• Confusing head insertion (reverses order) with tail insertion

4. The following Rust code tries to insert a new node with value 5 at the end of a linked list but causes a compilation error. What is the error?

let mut current = &head;
while current.is_some() {
    current = ¤t.unwrap().next;
}
*current = Some(Box::new(Node { value: 5, next: None }));

medium

A. Cannot assign to `*current` because `current` is an immutable reference

B. `unwrap()` called on None value causing panic

C. Missing semicolon after assignment

D. Node struct is not defined

Solution

1. Step 1: Identify reference mutability

   Variable `current` is an immutable reference to `head`, so `*current = ...` is invalid.

2. Step 2: Understand Rust's mutability rules

   To modify the list, `current` must be a mutable reference (`&mut`).

3. Final Answer:

   Cannot assign to `*current` because `current` is an immutable reference -> Option A

4. Quick Check:

   Mutable reference needed for assignment [OK]

Hint: Use &mut references to modify linked list nodes [OK]

Common Mistakes:

• Using immutable references when mutability is required
• Ignoring Rust's ownership and borrowing rules
• Assuming unwrap causes error here instead of mutability

5. Given a singly linked list in Rust, how would you modify the tail insert function to handle the edge case when the list is initially empty?

hard

A. Replace head with new node regardless of current list state

B. Always traverse the list without checking head, insert at the end

C. Use recursion to insert node at the beginning

D. Check if head is None, then assign new node directly to head; else traverse to tail and insert

Solution

1. Step 1: Handle empty list case

   If head is None, assign the new node directly to head to start the list.

2. Step 2: Handle non-empty list case

   If head exists, traverse to the last node and insert the new node at the end.

3. Final Answer:

   Check if head is None, then assign new node directly to head; else traverse to tail and insert -> Option D

4. Quick Check:

   Empty list needs direct head assignment [OK]

Hint: Always check if list is empty before tail insert [OK]

Common Mistakes:

• Not checking for empty list causing panic
• Overwriting head without condition
• Using recursion incorrectly for tail insertion