Push Using Linked List Node in DSA Rust

Mental Model

Adding a new item at the start of a linked list means making it the new head and linking it to the old head.

Analogy: Imagine a line of people holding hands. To add a new person at the front, they hold the new person's hand first, then the rest follow.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, push value 0

Goal: Add a new node with value 0 at the start of the list

Step 1: Create new node with value 0

new_node(0) -> null
head -> 1 -> 2 -> 3 -> null

Why: We need a new node to add to the list

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

new_node(0) -> 1 -> 2 -> 3 -> null
head -> 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: New node becomes 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>>>,
}

impl Node {
    fn new(val: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { val, next: None }))
    }
}

struct LinkedList {
    head: Option<Rc<RefCell<Node>>>,
}

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

    fn push(&mut self, val: i32) {
        // create new node
        let new_node = Node::new(val);
        // link new node's next to current head
        new_node.borrow_mut().next = self.head.take();
        // update head to new node
        self.head = Some(new_node);
    }

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

fn main() {
    let mut list = LinkedList::new();
    // create initial list 1 -> 2 -> 3 -> null
    list.push(3);
    list.push(2);
    list.push(1);
    // push 0 at front
    list.push(0);
    list.print_list();
}

let new_node = Node::new(val);

create new node with given value

new_node.borrow_mut().next = self.head.take();

link new node's next to current head to connect to existing list

self.head = Some(new_node);

update head pointer to new node making it the first node

Output

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

Complexity Analysis

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

Space: O(1) because we add only one new node regardless of list size

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

Edge Cases

empty list

new node becomes the head and next is None

DSA Rust

new_node.borrow_mut().next = self.head.take();

When to Use This Pattern

When you need to add an element quickly at the start of a list, use push with linked list nodes to avoid traversing.

Common Mistakes

Mistake: Not updating the head pointer to the new node after linking
Fix: Assign the new node to head after setting its next pointer

Mistake: Forgetting to set new node's next to the old head, breaking the list
Fix: Always link new node's next to current head before updating head

Summary

Adds a new node at the start of a linked list by updating pointers.

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

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

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