Insert at Beginning Head Insert in DSA Rust

Mental Model

Add a new item right at the start so it becomes the first thing in the list.

Analogy: Imagine a line of people waiting. If a new person comes and stands at the very front, everyone else moves back one spot.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, insert value 0 at beginning

Goal: Add 0 at the start so the list becomes 0 -> 1 -> 2 -> 3

Step 1: Create new node with value 0

new_node[0] null

Why: We need a new node to insert at the beginning

Step 2: Set new node's next to current head (node 1)

new_node[0] -> 1 -> 2 -> 3 -> null

Why: Link new node to the existing list so it points to the old first node

Step 3: Update head to new node

head -> 0 -> 1 -> 2 -> 3 -> null

Why: Make new node the first node in the list

Result:

head -> 0 -> 1 -> 2 -> 3 -> null

Annotated Code

DSA Rust

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

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

#[derive(Debug)]
struct LinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    fn insert_at_beginning(&mut self, val: i32) {
        // create new node
        let new_node = Rc::new(RefCell::new(Node { val, next: self.head.clone() }));
        // update head to new node
        self.head = Some(new_node);
    }

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

fn main() {
    let mut list = LinkedList::new();
    // initial list 3 -> 2 -> 1 -> null
    list.insert_at_beginning(3);
    list.insert_at_beginning(2);
    list.insert_at_beginning(1);
    println!("Initial list:");
    list.print_list();

    // insert 0 at beginning
    list.insert_at_beginning(0);
    println!("After inserting 0 at beginning:");
    list.print_list();
}

let new_node = Rc::new(RefCell::new(Node { val, next: self.head.clone() }));

create new node with value and link it to current head

self.head = Some(new_node);

update head pointer to new node to insert at beginning

Output

Initial list:

1 -> 2 -> 3 -> null

After inserting 0 at beginning:

0 -> 1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(1) because we only change pointers without traversing the list

Space: O(1) because we create only one new node

vs Alternative: Compared to inserting at the end which requires O(n) traversal, inserting at beginning is faster and simpler

Edge Cases

empty list

new node becomes the head and points to null

DSA Rust

self.head = Some(new_node);

single element list

new node points to the existing single node, becoming new head

DSA Rust

let new_node = Rc::new(RefCell::new(Node { val, next: self.head.clone() }));

When to Use This Pattern

When you need to add an item quickly at the start of a list, use head insert to avoid traversing the list.

Common Mistakes

Mistake: Not updating the head pointer to the new node after insertion
Fix: Assign the new node to head after linking it to the old head

Mistake: Setting new node's next to null instead of current head
Fix: Set new node's next to the current head to keep the list connected

Summary

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

Use when you want to quickly insert without traversing the list.

The new node points to the old head, then becomes the new head.

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