Insert at Beginning Head Insert in DSA Rust - Build from Scratch

Insert at Beginning (Head Insert) in a Linked List

📖 Scenario: Imagine you are managing a list of tasks where new tasks must be added to the front of the list so they get done first.

🎯 Goal: You will build a simple linked list in Rust and learn how to insert new nodes at the beginning (head) of the list.

📋 What You'll Learn

Create a linked list node struct called Node with value and next fields

Create a linked list struct called LinkedList with a head field

Implement a method insert_at_beginning to add a new node at the start of the list

Print the list after insertions showing values connected by arrows

💡 Why This Matters

🌍 Real World

Linked lists are used in many applications where dynamic data storage is needed, such as task scheduling, undo functionality, and memory management.

💼 Career

Understanding linked lists and how to manipulate them is fundamental for software developers, especially when working with low-level data structures or optimizing performance.

1

Create Node and LinkedList structs

Create a struct called Node with a field value of type i32 and a field next of type Option>. Also create a struct called LinkedList with a field head of type Option>.

DSA Rust

# Define the Node and LinkedList structs here
# Your code here

Hint

Use Option> for the next pointer to allow for empty or next nodes.

2

Add insert_at_beginning method

Implement a method called insert_at_beginning for LinkedList that takes &mut self and a parameter value: i32. This method should create a new Node with the given value and insert it at the start of the list by updating self.head.

DSA Rust

impl LinkedList {
    // Add insert_at_beginning method here
    # Your code here
}

Hint

Use self.head.take() to move the current head into the new node's next field.

3

Add a method to print the list

Add a method called print_list for LinkedList that prints the values of the nodes in order separated by -> and ends with None. Use a variable current to traverse the list starting from self.head.as_ref().

DSA Rust

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

    // Add print_list method here
    # Your code here
}

Hint

Use while let Some(node) = current to loop through nodes and current = node.next.as_ref() to move forward.

4

Insert values and print the list

Create a mutable LinkedList called list. Insert the values 10, 20, and 30 at the beginning using insert_at_beginning. Then call print_list on list to display the final list.

DSA Rust

fn main() {
    // Create LinkedList and insert values
    # Your code here
}

Hint

Remember to create list as mutable and call insert_at_beginning three times with the values 10, 20, and 30.

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