Insert at Beginning Head Insert in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does 'Insert at Beginning' mean in a linked list?

It means adding a new node at the start (head) of the linked list, making it the first element.

beginner

Why is inserting at the beginning of a linked list efficient?

Because it only requires changing the head pointer and the new node's next pointer, so it runs in constant time O(1).

intermediate

In Rust, what is the role of Box in a linked list node?

Box is used to allocate nodes on the heap, allowing recursive data structures like linked lists to own their next nodes safely.

beginner

What happens to the old head node when a new node is inserted at the beginning?

The new node's next pointer points to the old head node, and the head pointer updates to the new node.

intermediate

Show the Rust code snippet to insert a new value at the beginning of a singly linked list.

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

What is the time complexity of inserting a node at the beginning of a singly linked list?

A O(n)

B O(1)

C O(log n)

D O(n^2)

Inserting at the beginning only changes the head pointer and the new node's next pointer, so it takes constant time O(1).

In Rust, which keyword is used to create a heap-allocated node for a linked list?

A Box

B Vec

C Rc

D RefCell

Box allocates data on the heap and is commonly used for linked list nodes to enable recursive structures.

When inserting at the beginning, what does the new node's next pointer point to?

A The old head node

B Null

C The tail node

D Itself

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

What happens to the head pointer after inserting a new node at the beginning?

A It points to the tail node

B It remains unchanged

C It points to the new node

D It becomes null

The head pointer updates to point to the newly inserted node.

Which of these is NOT needed when inserting at the beginning of a linked list?

A Creating a new node

B Setting the new node's next pointer

C Updating the head pointer

D Traversing the entire list

Traversing the list is not needed because insertion happens at the head directly.

Explain step-by-step how to insert a new node at the beginning of a singly linked list.

Think about what happens to the head pointer and the new node's next pointer.

Describe how Rust's ownership and Box help in implementing a linked list with head insertion.

Consider how Rust prevents dangling pointers and manages recursive structures.

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