Doubly Linked List Structure and Node Design in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting nodes in a doubly linked list

What is the printed state of the doubly linked list after inserting nodes with values 10, 20, and 30 at the end?

DSA Rust

struct Node {
    value: 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, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;
        match self.tail {
            Some(tail_ptr) => unsafe {
                (*tail_ptr).next = Some(new_node);
                new_node.prev = Some(Box::from_raw(tail_ptr));
                self.tail = Some(raw_node);
            },
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
        }
    }

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

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

A 10 <-> 20 <-> 30 <-> null

B 30 <-> 20 <-> 10 <-> null

C 10 <-> 20 <-> null

D null

💡 Hint

Think about how nodes are linked when appended at the end.

Appending nodes adds them to the end, so the list prints in insertion order: 10, then 20, then 30.

❓ Predict Output

intermediate

Output after deleting the head node in a doubly linked list

Given a doubly linked list with nodes 5 <-> 15 <-> 25 <-> null, what is the printed state after deleting the head node?

DSA Rust

struct Node {
    value: 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, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;
        match self.tail {
            Some(tail_ptr) => unsafe {
                (*tail_ptr).next = Some(new_node);
                new_node.prev = Some(Box::from_raw(tail_ptr));
                self.tail = Some(raw_node);
            },
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
        }
    }

    fn delete_head(&mut self) {
        if let Some(mut old_head) = self.head.take() {
            self.head = old_head.next.take();
            if let Some(ref mut new_head) = self.head {
                new_head.prev = None;
            } else {
                self.tail = None;
            }
        }
    }

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

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(5);
    list.append(15);
    list.append(25);
    list.delete_head();
    list.print_forward();
}

A 15 <-> 25 <-> null

B 5 <-> 15 <-> 25 <-> null

C 25 <-> null

D null

💡 Hint

Deleting the head removes the first node and updates the head pointer.

After deleting the head (5), the new head is 15, so the list is 15 <-> 25 <-> null.

🔧 Debug

advanced

Identify the bug in the doubly linked list append method

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

DSA Rust

fn append(&mut self, val: i32) {
    let mut new_node = Box::new(Node { value: val, prev: None, next: None });
    match self.tail.take() {
        Some(mut old_tail) => {
            old_tail.next = Some(new_node);
            new_node.prev = Some(old_tail);
            self.tail = Some(new_node);
        }
        None => {
            self.head = Some(new_node);
            self.tail = self.head.clone();
        }
    }
}

A Runtime panic due to null pointer dereference

B Compile-time error due to moving 'old_tail' and then using it again

C Logical error: list will be reversed after multiple appends

D No error, code runs correctly

💡 Hint

Consider ownership and borrowing rules in Rust when moving variables.

The 'old_tail' is moved when assigned to 'new_node.prev', so using it again to set 'old_tail.next' causes a compile-time error.

❓ Predict Output

advanced

Output after reversing a doubly linked list

Given a doubly linked list with nodes 1 <-> 2 <-> 3 <-> null, what is the printed state after reversing the list?

DSA Rust

struct Node {
    value: 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, val: i32) {
        let mut new_node = Box::new(Node { value: val, prev: None, next: None });
        let raw_node: *mut _ = &mut *new_node;
        match self.tail {
            Some(tail_ptr) => unsafe {
                (*tail_ptr).next = Some(new_node);
                new_node.prev = Some(Box::from_raw(tail_ptr));
                self.tail = Some(raw_node);
            },
            None => {
                self.head = Some(new_node);
                self.tail = Some(raw_node);
            }
        }
    }

    fn reverse(&mut self) {
        let mut current = self.head.take();
        self.tail = current.as_ref().map(|node| &**node as *const Node as *mut Node);
        let mut prev = None;
        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            if let Some(ref mut next_node) = node.next {
                next_node.prev = Some(Box::new(Node {
                    value: node.value,
                    prev: None,
                    next: None,
                }));
            }
            prev = Some(node);
            current = next;
        }
        self.head = prev;
    }

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

fn main() {
    let mut list = DoublyLinkedList::new();
    list.append(1);
    list.append(2);
    list.append(3);
    list.reverse();
    list.print_forward();
}

A 1 <-> 3 <-> 2 <-> null

B 1 <-> 2 <-> 3 <-> null

C null

D 3 <-> 2 <-> 1 <-> null

💡 Hint

Reversing swaps next and prev pointers for all nodes.

Reversing the list changes the order to 3 <-> 2 <-> 1 <-> null.

🧠 Conceptual

expert

Memory safety in doubly linked list node design in Rust

Which statement best explains why using Box for both prev and next pointers in a doubly linked list can cause problems in Rust?

A Box<Node> automatically handles cyclic references safely with no leaks.

B Box<Node> cannot be used for linked lists because it does not allow mutable access.

C Box<Node> creates ownership cycles causing memory leaks because prev and next own each other.

D Box<Node> is not allowed in Rust structs due to size constraints.

💡 Hint

Think about ownership and cycles in Rust's memory model.

Using Box for both prev and next creates strong ownership cycles, preventing memory from being freed, causing leaks.

Practice

1. What is the main advantage of a doubly linked list over a singly linked list?

easy

A. It allows traversal in both forward and backward directions

B. It uses less memory per node

C. It requires fewer pointers per node

D. It can only be traversed forward

Solution

1. Step 1: Understand node pointers in doubly linked list

   A doubly linked list node has two pointers: one to the next node and one to the previous node.

2. Step 2: Compare traversal capabilities

   This allows moving forward and backward through the list, unlike singly linked lists which only allow forward traversal.

3. Final Answer:

   It allows traversal in both forward and backward directions -> Option A

4. Quick Check:

   Doubly linked list = two-way traversal [OK]

Hint: Remember: two pointers mean two directions [OK]

Common Mistakes:

• Thinking it uses less memory than singly linked list
• Assuming it only allows forward traversal
• Confusing pointer count with memory usage

2. Which of the following is the correct Rust struct definition for a doubly linked list node holding an integer value?

easy

A. struct Node { value: i32, next: Option, prev: Option<*mut Node> }

B. struct Node { value: i32, next: Option, prev: Option }

C. struct Node { value: i32, next: Option, prev: Option }

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

Solution

1. Step 1: Understand ownership and pointers in Rust doubly linked list

   Rust's ownership rules prevent two owning pointers to the same data. The next pointer can own the next node using Box, but the prev pointer must be a raw pointer or weak reference to avoid ownership conflicts.

2. Step 2: Analyze options for prev pointer

   struct Node { value: i32, next: Option, prev: Option<*mut Node> } uses Option<*mut Node> (a raw mutable pointer) for prev, which is common in unsafe doubly linked list implementations. struct Node { value: i32, next: Option, prev: Option } incorrectly uses Box for prev, causing double ownership. struct Node { value: i32, next: Option, prev: Option } uses Rc which is for shared ownership but not mutable by default. struct Node { value: i32, next: Option<Node>, prev: Option<Node> } uses Option<Node> which is invalid because Node is not sized.

3. Final Answer:

   struct Node { value: i32, next: Option, prev: Option<*mut Node> } -> Option A

4. Quick Check:

   Prev pointer = raw pointer to avoid ownership [OK]

Hint: Prev pointer often uses raw pointer in Rust doubly linked lists [OK]

Common Mistakes:

• Using Box for both next and prev causing ownership errors
• Using Rc without mutability for prev
• Trying to store Node directly without Box or pointer

3. Given the following Rust code snippet for a doubly linked list node insertion, what will be the printed output?

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

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

    second.prev = Some(&mut *first as *mut _);
    first.next = Some(second);

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

medium

A. Runtime panic due to null pointer

B. 2 -> 1

C. Compilation error due to borrowing

D. 1 -> 2

Solution

1. Step 1: Understand node creation and linking

   Two nodes are created: first with value 1, second with value 2. The second node's prev pointer is set to point to first. The first node's next pointer is set to own second.

2. Step 2: Analyze the print statement

   The print accesses first.value (1) and first.next's value (2). Since first.next is Some(second), unwrap() succeeds and prints "1 -> 2".

3. Final Answer:

   1 -> 2 -> Option D

4. Quick Check:

   First node value then next node value = 1 -> 2 [OK]

Hint: Print first node then unwrap next for correct order [OK]

Common Mistakes:

• Confusing prev pointer direction
• Expecting compilation error due to unsafe pointer
• Assuming runtime panic without dereferencing prev

4. Identify the error in this Rust doubly linked list node struct and fix it:

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

medium

A. Change next to Option for shared ownership

B. Remove prev pointer completely

C. Change prev to Option<*mut Node> to avoid double ownership

D. Use Option<Node> for both next and prev

Solution

1. Step 1: Identify ownership problem with prev pointer

   Using Box for both next and prev means both own the node, causing double ownership which Rust disallows.

2. Step 2: Fix by changing prev pointer type

   Changing prev to Option<*mut Node> uses a raw pointer, which does not own the node and avoids ownership conflicts.

3. Final Answer:

   Change prev to Option<*mut Node> to avoid double ownership -> Option C

4. Quick Check:

   Prev pointer must not own node to prevent ownership error [OK]

Hint: Prev pointer uses raw pointer to avoid ownership conflicts [OK]

Common Mistakes:

• Using Box for prev causing compile errors
• Trying to remove prev pointer losing backward traversal
• Using Option<Node> which is invalid due to size

5. You want to implement a safe doubly linked list in Rust that allows multiple owners of nodes and mutable access. Which combination of pointer types is the best design choice?

hard

A. Use raw pointers (*mut Node) for both next and prev

B. Use Rc for next and Weak for prev

C. Use Option<Node> for next and Option<Node> for prev

D. Use Box<Node> for next and Box<Node> for prev

Solution

1. Step 1: Understand ownership and mutability requirements

   Multiple owners require reference counting (Rc). Mutable access requires interior mutability (RefCell).

2. Step 2: Choose pointer types for next and prev

   Next pointer uses Rc to own and allow mutation. Prev pointer uses Weak to avoid strong reference cycles and memory leaks.

3. Final Answer:

   Use Rc for next and Weak for prev -> Option B

4. Quick Check:

   Rc + RefCell + Weak = safe mutable doubly linked list [OK]

Hint: Use Rc + RefCell for ownership and Weak for back links [OK]

Common Mistakes:

• Using Box for both pointers causing ownership errors
• Using raw pointers risking unsafe code
• Ignoring Weak to prevent reference cycles