Push Using Linked List Node in DSA Rust - Execution Trace

Concept Flow - Push Using Linked List Node

Create new node with value

↓

Set new node.next to current head

↓

Update head to new node

↓

Done

This flow shows how a new node is created and added at the start of the linked list by adjusting pointers.

Execution Sample

DSA Rust

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

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

This Rust code adds a new node with a given value at the start of the linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = None	null
2	Create new node with value 10	Node(10) -> null	new_node.next = None	10 -> null
3	Set new_node.next to head (None)	Node(10) -> null	new_node.next = None	10 -> null
4	Update head to new_node	Node(10) -> null	head = new_node	10 -> null
5	Create new node with value 20	Node(20) -> Node(10) -> null	new_node.next = head (Node(10))	20 -> 10 -> null
6	Set new_node.next to head (Node(10))	Node(20) -> Node(10) -> null	new_node.next = Node(10)	20 -> 10 -> null
7	Update head to new_node	Node(20) -> Node(10) -> null	head = new_node	20 -> 10 -> null
8	Create new node with value 30	Node(30) -> Node(20) -> Node(10) -> null	new_node.next = head (Node(20))	30 -> 20 -> 10 -> null
9	Set new_node.next to head (Node(20))	Node(30) -> Node(20) -> Node(10) -> null	new_node.next = Node(20)	30 -> 20 -> 10 -> null
10	Update head to new_node	Node(30) -> Node(20) -> Node(10) -> null	head = new_node	30 -> 20 -> 10 -> null
11	End of push operations	Node(30) -> Node(20) -> Node(10) -> null	head points to Node(30)	30 -> 20 -> 10 -> null

💡 All push operations complete, head points to newest node at list start

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	Final
head	None	Node(10)	Node(20)	Node(30)	Node(30)
new_node	None	Node(10)	Node(20)	Node(30)	None (last new_node moved to head)
new_node.next	None	None	Node(10)	Node(20)	N/A

Key Moments - 3 Insights

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

Because new_node.next must point to the current first node to keep the list connected. This is shown in steps 3, 6, and 9 where new_node.next is set before head changes (steps 4, 7, 10).

What happens if the list is empty when we push?

At step 1, head is None. When pushing the first node (step 2), new_node.next is set to None (empty list), so the new node becomes the only node, as seen in step 4.

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

Because after setting new_node.next, we update head to new_node (steps 4, 7, 10). This makes the new node the first node in the list.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What does new_node.next point to?

A None

B Node with value 20

C Node with value 10

D Node with value 30

💡 Hint

Check the 'Pointer Changes' column at step 5 in the execution table.

At which step does the head first point to a node with value 20?

A Step 2

B Step 7

C Step 4

D Step 5

💡 Hint

Look at the 'Pointer Changes' and 'Nodes in List' columns to see when head updates to Node(20).

If we skip setting new_node.next to head, what would happen to the list?

A List would have only the new node, losing previous nodes

B List would be empty

C List would have duplicate nodes

D List would be unchanged

💡 Hint

Refer to the key moment about setting new_node.next before updating head.

Concept Snapshot

Push Using Linked List Node:
- Create new node with value
- Set new_node.next to current head
- Update head to new_node
- New node becomes list start
- Preserves existing nodes by linking
- Works even if list is empty

Full Transcript

This concept shows how to add a new node at the start of a linked list. First, a new node is created with the given value. Then, the new node's next pointer is set to the current head of the list, linking it to existing nodes. Finally, the head pointer is updated to the new node, making it the first node. This process works even if the list is empty, where the new node's next is None. The execution table traces each step, showing how the list grows from empty to having nodes 10, then 20, then 30 at the front. Key moments clarify why pointer updates happen in this order to keep the list connected and correct.

Practice

1. What does the push operation do in a linked list when using a node?

easy

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

B. Removes the last node from the list

C. Searches for a node with a specific value

D. Deletes the entire list

Solution

1. Step 1: Understand push operation in linked list

   The push operation adds a new node to the linked list.

2. Step 2: Identify where the new node is added

   In a singly linked list, push usually adds the new node at the start (head) of the list.

3. Final Answer:

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

4. Quick Check:

   Push = Add at head [OK]

Hint: Push always adds node at the start of the list [OK]

Common Mistakes:

• Thinking push adds at the end
• Confusing push with pop
• Assuming push deletes nodes

2. Which of the following Rust code snippets correctly creates a new node and pushes it to the front of a linked list?

easy

A. head = Some(Node { data: 5, next: None });

B. let new_node = Node { data: 5, next: None }; head = new_node.next;

C. let new_node = Box::new(Node { data: 5, next: head }); head = Some(new_node);

D. let new_node = Box::new(Node { data: 5 }); head = new_node.next;

Solution

1. Step 1: Check node creation with Box and linking

   let new_node = Box::new(Node { data: 5, next: head }); head = Some(new_node); creates a boxed node with data 5 and next pointing to current head.

2. Step 2: Assign new node as new head

   Then head is updated to Some(new_node), correctly pushing at front.

3. Final Answer:

   let new_node = Box::new(Node { data: 5, next: head }); head = Some(new_node); -> Option C

4. Quick Check:

   Boxed node with next=head, then head=Some(new_node) [OK]

Hint: Use Box::new and set next to current head [OK]

Common Mistakes:

• Not boxing the node
• Not updating head correctly
• Setting next to None instead of head

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

struct Node {
    data: i32,
    next: Option,
}

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

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

fn main() {
    let mut head = None;
    push(&mut head, 10);
    push(&mut head, 20);
    push(&mut head, 30);
    print_list(&head);
}

medium

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

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

C. null

D. Compilation error

Solution

1. Step 1: Trace push calls and list building

   First push adds 10 as head. Second push adds 20 before 10. Third push adds 30 before 20.

2. Step 2: Print list from head

   Print starts at head (30), then 20, then 10, then null.

3. Final Answer:

   30 -> 20 -> 10 -> null -> Option B

4. Quick Check:

   Last pushed node is head, so list is 30->20->10->null [OK]

Hint: Last pushed node appears first in list [OK]

Common Mistakes:

• Assuming push adds at end
• Confusing order of nodes
• Ignoring Option and Box usage

4. Identify the error in this Rust function that tries to push a new node to the linked list head:

fn push(head: &mut Option, data: i32) {
    let new_node = Box::new(Node { data, next: head });
    *head = Some(new_node);
}

medium

A. Cannot assign &Option to next, must use head.take()

B. Missing return statement

C. Box::new cannot be used here

D. Data type i32 is incorrect

Solution

1. Step 1: Analyze next field assignment

   The next field expects Option, but head is &mut Option, a reference.

2. Step 2: Correct usage with head.take()

   Using head.take() moves the Option out, allowing ownership transfer to next.

3. Final Answer:

   Cannot assign &Option to next, must use head.take() -> Option A

4. Quick Check:

   Use head.take() to move ownership [OK]

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

Common Mistakes:

• Assigning reference instead of owned Option
• Ignoring Rust ownership rules
• Thinking Box::new is invalid here

5. Given a linked list implemented with nodes in Rust, how would you modify the push function to prevent memory leaks when repeatedly pushing nodes?

hard

A. Use clone() on nodes to duplicate data

B. Use raw pointers instead of Box to manage nodes

C. Manually call drop() on old head before pushing

D. Use head.take() to transfer ownership and avoid dangling references

Solution

1. Step 1: Understand ownership in Rust linked list

   Each node owns the next node via Box. To avoid leaks, ownership must be properly transferred.

2. Step 2: Use head.take() to move ownership safely

   head.take() replaces head with None and moves ownership to new node's next, preventing leaks.

3. Final Answer:

   Use head.take() to transfer ownership and avoid dangling references -> Option D

4. Quick Check:

   head.take() safely moves ownership, preventing leaks [OK]

Hint: Use head.take() to transfer ownership safely [OK]

Common Mistakes:

• Using raw pointers causing unsafe code
• Calling drop manually causing double free
• Cloning nodes causing unnecessary copies