Insert at Beginning of Doubly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting 10 at the beginning?

Consider a doubly linked list initially containing 20 -> 30 -> null. We insert 10 at the beginning. What is the printed list?

DSA Rust

struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

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

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

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

        self.head = Some(new_node);
    }

    fn print_list(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        print!("null\n");
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.insert_at_beginning(30);
    dll.insert_at_beginning(20);
    dll.insert_at_beginning(10);
    dll.print_list();
}

A 20 -> 10 -> 30 -> null

B 30 -> 20 -> 10 -> null

C 10 -> 30 -> 20 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Remember, inserting at the beginning means the new node becomes the head.

Inserting 10 at the beginning places it before 20 and 30, so the list is 10 -> 20 -> 30 -> null.

❓ Predict Output

intermediate

What is the output after inserting 5 at the beginning of an empty list?

Start with an empty doubly linked list. Insert 5 at the beginning. What is the printed list?

DSA Rust

struct Node {
    data: i32,
    prev: Option<Box<Node>>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

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

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

    fn print_list(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        print!("null\n");
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.insert_at_beginning(5);
    dll.print_list();
}

A 5 -> null

B null

C 0 -> 5 -> null

D 5

💡 Hint

Inserting into an empty list creates a single node.

After inserting 5, the list contains one node: 5 -> null.

🔧 Debug

advanced

Why does this insert_at_beginning function cause a compile error?

This Rust code for inserting at the beginning of a doubly linked list causes a compile error. What is the cause?

DSA Rust

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

    if let Some(ref mut old_head) = new_node.next {
        old_head.prev = Some(new_node);
    }

    self.head = Some(new_node);
}

A It causes a syntax error because of missing semicolons.

B It causes a move of new_node into old_head.prev, then tries to use new_node again, causing a use-after-move error.

C It causes a type mismatch because prev expects a Box<Node> but gets an integer.

D It causes a null pointer dereference because old_head is None.

💡 Hint

Check ownership and moves in Rust when assigning new_node inside itself.

Assigning new_node into old_head.prev moves ownership, so new_node cannot be used afterward, causing a compile error.

❓ Predict Output

advanced

What is the output of this corrected insert_at_beginning function?

After fixing ownership issues, what is the printed list after inserting 40 at the beginning of 50 -> 60 -> null?

DSA Rust

struct Node {
    data: i32,
    prev: Option<*mut Node>,
    next: Option<Box<Node>>,
}

struct DoublyLinkedList {
    head: Option<Box<Node>>,
}

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

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

        if let Some(ref mut old_head) = new_node.next {
            old_head.prev = Some(&mut *new_node as *mut Node);
        }

        self.head = Some(new_node);
    }

    fn print_list(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            print!("{} -> ", node.data);
            current = &node.next;
        }
        print!("null\n");
    }
}

fn main() {
    let mut dll = DoublyLinkedList::new();
    dll.insert_at_beginning(60);
    dll.insert_at_beginning(50);
    dll.insert_at_beginning(40);
    dll.print_list();
}

A 60 -> 50 -> 40 -> null

B 50 -> 40 -> 60 -> null

C 40 -> 50 -> 60 -> null

D 40 -> 60 -> 50 -> null

💡 Hint

The new node becomes the head, so it appears first in the list.

Inserting 40 at the beginning places it before 50 and 60, so the list is 40 -> 50 -> 60 -> null.

🧠 Conceptual

expert

Why is using raw pointers (*mut Node) in Rust doubly linked lists risky?

In Rust, some doubly linked list implementations use raw pointers (*mut Node) for the prev field. Why is this approach risky?

A Raw pointers bypass Rust's safety checks, risking dangling pointers and undefined behavior if not handled carefully.

B Raw pointers cause the compiler to reject the code due to syntax errors.

C Raw pointers automatically manage memory, so they can cause memory leaks.

D Raw pointers prevent the list from being mutable.

💡 Hint

Think about Rust's safety guarantees and what raw pointers skip.

Raw pointers do not have Rust's ownership and borrowing checks, so misuse can cause unsafe memory access and bugs.

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