Insert at Beginning of Doubly Linked List in DSA Rust - Build from Scratch

Insert at Beginning of Doubly Linked List

📖 Scenario: You are building a simple contact list app. Each contact is stored in a doubly linked list node with a name. You want to add new contacts at the beginning of the list so the newest contact appears first.

🎯 Goal: Build a doubly linked list in Rust and insert a new node at the beginning. Then print the list from head to tail showing all contact names.

📋 What You'll Learn

Define a struct Node with fields name: String, prev: Option>, and next: Option>

Create a variable head that points to the start of the list

Write a function insert_at_beginning that takes head and a String name and inserts a new node at the start

Print the list from head to tail showing the names separated by -> and ending with null

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players to move forward and backward between songs, in browsers to navigate back and forth between pages, and in many apps that require flexible data insertion and deletion.

💼 Career

Understanding linked lists is fundamental for software developers. It helps in writing efficient code for memory management, implementing complex data structures, and solving algorithmic problems.

1

Define the Node struct and create initial list

Define a struct called Node with fields name: String, prev: Option>, and next: Option>. Then create a variable head that points to a single node with name "Alice" and both prev and next set to None.

DSA Rust

struct Node {
    // Your code here
}

fn main() {
    // Your code here
}

Hint

Use struct to define Node. Use Option> for prev and next to allow links or no links.

2

Add a helper function to insert at beginning

Create a function called insert_at_beginning that takes two parameters: head: Option> and name: String. Inside the function, create a new node with name, prev set to None, and next set to the current head. Return the new node wrapped in Some.

DSA Rust

struct Node {
    name: String,
    prev: Option>,
    next: Option>,
}

fn insert_at_beginning(head: Option>, name: String) -> Option> {
    // Your code here
}

fn main() {
    let head = Box::new(Node {
        name: String::from("Alice"),
        prev: None,
        next: None,
    });
}

Hint

Create a new Node with name, prev as None, and next as the current head. Return it wrapped in Some.

3

Update the head by inserting a new node at the beginning

In main, create a variable head_option of type Option> and set it to Some(head). Then call insert_at_beginning with head_option and String::from("Bob"), and assign the result back to head_option.

DSA Rust

struct Node {
    name: String,
    prev: Option>,
    next: Option>,
}

fn insert_at_beginning(head: Option>, name: String) -> Option> {
    let new_node = Box::new(Node {
        name,
        prev: None,
        next: head,
    });
    Some(new_node)
}

fn main() {
    let head = Box::new(Node {
        name: String::from("Alice"),
        prev: None,
        next: None,
    });
    // Your code here
}

Hint

Wrap head in Some to create head_option. Then call insert_at_beginning with head_option and "Bob".

4

Print the list from head to tail

Write a while loop to print the names of nodes starting from head_option. Use a variable current initialized to head_option.as_ref(). In each loop, print current.unwrap().name followed by -> . Then update current to current.unwrap().next.as_ref(). After the loop, print null.

DSA Rust

Hint

Use while let Some(node) = current to loop through nodes. Print each node.name followed by -> . After the loop, print null.

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