Insert at Beginning Head Insert in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting nodes at the beginning?

Consider the Rust code below that inserts nodes at the beginning of a singly linked list. What will be the printed list after all 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_at_beginning(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

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

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

A 20 -> 30 -> 10 -> null

B 30 -> 20 -> 10 -> null

C null

D 10 -> 20 -> 30 -> null

💡 Hint

Remember, inserting at the beginning means the newest node becomes the head.

Each new node is added before the current head, so the list order is reversed from insertion order.

❓ Predict Output

intermediate

What is the head node's data after these insertions?

Given the Rust linked list code that inserts nodes at the beginning, what is the data value of the head node after inserting 5, then 15, then 25?

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_at_beginning(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }
}

fn main() {
    let mut list = LinkedList::new();
    list.insert_at_beginning(5);
    list.insert_at_beginning(15);
    list.insert_at_beginning(25);
    // What is list.head.data?
}

A 25

B 15

C 5

D None

💡 Hint

The last inserted node becomes the head.

Each insertion puts the new node at the front, so the last inserted node with data 25 is the head.

🔧 Debug

advanced

Why does this Rust code fail to compile when inserting at beginning?

This Rust code tries to insert a node at the beginning of a singly linked list but fails to compile. What is the cause?

DSA Rust

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

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

impl LinkedList {
    fn insert_at_beginning(&mut self, data: i32) {
        let new_node = Box::new(Node {
            data,
            next: self.head,
        });
        self.head = Some(new_node);
    }
}

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

A head is not mutable, causing compile error

B Box::new is not used correctly, causing memory leak

C self.head is moved without using take(), causing use after move error

D next field is not initialized, causing null pointer dereference

💡 Hint

Check how self.head is used inside insert_at_beginning.

Assigning next: self.head moves ownership of head, so self.head cannot be used again without take().

🧠 Conceptual

advanced

What is the time complexity of inserting at the beginning of a singly linked list?

When inserting a new node at the beginning (head) of a singly linked list, what is the time complexity in terms of number of nodes n?

A O(n^2) - quadratic time

B O(n) - linear time

C O(log n) - logarithmic time

D O(1) - constant time

💡 Hint

Inserting at head does not require traversal.

Insertion at the beginning only changes head pointer and new node's next, so it takes constant time.

🚀 Application

expert

After inserting 1, 2, 3 at beginning, what is the list order?

You insert nodes with values 1, then 2, then 3 at the beginning of an empty singly linked list. What is the final order of nodes when printed from head to tail?

A 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> null

C 2 -> 3 -> 1 -> null

D 1 -> 3 -> 2 -> null

💡 Hint

Each new node becomes the new head.

Inserting at beginning reverses insertion order, so last inserted node is first.

Practice

1. What does the "Insert at Beginning" operation do in a linked list?

easy

A. Adds a new node at the start of the list

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

C. Deletes the first node of the list

D. Deletes the last node of the list

Solution

1. Step 1: Understand the operation

   Inserting at the beginning means adding a new node before the current first node.

2. Step 2: Effect on linked list

   The new node becomes the head, pushing existing nodes after it.

3. Final Answer:

   Adds a new node at the start of the list -> Option A

4. Quick Check:

   Insert at beginning = Add node at start [OK]

Hint: Insert at beginning means new head node [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes
• Assuming it modifies middle nodes

2. Which of the following is the correct Rust syntax to insert a new node at the beginning of a singly linked list?

easy

A. self.head = Some(Box::new(Node { data, next: self.head.take() }));

B. self.head.push(Node { data, next: None });

C. self.head.append(Node { data, next: None });

D. self.head.insert(0, Node { data, next: None });

Solution

1. Step 1: Understand Rust linked list insertion

   In Rust, to insert at head, create a new node with next pointing to current head, then update head.

2. Step 2: Match syntax

   self.head = Some(Box::new(Node { data, next: self.head.take() })); uses Some(Box::new(Node { data, next: self.head.take() })) which correctly sets new node's next to old head.

3. Final Answer:

   self.head = Some(Box::new(Node { data, next: self.head.take() })); -> Option A

4. Quick Check:

   Rust head insert = new node points to old head [OK]

Hint: Use Some(Box::new(Node { data, next: old_head })) [OK]

Common Mistakes:

• Using push or append on Option type
• Not using Box::new for heap allocation
• Forgetting to update head pointer

3. What will be the output linked list after executing this Rust code snippet?

let mut list = LinkedList::new();
list.insert_at_beginning(10);
list.insert_at_beginning(20);
list.insert_at_beginning(30);
list.print();

Assuming print() shows nodes from head to tail.

medium

A. null -> 10 -> 20 -> 30

B. 10 -> 20 -> 30 -> null

C. 30 -> 20 -> 10 -> null

D. 20 -> 30 -> 10 -> null

Solution

1. Step 1: Trace insertions

   First insert 10 at beginning: list = 10 -> null Second insert 20 at beginning: list = 20 -> 10 -> null Third insert 30 at beginning: list = 30 -> 20 -> 10 -> null

2. Step 2: Confirm print output

   Print shows from head to tail, so output is 30 -> 20 -> 10 -> null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option C

4. Quick Check:

   Last inserted at head appears first [OK]

Hint: Last inserted at head appears first in list [OK]

Common Mistakes:

• Assuming insertion adds at tail
• Reading list backwards
• Confusing print order

4. Identify the error in this Rust code for inserting at the beginning of a linked list:

fn insert_at_beginning(&mut self, data: i32) {
    let new_node = Box::new(Node { data, next: self.head });
    self.head = Some(new_node);
}

medium

A. data type i32 is incorrect for node data

B. self.head should be cloned before assigning to next

C. Box::new cannot be used here

D. self.head is an Option and needs to be taken with .take() to move ownership

Solution

1. Step 1: Understand ownership rules

   self.head is an Option, so assigning it directly to next moves ownership, which is not allowed without .take().

2. Step 2: Correct usage

   Using self.head.take() moves ownership out safely, allowing new_node.next to own old head.

3. Final Answer:

   self.head is an Option and needs to be taken with .take() to move ownership -> Option D

4. Quick Check:

   Use .take() to move Option ownership safely [OK]

Hint: Use .take() to move Option ownership when inserting [OK]

Common Mistakes:

• Assigning Option without .take()
• Ignoring Rust ownership rules
• Using wrong data types

5. Given a Rust singly linked list, how would you modify the insert_at_beginning method to handle inserting into an empty list and a non-empty list correctly without cloning nodes?

hard

A. Check if self.head is None, then assign new node; else append at tail

B. Use self.head = Some(Box::new(Node { data, next: self.head.take() })) to move ownership safely

C. Clone the entire list before inserting the new node

D. Use unsafe pointers to bypass ownership rules

Solution

1. Step 1: Handle empty and non-empty list uniformly

   Using self.head.take() moves the current head out safely whether it is None or Some(node).

2. Step 2: Create new node with next as old head

   Assign new node as head with next pointing to old head, no cloning needed.

3. Final Answer:

   Use self.head = Some(Box::new(Node { data, next: self.head.take() })) to move ownership safely -> Option B

4. Quick Check:

   Use .take() for safe ownership transfer in insert [OK]

Hint: Use .take() to handle empty and non-empty head safely [OK]

Common Mistakes:

• Appending at tail instead of head
• Cloning nodes unnecessarily
• Using unsafe code without need