Insert at End Tail Insert in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting nodes at the tail?

Consider a singly linked list initially empty. We insert nodes with values 10, 20, and 30 at the tail in that order. What is the printed state of the list after these insertions?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn insert_tail(&mut self, value: i32) {
        let new_node = Box::new(Node { data: value, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next_node) = current.next {
                    current = next_node;
                }
                current.next = Some(new_node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.insert_tail(10);
    list.insert_tail(20);
    list.insert_tail(30);
    list.print_list();
}

A 10 -> 20 -> 30 -> null

B 30 -> 20 -> 10 -> null

C 20 -> 30 -> 10 -> null

D 10 -> 20 -> null

💡 Hint

Think about how inserting at the tail adds nodes to the end of the list.

Inserting at the tail means each new node is added after the last node. So the list grows as 10 -> 20 -> 30 -> null.

❓ Predict Output

intermediate

What is the list after inserting at tail twice with same value?

Starting with an empty singly linked list, we insert the value 5 twice at the tail. What is the printed state of the list?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn insert_tail(&mut self, value: i32) {
        let new_node = Box::new(Node { data: value, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next_node) = current.next {
                    current = next_node;
                }
                current.next = Some(new_node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.insert_tail(5);
    list.insert_tail(5);
    list.print_list();
}

A 5 -> 5 -> null

B 5 -> null

C null

D 5 -> 0 -> null

💡 Hint

Each insert at tail adds a new node at the end, even if values are the same.

Inserting 5 twice at the tail creates two nodes with value 5 linked one after another.

🔧 Debug

advanced

Why does this tail insert code cause a runtime error?

This Rust code for inserting at tail causes a runtime error (panic). What is the cause?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn insert_tail(&mut self, value: i32) {
        let new_node = Box::new(Node { data: value, next: None });
        let mut current = self.head.as_mut().unwrap();
        while current.next.is_some() {
            current = current.next.as_mut().unwrap();
        }
        current.next = Some(new_node);
    }
}

fn main() {
    let mut list = LinkedList { head: None };
    list.insert_tail(1);
}

A Infinite loop in while condition causes stack overflow

B Calling unwrap() on None when list is empty causes panic

C Missing return statement causes compile error

D new_node is not boxed properly causing type mismatch

💡 Hint

Check what happens when the list is empty and unwrap() is called.

When the list is empty, self.head is None. Calling unwrap() on None causes a panic at runtime.

🧠 Conceptual

advanced

What is the time complexity of inserting at tail in a singly linked list without tail pointer?

If a singly linked list does not maintain a tail pointer, what is the time complexity of inserting a new node at the end (tail) of the list?

A O(log n), because we use binary search to find the tail

B O(1), because insertion at tail is always constant time

C O(n), because we must traverse the entire list to find the last node

D O(n^2), because each insertion requires scanning all nodes multiple times

💡 Hint

Think about how to find the last node without a direct pointer.

Without a tail pointer, we must start at the head and move through each node until the last one, which takes O(n) time.

🚀 Application

expert

After these tail insertions, what is the list state?

Given this Rust code that inserts values 1, 2, 3, 4 at the tail of an initially empty singly linked list, what is the printed output?

DSA Rust

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

struct LinkedList {
    head: Option<Box<Node>>,
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { head: None }
    }

    fn insert_tail(&mut self, value: i32) {
        let new_node = Box::new(Node { data: value, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut current) => {
                while let Some(ref mut next_node) = current.next {
                    current = next_node;
                }
                current.next = Some(new_node);
            }
        }
    }

    fn print_list(&self) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = node.next.as_ref();
        }
        println!("null");
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.insert_tail(1);
    list.insert_tail(2);
    list.insert_tail(3);
    list.insert_tail(4);
    list.print_list();
}

A 1 -> 3 -> 2 -> 4 -> null

B 4 -> 3 -> 2 -> 1 -> null

C null

D 1 -> 2 -> 3 -> 4 -> null

💡 Hint

Inserting at tail adds nodes in the order given.

Each insert_tail adds the new node at the end, so the list prints in insertion order.

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