Insert at Beginning of Doubly Linked List in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has two links: one to the next node and one to the previous node. This allows traversal in both directions.

beginner

What steps are needed to insert a new node at the beginning of a doubly linked list?

1. Create a new node with the given data.
2. Set the new node's next pointer to the current head.
3. Set the new node's previous pointer to null.
4. If the list is not empty, set the current head's previous pointer to the new node.
5. Update the head pointer to the new node.

intermediate

In Rust, why do we use Option and Rc/RefCell for doubly linked lists?

Option is used to represent nullable pointers (some or none). Rc allows multiple ownership of nodes, and RefCell allows mutable access even when nodes are shared. Together, they help manage ownership and mutability safely.

intermediate

What happens if you forget to update the previous pointer of the old head when inserting at the beginning?

The old head's previous pointer will still be null or incorrect, breaking the backward link. This can cause errors when traversing backward or modifying the list.

beginner

How do you print the state of a doubly linked list after insertion at the beginning?

Start from the head node and follow the next pointers, collecting each node's data until you reach the end (null). This shows the list from start to end.

What pointer of the new node should be set to null when inserting at the beginning?

A Both pointers

B Previous pointer

C Next pointer

D None

The new node's previous pointer should be null because it will be the first node.

Which pointer of the old head node must be updated when inserting a new node at the beginning?

A Both pointers

B Next pointer

C Previous pointer

D No pointer

The old head's previous pointer must point to the new node.

In Rust, which type helps manage multiple owners of a node in a doubly linked list?

A Rc

B Box

C Vec

D Option

Rc (Reference Counted) allows multiple owners of the same data.

What is the first step when inserting a node at the beginning of a doubly linked list?

A Update the head pointer

B Traverse the list

C Set old head's previous pointer

D Create a new node

You first create the new node with the data.

After insertion at the beginning, which node becomes the new head?

A New node

B Old head

C Last node

D Null

The new node is assigned as the new head of the list.

Explain the process of inserting a node at the beginning of a doubly linked list.

Think about how links between nodes change.

Describe how Rust's ownership and mutability rules affect implementing a doubly linked list.

Consider how Rust prevents unsafe memory access.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To remove the first node from the list

B. To add a new node at the end of the list

C. To add a new node as the first element, updating head pointer

D. To reverse the entire 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 head pointer

   The head pointer must be updated to point to this new node, making it the first element.

3. Final Answer:

   To add a new node as the first element, updating head pointer -> Option C

4. Quick Check:

   Insert at beginning = update head to new node [OK]

Hint: New node becomes head; update pointers accordingly [OK]

Common Mistakes:

• Confusing insertion at beginning with insertion at end
• Not updating the head pointer
• Not adjusting previous pointer of old head

2. Which of the following Rust code snippets correctly creates a new node and inserts it at the beginning of a doubly linked list?

easy

A. let new_node = Box::new(Node { data: val, prev: None, next: head }); head = Some(new_node);

B. let new_node = Node { data: val, prev: head, next: None }; head = Some(Box::new(new_node));

C. head = Some(Box::new(Node { data: val, prev: None, next: None }));

D. let new_node = Box::new(Node { data: val, prev: None, next: None }); tail = Some(new_node);

Solution

1. Step 1: Create new node with prev None and next as current head

   The new node's previous pointer should be None because it will be the first node. Its next pointer should point to the current head.

2. Step 2: Update head to new node

   After creating the new node, the head pointer must be updated to point to this new node.

3. Final Answer:

   let new_node = Box::new(Node { data: val, prev: None, next: head }); head = Some(new_node); -> Option A

4. Quick Check:

   New node prev None, next head, update head [OK]

Hint: Prev None, next old head, then update head [OK]

Common Mistakes:

• Setting prev to head instead of None
• Not boxing the new node
• Updating tail instead of head

3. Given the following Rust code for inserting at the beginning of a doubly linked list, what will be the printed list after insertion?

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

let mut head = Some(Box::new(Node { data: 2, prev: None, next: None }));

// Insert 1 at beginning
let new_node = Box::new(Node { data: 1, prev: None, next: head });
head = Some(new_node);

// Print list
let mut current = &head;
while let Some(node) = current {
    print!("{} -> ", node.data);
    current = &node.next;
}
print!("null");

medium

A. 1 -> 2 -> null

B. 2 -> 1 -> null

C. 1 -> null

D. 2 -> null

Solution

1. Step 1: Understand insertion

   The new node with data 1 is created with next pointing to old head (node with data 2). So list starts with 1, then 2.

2. Step 2: Trace printing loop

   Printing starts at head (1), then moves to next (2), then next is None, so ends with null.

3. Final Answer:

   1 -> 2 -> null -> Option A

4. Quick Check:

   New node at front, list prints 1 then 2 [OK]

Hint: New node points to old head; print follows next pointers [OK]

Common Mistakes:

• Confusing order of nodes after insertion
• Not updating head pointer
• Printing prev instead of next

4. Identify the error in this Rust code snippet that tries to insert a node at the beginning of a doubly linked list:

let mut head = Some(Box::new(Node { data: 3, prev: None, next: None }));
let new_node = Box::new(Node { data: 1, prev: None, next: head });
head = Some(new_node);
if let Some(ref mut old_head) = head {
    old_head.prev = Some(Box::new(Node { data: 1, prev: None, next: None }));
}

medium

A. Fails to update head pointer

B. Incorrectly creates a new node for prev instead of linking to new_node

C. Does not set new_node.next to old head

D. Uses immutable reference instead of mutable

Solution

1. Step 1: Check prev pointer update

   The code sets old_head.prev to a new node with data 1 instead of linking it to the existing new_node.

2. Step 2: Understand correct linking

   Prev pointer should point to the new_node itself, not a new separate node.

3. Final Answer:

   Incorrectly creates a new node for prev instead of linking to new_node -> Option B

4. Quick Check:

   Prev must link to new_node, not new node copy [OK]

Hint: Prev pointer links to existing node, not a new duplicate [OK]

Common Mistakes:

• Creating duplicate nodes instead of linking
• Not using mutable references for modification
• Not updating prev pointer at all

5. You have a doubly linked list with nodes containing values 3 <-> 5 <-> 7. You want to insert 1 at the beginning. Which sequence of pointer updates is correct to maintain list integrity?

hard

A. Create new node with prev old head, next old head; update head to new node

B. Create new node with prev old head, next None; set old head next to new node; update head to new node

C. Create new node with prev None, next None; update head to new node only

D. Create new node with prev None, next old head; set old head prev to new node; update head to new node

Solution

1. Step 1: Create new node with prev None and next pointing to old head

   The new node is first, so prev is None. Next points to old head (node with 3).

2. Step 2: Update old head's prev pointer to new node and head pointer to new node

   Old head's prev must point back to new node. Head pointer must be updated to new node.

3. Final Answer:

   Create new node with prev None, next old head; set old head prev to new node; update head to new node -> Option D

4. Quick Check:

   New node prev None, next old head; old head prev new node; update head [OK]

Hint: New node prev None, next old head; old head prev new node; update head [OK]

Common Mistakes:

• Setting new node prev to old head
• Not updating old head prev pointer
• Not updating head pointer