Insert at Beginning of Doubly Linked List in DSA Rust

Mental Model

Add a new item at the start by linking it before the current first item and updating the head pointer.

Analogy: Imagine adding a new first book to a shelf where each book knows the one before and after it; you place the new book at the front and connect it to the old first book.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 0 at beginning

Goal: Add 0 at the start so the list becomes 0 ↔ 1 ↔ 2 ↔ 3

Step 1: Create new node with value 0

null ← 1 ↔ 2 ↔ 3 -> null
↑head
new_node: 0

Why: We need a new node to insert at the beginning

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

0 -> 1 ↔ 2 ↔ 3 -> null
null ← 1 ↔ 2 ↔ 3 -> null
↑head
new_node: 0 -> 1

Why: Link new node forward to old first node

Step 3: Set current head's previous pointer to new node

0 ↔ 1 ↔ 2 ↔ 3 -> null
null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head
new_node: 0 ↔ 1

Why: Link old first node back to new node

Step 4: Update head pointer to new node

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: New node is now the first node in the list

Result:

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    val: i32,
    prev: Option<Rc<RefCell<Node>>>,
    next: Option<Rc<RefCell<Node>>>,
}

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

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

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

    fn insert_at_beginning(&mut self, val: i32) {
        let new_node = Node::new(val);
        if let Some(old_head) = self.head.take() {
            new_node.borrow_mut().next = Some(old_head.clone()); // link new_node forward
            old_head.borrow_mut().prev = Some(new_node.clone()); // link old head back
            self.head = Some(new_node); // update head
        } else {
            self.head = Some(new_node); // empty list case
        }
    }

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

fn main() {
    let mut dll = DoublyLinkedList::new();
    // Create initial list 1 ↔ 2 ↔ 3
    dll.insert_at_beginning(3);
    dll.insert_at_beginning(2);
    dll.insert_at_beginning(1);
    println!("Before insertion:");
    dll.print_list();

    // Insert 0 at beginning
    dll.insert_at_beginning(0);
    println!("After insertion at beginning:");
    dll.print_list();
}

let new_node = Node::new(val);

Create new node with given value

if let Some(old_head) = self.head.take() {

Check if list is not empty and take current head

new_node.borrow_mut().next = Some(old_head.clone());

Link new node's next to old head

old_head.borrow_mut().prev = Some(new_node.clone());

Link old head's prev to new node

self.head = Some(new_node);

Update head pointer to new node

} else { self.head = Some(new_node); }

If list empty, new node becomes head

Output

Before insertion:

1 ↔ 2 ↔ 3 -> null

After insertion at beginning:

0 ↔ 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(1) because insertion at beginning only changes a few pointers without traversal

Space: O(1) because only one new node is created regardless of list size

vs Alternative: Compared to inserting at end which may require traversal O(n), this is faster and simpler

Edge Cases

Empty list

New node becomes the head with no next or prev

DSA Rust

else { self.head = Some(new_node); }

Single element list

New node links forward to old head, old head links back to new node

DSA Rust

new_node.borrow_mut().next = Some(old_head.clone());

When to Use This Pattern

When you need to add an element quickly at the start of a list with two-way links, use insert at beginning in doubly linked list for O(1) insertion.

Common Mistakes

Mistake: Forgetting to update the old head's prev pointer to the new node
Fix: Always set old_head.prev = new_node to maintain backward links

Mistake: Not updating the head pointer to the new node
Fix: Set head = new_node after linking to make new node the first

Summary

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

Use when you want fast insertion at the front without traversing the list.

The key is linking the new node forward to old head and old head back to new node, then updating head.

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