Insert at Middle Specific Position in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting at middle position in a linked list

What is the printed state of the linked list after inserting value 99 at position 2?

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 append(&mut self, data: i32) {
        let new_node = Box::new(Node { data, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let new_node = Box::new(Node {
                data,
                next: self.head.take(),
            });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let new_node = Box::new(Node {
                    data,
                    next: node.next.take(),
                });
                node.next = Some(new_node);
                return;
            }
            current = node.next.as_mut();
            index += 1;
        }
    }

    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.append(10);
    list.append(20);
    list.append(30);
    list.insert_at(99, 2);
    list.print_list();
}

A 10 -> 20 -> 99 -> 30 -> null

B 10 -> 99 -> 20 -> 30 -> null

C 99 -> 10 -> 20 -> 30 -> null

D 10 -> 20 -> 30 -> 99 -> null

💡 Hint

Remember that position 2 means after the second element (0-based indexing).

The insert_at function inserts the new node after the node at position 1 (0-based). So the new node with value 99 is placed between 20 and 30.

❓ Predict Output

intermediate

Result of inserting at position beyond list length

What is the printed state of the linked list after inserting value 50 at position 5 in a list of length 3?

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 append(&mut self, data: i32) {
        let new_node = Box::new(Node { data, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let new_node = Box::new(Node {
                data,
                next: self.head.take(),
            });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let new_node = Box::new(Node {
                    data,
                    next: node.next.take(),
                });
                node.next = Some(new_node);
                return;
            }
            current = node.next.as_mut();
            index += 1;
        }
        // If position is beyond length, append at end
        self.append(data);
    }

    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.append(1);
    list.append(2);
    list.append(3);
    list.insert_at(50, 5);
    list.print_list();
}

A 1 -> 2 -> 3 -> 50 -> null

B 1 -> 2 -> 50 -> 3 -> null

C 1 -> 2 -> 3 -> null

D 50 -> 1 -> 2 -> 3 -> null

💡 Hint

If the position is beyond the list length, the new node is appended at the end.

Since position 5 is beyond the current length 3, the insert_at function appends the new node with value 50 at the end.

🔧 Debug

advanced

Identify the error in insert_at function

What error will this Rust code produce when trying to insert at position 1 in an empty list?

DSA Rust

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

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

impl LinkedList {
    fn insert_at(&mut self, data: i32, position: usize) {
        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let new_node = Box::new(Node {
                    data,
                    next: node.next.take(),
                });
                node.next = Some(new_node);
                return;
            }
            current = node.next.as_mut();
            index += 1;
        }
    }
}

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

A Compilation error due to missing head initialization

B Panic at runtime due to unwrap on None

C No error, inserts at position 1 correctly

D No insertion happens, list remains empty

💡 Hint

Check what happens when the list is empty and position is not zero.

The insert_at function does nothing if the list is empty and position is not zero, so no insertion happens and the list remains empty.

❓ Predict Output

advanced

Output after multiple insertions at middle positions

What is the printed state of the linked list after these operations? - Append 5 - Append 15 - Insert 10 at position 1 - Insert 20 at position 3

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 append(&mut self, data: i32) {
        let new_node = Box::new(Node { data, next: None });
        match self.head.as_mut() {
            None => self.head = Some(new_node),
            Some(mut node) => {
                while let Some(ref mut next_node) = node.next {
                    node = next_node;
                }
                node.next = Some(new_node);
            }
        }
    }

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let new_node = Box::new(Node {
                data,
                next: self.head.take(),
            });
            self.head = Some(new_node);
            return;
        }

        let mut current = self.head.as_mut();
        let mut index = 0;

        while let Some(node) = current {
            if index + 1 == position {
                let new_node = Box::new(Node {
                    data,
                    next: node.next.take(),
                });
                node.next = Some(new_node);
                return;
            }
            current = node.next.as_mut();
            index += 1;
        }
        self.append(data);
    }

    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.append(5);
    list.append(15);
    list.insert_at(10, 1);
    list.insert_at(20, 3);
    list.print_list();
}

A 5 -> 15 -> 10 -> 20 -> null

B 5 -> 10 -> 20 -> 15 -> null

C 5 -> 10 -> 15 -> 20 -> null

D 10 -> 5 -> 15 -> 20 -> null

💡 Hint

Insertions at position 1 and 3 place nodes between existing nodes.

Insert 10 at position 1 places it between 5 and 15. Insert 20 at position 3 places it after 15. Final list: 5 -> 10 -> 15 -> 20 -> null.

❓ Predict Output

expert

Output after inserting at middle in a doubly linked list

Given this doubly linked list code, what is the printed forward traversal after inserting 25 at position 2?

DSA Rust

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

#[derive(Debug)]
struct Node {
    data: i32,
    prev: Option<Rc<RefCell<Node>>>,
    next: Option<Rc<RefCell<Node>>>,
}

struct DoublyLinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    fn append(&mut self, data: i32) {
        let new_node = Rc::new(RefCell::new(Node { data, prev: None, next: None }));
        match self.head.clone() {
            None => self.head = Some(new_node),
            Some(head) => {
                let mut tail = head.clone();
                while let Some(next) = tail.borrow().next.clone() {
                    tail = next;
                }
                new_node.borrow_mut().prev = Some(tail.clone());
                tail.borrow_mut().next = Some(new_node);
            }
        }
    }

    fn insert_at(&mut self, data: i32, position: usize) {
        if position == 0 {
            let new_node = Rc::new(RefCell::new(Node { data, prev: None, next: self.head.clone() }));
            if let Some(old_head) = self.head.take() {
                old_head.borrow_mut().prev = Some(new_node.clone());
                self.head = Some(new_node);
            } else {
                self.head = Some(new_node);
            }
            return;
        }

        let mut current = self.head.clone();
        let mut index = 0;

        while let Some(node) = current.clone() {
            if index == position {
                let prev_node = node.borrow().prev.clone();
                let new_node = Rc::new(RefCell::new(Node { data, prev: prev_node.clone(), next: Some(node.clone()) }));
                if let Some(prev) = prev_node {
                    prev.borrow_mut().next = Some(new_node.clone());
                }
                node.borrow_mut().prev = Some(new_node);
                if position == 0 {
                    self.head = Some(new_node);
                }
                return;
            }
            current = node.borrow().next.clone();
            index += 1;
        }

        // If position is beyond length, append
        self.append(data);
    }

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

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(10);
    list.append(20);
    list.append(30);
    list.insert_at(25, 2);
    list.print_forward();
}

A 10 -> 20 -> 30 -> 25 -> null

B 10 -> 20 -> 25 -> 30 -> null

C 25 -> 10 -> 20 -> 30 -> null

D 10 -> 25 -> 20 -> 30 -> null

💡 Hint

Insertion at position 2 places the new node between nodes at positions 1 and 2.

The insert_at function inserts 25 between 20 (pos 1) and 30 (pos 2). The list becomes 10 -> 20 -> 25 -> 30 -> null.

Practice

1. What does inserting a node at a specific middle position in a linked list mean?

easy

A. Removing a node from the middle of the list

B. Adding a new node only at the start of the list

C. Adding a new node only at the end of the list

D. Adding a new node exactly between two existing nodes at a given position

Solution

1. Step 1: Understand linked list positions

   Positions in a linked list start from 1 at the head. Inserting at a middle position means placing a new node between existing nodes.

2. Step 2: Define insertion at middle

   Inserting at a specific middle position means the new node will be placed after the node at position (pos-1) and before the node at position pos.

3. Final Answer:

   Adding a new node exactly between two existing nodes at a given position -> Option D

4. Quick Check:

   Insert at middle = Add node between nodes [OK]

Hint: Middle insertion means placing node between two nodes [OK]

Common Mistakes:

• Confusing insertion with deletion
• Thinking insertion only happens at start or end
• Ignoring position indexing starting at 1

2. Which Rust code snippet correctly inserts a new node with value 10 at position 3 in a singly linked list?

easy

A. let mut current = &mut head;
for _ in 1..2 {
current = &mut current.as_mut().unwrap().next;
}
let new_node = Some(Box::new(Node { val: 10, next: current.take() }));
*current = new_node;

B. let mut current = &head;
for _ in 1..3 {
current = ¤t.unwrap().next;
}
current = Some(Box::new(Node { val: 10, next: None }));

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

D. let new_node = Node { val: 10, next: None };
head.next = Some(Box::new(new_node));

Solution

1. Step 1: Traverse to position before insertion

   The loop runs from 1 to 2 (pos-1) to reach node at position 2, using mutable references to modify links.

2. Step 2: Insert new node at position 3

   Create new node with value 10, set its next to current node's next, then update current's next to new node.

3. Final Answer:

   Code snippet in option A correctly inserts at position 3 -> Option A

4. Quick Check:

   Traverse to pos-1, link new node next to current next, update current next [OK]

Hint: Traverse to pos-1, then link new node [OK]

Common Mistakes:

• Using immutable references when mutable needed
• Incorrect loop range causing wrong position
• Not updating links properly causing list break

3. What is the output linked list after inserting value 99 at position 2 in the list 1 -> 2 -> 3 -> null using the following Rust code?

let mut head = Some(Box::new(Node { val: 1, next: Some(Box::new(Node { val: 2, next: Some(Box::new(Node { val: 3, next: None })) })) }));

let mut current = &mut head;
for _ in 1..1 {
    current = &mut current.as_mut().unwrap().next;
}
let new_node = Some(Box::new(Node { val: 99, next: current.as_mut().unwrap().next.take() }));
current.as_mut().unwrap().next = new_node;

// Print list code omitted for brevity

medium

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

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

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

D. 1 -> 2 -> 3 -> 99 -> null

Solution

1. Step 1: Traverse to node at position 1

   The loop runs from 1 to 1, which is empty, so no iteration; current points to head node with value 1.

2. Step 2: Insert new node after current

   New node with value 99 is created with next pointing to current's next (node with value 2). Then current's next is updated to new node.

3. Final Answer:

   1 -> 99 -> 2 -> 3 -> null -> Option A

4. Quick Check:

   Insert after position 1 adds 99 between 1 and 2 [OK]

Hint: Insert after pos-1 node, new node points to old next [OK]

Common Mistakes:

• Miscounting loop iterations causing wrong position
• Not updating next pointers correctly
• Confusing node values and positions

4. Identify the error in this Rust code snippet that tries to insert a node at position 2 in a singly linked list:

let mut current = &mut head;
for _ in 0..2 {
    current = &mut current.as_mut().unwrap().next;
}
let new_node = Some(Box::new(Node { val: 5, next: current.take() }));
*current = new_node;

medium

A. The code uses immutable references instead of mutable

B. The loop runs too many times, moving current past the insertion point

C. The new node's next pointer is not set correctly

D. The head pointer is not updated after insertion

Solution

1. Step 1: Analyze loop iteration count

   The loop runs from 0 to 1 (0..2), so two iterations, moving current two nodes ahead, which is past position 2.

2. Step 2: Understand insertion position

   To insert at position 2, current should point to node at position 1 (pos-1). Loop should run once, not twice.

3. Final Answer:

   The loop runs too many times, moving current past the insertion point -> Option B

4. Quick Check:

   Loop count must be pos-1 to insert correctly [OK]

Hint: Loop must run pos-1 times to reach insertion point [OK]

Common Mistakes:

• Off-by-one error in loop range
• Not using mutable references for insertion
• Incorrectly setting new node's next pointer

5. Given a singly linked list and a position that may be beyond the current list length, how should you modify the insertion logic in Rust to insert a node with value 50 at position 5 in the list 10 -> 20 -> 30 -> null?

hard

A. Return an error and do not insert if position is beyond length

B. Insert at the head regardless of position

C. Traverse until the end if position exceeds length, then insert at the end

D. Insert at position 3 instead of 5 automatically

Solution

1. Step 1: Check position against list length

   Since position 5 is beyond current length 3, traverse until the last node to insert at the end.

2. Step 2: Insert new node at end

   Once at last node, set its next pointer to new node with value 50 and next as None.

3. Final Answer:

   Traverse until the end if position exceeds length, then insert at the end -> Option C

4. Quick Check:

   Insert at end if position too large [OK]

Hint: If position too big, insert at list end [OK]

Common Mistakes:

• Crashing or panicking when position is too large
• Ignoring position and inserting at wrong place
• Not handling None next pointers properly