Create and Initialize Doubly Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Doubly Linked List after Insertions

What is the printed state of the doubly linked list after inserting 10, 20, and 30 in order?

DSA Rust

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

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

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                if let Some(ref mut next_node) = (*tail).next {
                    next_node.prev = Some(Box::from_raw(tail));
                }
                self.tail = Some(raw_node);
            },
        }
    }

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

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(10);
    list.append(20);
    list.append(30);
    list.print_forward();
}

A 10 -> 20 -> null

B 30 -> 20 -> 10 -> null

C 10 -> 20 -> 30 -> null

D 20 -> 30 -> 10 -> null

💡 Hint

Think about the order in which elements are appended to the list.

The append method adds nodes at the end. So the list prints in the order 10, then 20, then 30.

❓ Predict Output

intermediate

Value of head node after initialization

What is the value of the head node's data after creating a doubly linked list and inserting only one element 42?

DSA Rust

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

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

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                if let Some(ref mut next_node) = (*tail).next {
                    next_node.prev = Some(Box::from_raw(tail));
                }
                self.tail = Some(raw_node);
            },
        }
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(42);
    if let Some(ref head_node) = list.head {
        println!("{}", head_node.data);
    }
}

A 42

B Compilation error

C None

D 0

💡 Hint

The first inserted node becomes the head.

After inserting 42, the head node stores 42 as its data.

🔧 Debug

advanced

Identify the runtime error in doubly linked list append method

What runtime error will occur when running this append method in the doubly linked list implementation?

DSA Rust

fn append(&mut self, data: i32) {
    let mut new_node = Box::new(Node { data, prev: None, next: None });
    let raw_node: *mut _ = &mut *new_node;

    match self.tail {
        None => {
            self.head = Some(new_node);
            self.tail = Some(raw_node);
        }
        Some(tail) => unsafe {
            (*tail).next = Some(new_node);
            if let Some(ref mut next_node) = (*tail).next {
                next_node.prev = Some(Box::from_raw(tail));
            }
            self.tail = Some(raw_node);
        },
    }
}

A Use after free (dangling pointer) due to Box::from_raw on tail

B Stack overflow due to infinite recursion

C No error, runs correctly

D Compilation error due to mutable borrow

💡 Hint

Look at how Box::from_raw is used on a pointer already owned elsewhere.

Using Box::from_raw on a pointer that is still owned causes double free or use after free errors at runtime.

🧠 Conceptual

advanced

Why use Option> for prev and next in doubly linked list?

Why do we use Option> for the prev and next pointers in a doubly linked list node in Rust?

A To store multiple nodes in a single prev or next field

B To avoid using pointers and use only values for prev and next

C To make the list immutable and thread-safe

D To allow nodes to optionally point to other nodes or None, enabling list ends

💡 Hint

Think about what happens at the start and end of the list.

Option> allows prev and next to be None when there is no previous or next node, such as at the list ends.

🚀 Application

expert

Resulting list after mixed insertions and deletions

Given a doubly linked list initially empty, perform these operations in order: append 5, append 10, append 15, remove head, append 20. What is the final list printed forward?

DSA Rust

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

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

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

    fn append(&mut self, data: i32) {
        let mut new_node = Box::new(Node { data, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;

        match self.tail {
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
            Some(tail) => unsafe {
                (*tail).next = Some(new_node);
                self.tail = Some(raw_node);
            },
        }
    }

    fn remove_head(&mut self) {
        if let Some(mut old_head) = self.head.take() {
            self.head = old_head.next.take();
            if self.head.is_none() {
                self.tail = None;
            }
        }
    }

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

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(5);
    list.append(10);
    list.append(15);
    list.remove_head();
    list.append(20);
    list.print_forward();
}

A 5 -> 10 -> 15 -> 20 -> null

B 10 -> 15 -> 20 -> null

C 15 -> 20 -> null

D 20 -> null

💡 Hint

Removing head removes the first element, then appending adds at the end.

After removing head (5), the list starts at 10, then 15, then appending 20 adds at the end.

Practice

1. What is the main purpose of a doubly linked list in data structures?

easy

A. To allow traversal in both forward and backward directions

B. To store data in a fixed-size array

C. To sort elements automatically

D. To prevent duplicate values

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes with pointers to both previous and next nodes.

2. Step 2: Identify traversal capability

   This structure allows moving forward and backward through the list easily.

3. Final Answer:

   To allow traversal in both forward and backward directions -> Option A

4. Quick Check:

   Doubly linked list traversal = forward and backward [OK]

Hint: Remember: double links mean two-way movement [OK]

Common Mistakes:

• Confusing doubly linked list with arrays
• Thinking it sorts data automatically
• Assuming it prevents duplicates

2. Which Rust code snippet correctly defines a node struct for a doubly linked list?

easy

A. struct Node { data: i32, next: Node, prev: Node }

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

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

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

Solution

1. Step 1: Understand Rust ownership and pointers

   Rust uses Option for next to allow nullable ownership and *mut Node for raw pointer prev.

2. Step 2: Check each option for correctness

   struct Node { data: i32, next: Option, prev: Option<*mut Node> } uses Option for next and Option<*mut Node> for prev, which is correct for doubly linked list nodes in Rust.

3. Final Answer:

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

4. Quick Check:

   Rust doubly linked list node = Option<Box> + raw pointer [OK]

Hint: Use Option<Box> for next and raw pointer for prev in Rust [OK]

Common Mistakes:

• Using direct Node type causing infinite size error
• Using Box<Node> for prev causing ownership issues
• Not using Option to allow null pointers

3. What will be the output after running this Rust code that creates a doubly linked list with nodes 1 and 2?

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

fn main() {
    let mut first = Box::new(Node { data: 1, next: None, prev: None });
    let mut second = Box::new(Node { data: 2, next: None, prev: None });

    first.next = Some(second);
    // Set prev pointer
    if let Some(ref mut next_node) = first.next {
        next_node.prev = Some(&mut *first as *mut Node);
    }

    println!("{} -> {} -> null", first.data, first.next.as_ref().unwrap().data);
}

medium

A. 1 -> 2 -> null

B. 2 -> 1 -> null

C. Compilation error due to ownership

D. Runtime panic due to null pointer

Solution

1. Step 1: Analyze node creation and linking

   Two nodes created: first with data 1, second with data 2. first.next points to second, second.prev points back to first.

2. Step 2: Understand ownership rules in Rust

   Assigning first.next = Some(second) moves ownership of second into first.next. However, second is moved and cannot be used after. Also, setting next_node.prev = Some(&mut *first as *mut Node) involves mutable borrow of first while first is already borrowed mutably, causing ownership conflict.

3. Step 3: Compilation error due to ownership and borrowing rules

   The code will not compile due to ownership and borrowing errors.

4. Final Answer:

   Compilation error due to ownership -> Option C

5. Quick Check:

   Rust ownership rules prevent multiple mutable borrows [OK]

Hint: Rust ownership rules prevent multiple mutable borrows [OK]

Common Mistakes:

• Confusing order of nodes in print
• Ignoring unsafe pointer usage
• Assuming compilation error without checking code

4. Identify the error in this Rust code snippet that tries to initialize a doubly linked list node:

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

fn main() {
    let mut node = Node { data: 10, next: None, prev: None };
    node.prev = Some(&mut node);
}

medium

A. Cannot assign reference to raw pointer without unsafe block

B. Missing lifetime annotation for prev pointer

C. Cannot borrow `node` as mutable more than once

D. No error, code runs fine

Solution

1. Step 1: Understand raw pointer assignment in Rust

   Assigning a reference (&mut node) to a raw pointer field (prev) requires an unsafe block because raw pointer dereferencing and assignment are unsafe operations.

2. Step 2: Identify missing unsafe block

   The code attempts to assign &mut node to prev without an unsafe block, causing a compilation error.

3. Final Answer:

   Cannot assign reference to raw pointer without unsafe block -> Option A

4. Quick Check:

   Raw pointer assignments require unsafe block in Rust [OK]

Hint: Use unsafe block when assigning raw pointers [OK]

Common Mistakes:

• Ignoring unsafe requirement for raw pointers
• Thinking mutable borrow error occurs here
• Assuming code compiles without error

5. You want to create a doubly linked list in Rust that supports inserting a new node at the front. Which approach correctly initializes the new node and updates pointers?

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

fn insert_front(head: &mut Option, value: i32) {
    // Fill in the missing code here
}

hard

A. Create new node with next = None, prev = head; set head to new node without changing old head

B. Create new node with next = None, prev = None; set head to new node without linking

C. Create new node with next = head, prev = head; set head to new node

D. Create new node with next = head.take(), prev = None; if old head exists, set its prev to new node pointer; then set head to new node

Solution

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

   Use head.take() to move old head out safely and assign to new node's next; prev is None because new node is front.

2. Step 2: Update old head's prev pointer if it exists

   If old head exists, set its prev pointer to new node's raw pointer to maintain backward link.

3. Step 3: Update head to point to new node

   Assign new node to head to complete insertion at front.

4. Final Answer:

   Create new node with next = head.take(), prev = None; if old head exists, set its prev to new node pointer; then set head to new node -> Option D

5. Quick Check:

   Insert front updates next, prev, and head correctly [OK]

Hint: Use head.take() and update old head's prev pointer [OK]

Common Mistakes:

• Not updating old head's prev pointer
• Setting prev pointer incorrectly
• Overwriting head without moving old head