Insert at Beginning Head Insert in DSA Rust - Execution Trace

Concept Flow - Insert at Beginning Head Insert

Create new node

↓

New node.next = current head

↓

Update head to new node

↓

Done

Insert a new node by creating it, linking it to the current head, then updating head to this new node.

Execution Sample

DSA Rust

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

fn insert_at_beginning(head: &mut Option<Box<Node>>, value: i32) {
    let new_node = Box::new(Node { data: value, next: head.take() });
    *head = Some(new_node);
}

This Rust function inserts a new node at the beginning of a singly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	∅	head = None	head → ∅
2	Create new node with data=10	Node(10)	new_node.next = None	new_node(10) → ∅
3	Set new_node.next = head (None)	Node(10)	new_node.next = None	new_node(10) → ∅
4	Update head to new_node	Node(10)	head → new_node	head → ┌────────┐ │ data:10│ │ next:∅ │ └────────┘
5	Insert new node with data=20 at beginning	Node(20) → Node(10)	new_node.next = head (Node(10))	new_node(20) → new_node(10) → ∅
6	Update head to new_node (20)	Node(20) → Node(10)	head → new_node(20)	head → ┌────────┐ ┌────────┐ │ data:20│ ──→ │ data:10│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘
7	Insert new node with data=30 at beginning	Node(30) → Node(20) → Node(10)	new_node.next = head (Node(20))	new_node(30) → new_node(20) → new_node(10) → ∅
8	Update head to new_node (30)	Node(30) → Node(20) → Node(10)	head → new_node(30)	head → ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ ──→ │ data:20│ ──→ │ data:10│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘
9	End of insertions	Node(30) → Node(20) → Node(10)	head points to Node(30)	head → ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ ──→ │ data:20│ ──→ │ data:10│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘

💡 All nodes inserted at beginning; head updated each time; list ends when no more insertions.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
head	None	None	Node(10)	Node(10)	Node(20)	Node(20)	Node(30)	Node(30)
new_node	N/A	Node(10)	N/A	Node(20)	N/A	Node(30)	N/A	N/A

Key Moments - 3 Insights

Why do we set new_node.next = head before updating head?

Because new_node must point to the current first node before head changes. See execution_table step 3 and 5 where new_node.next links to the old head.

What happens if the list is empty when inserting?

The new node's next is None, so it becomes the only node. See step 2-4 where head is None initially and after insertion points to the new node.

Why does head always point to the newest node after insertion?

Because we update head to new_node after linking. This keeps the list starting at the newest inserted node. See steps 4, 6, and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what does head point to?

A Node with data 10

B Node with data 20

C Node with data 30

D None

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6.

At which step does the list first contain two nodes?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Nodes in List' column to see when count changes from one to two.

If we insert a node with data 40 after step 8, what will head point to?

A Node with data 40

B Node with data 10

C Node with data 30

D Node with data 20

💡 Hint

Recall that head always points to the newest inserted node as shown in variable_tracker.

Concept Snapshot

Insert at Beginning (Head Insert):
- Create new node with data
- Set new_node.next to current head
- Update head to new_node
- New node becomes first in list
- Works even if list is empty
- Head always points to newest node

Full Transcript

This concept shows how to insert a new node at the beginning of a singly linked list. We create a new node, link its next pointer to the current head, then update head to this new node. This makes the new node the first element. The process works even if the list is empty, where head is None. Each insertion updates head to point to the newest node, maintaining the list order. The execution table traces each step, showing node creation, pointer updates, and the visual linked list state. Variable tracking shows how head and new_node change after each step. Key moments clarify why linking new_node.next before updating head is important, and how the list grows. The visual quiz tests understanding of pointer changes and list state at different steps.

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