Push Using Linked List Node in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the 'push' operation do in a linked list?

It adds a new node at the beginning (head) of the linked list, updating the head to this new node.

intermediate

In Rust, what is the common way to represent the next node in a singly linked list?

Using an Option type, where Box<Node> points to the next node and Option handles the end (None).

intermediate

Why do we use Box in Rust linked lists for nodes?

Box allocates data on the heap, allowing nodes to own their next node and have a fixed size pointer for recursive types.

beginner

What happens to the old head node when a new node is pushed onto the linked list?

The new node's next pointer points to the old head node, effectively placing the new node before it.

intermediate

How do you update the head of the linked list after pushing a new node in Rust?

You assign the head to Some(Box::new(new_node)) where new_node's next is the old head.

What type is typically used to represent the next node in a Rust singly linked list?

A Vec<Node>

B Option<Node>

C Node

D Option<Box<Node>>

Option> is used to represent the next node or None if it is the end.

When pushing a new node, where is it added in the linked list?

A At the beginning

B In the middle

C At the end

D It replaces the head

Push adds the new node at the beginning, updating the head pointer.

Why do linked list nodes in Rust use Box?

A To allow recursive types with heap allocation

B To store data on the stack

C To avoid ownership

D To use unsafe pointers

Box allows recursive types by allocating nodes on the heap with ownership.

What does the head pointer hold after a push operation?

A None

B The old head node

C The new node wrapped in Some(Box::new())

D A raw pointer

The head points to the new node wrapped in Some(Box::new()).

What is the next pointer of the new node after push?

A None

B Points to the old head node

C Points to itself

D Is uninitialized

The new node's next points to the old head node to maintain the list.

Explain step-by-step how the push operation works in a Rust singly linked list using Box and Option.

Think about ownership and pointers in Rust.

Describe why Rust linked lists use Option> for the next pointer instead of just Node or raw pointers.

Consider Rust's ownership and type system.

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