Dequeue Using Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

What is the printed state of the dequeue after these operations?

Operations:
1. Add 10 to front
2. Add 20 to rear
3. Add 30 to front
4. Remove from rear
5. Add 40 to rear

DSA Rust

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

struct Dequeue {
    front: Option<Box<Node>>,
    rear: Option<*mut Node>,
}

impl Dequeue {
    fn new() -> Self {
        Dequeue { front: None, rear: None }
    }

    fn add_front(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, next: self.front.take(), prev: None });
        let raw_new: *mut _ = &mut *new_node;
        if let Some(old_front) = &mut new_node.next {
            old_front.prev = Some(raw_new);
        } else {
            self.rear = Some(raw_new);
        }
        self.front = Some(new_node);
    }

    fn add_rear(&mut self, val: i32) {
        let mut new_node = Box::new(Node { value: val, next: None, prev: self.rear });
        let raw_new: *mut _ = &mut *new_node;
        unsafe {
            if let Some(rear_ptr) = self.rear {
                (*rear_ptr).next = Some(new_node);
            } else {
                self.front = Some(new_node);
            }
        }
        self.rear = Some(raw_new);
    }

    fn remove_rear(&mut self) -> Option<i32> {
        unsafe {
            self.rear.map(|rear_ptr| {
                let val = (*rear_ptr).value;
                if let Some(prev_ptr) = (*rear_ptr).prev {
                    (*prev_ptr).next = None;
                    self.rear = Some(prev_ptr);
                } else {
                    self.front = None;
                    self.rear = None;
                }
                val
            })
        }
    }

    fn print_dequeue(&self) {
        let mut current = &self.front;
        let mut result = vec![];
        while let Some(node) = current {
            result.push(node.value);
            current = &node.next;
        }
        println!("{:?}", result);
    }
}

fn main() {
    let mut dq = Dequeue::new();
    dq.add_front(10);
    dq.add_rear(20);
    dq.add_front(30);
    dq.remove_rear();
    dq.add_rear(40);
    dq.print_dequeue();
}

A [30, 10, 40]

B [10, 20, 40]

C [30, 10, 20, 40]

D [10, 30, 40]

💡 Hint

Trace each operation step by step, updating the front and rear pointers.

After adding 10 front: [10]. Add 20 rear: [10, 20]. Add 30 front: [30, 10, 20]. Remove rear removes 20: [30, 10]. Add 40 rear: [30, 10, 40].

🧠 Conceptual

intermediate

Understanding Dequeue Node Links

In a doubly linked list used for a dequeue, what does the 'prev' pointer of the front node point to?

A It points to None (null).

B It points to the rear node.

C It points to the next node.

D It points to itself.

💡 Hint

Think about the start of the list and what comes before it.

The front node has no previous node, so its 'prev' pointer is None (null).

🔧 Debug

advanced

Identify the Bug in Remove Rear Method

What error will occur when running the remove_rear method if the dequeue has only one node?

DSA Rust

fn remove_rear(&mut self) -> Option<i32> {
    unsafe {
        self.rear.map(|rear_ptr| {
            let val = (*rear_ptr).value;
            if let Some(prev_ptr) = (*rear_ptr).prev {
                (*prev_ptr).next = None;
                self.rear = Some(prev_ptr);
            } else {
                self.front = None;
                self.rear = None;
            }
            val
        })
    }
}

A Dereferencing a null pointer causing a segmentation fault.

B No error, works correctly.

C Use of dangling pointer after setting front to None.

D Double free error due to improper memory handling.

💡 Hint

Check the condition when prev_ptr is None.

When there is only one node, prev_ptr is None, so front and rear are set to None safely. No error occurs.

❓ Predict Output

advanced

Result After Mixed Add and Remove Operations

What is the printed state of the dequeue after these operations?

Operations:
1. Add 5 to rear
2. Add 15 to rear
3. Add 25 to front
4. Remove rear
5. Remove front
6. Add 35 to front

DSA Rust

fn main() {
    let mut dq = Dequeue::new();
    dq.add_rear(5);
    dq.add_rear(15);
    dq.add_front(25);
    dq.remove_rear();
    dq.remove_front();
    dq.add_front(35);
    dq.print_dequeue();
}

A [35, 15]

B [25, 5]

C [5, 15]

D [35, 5]

💡 Hint

Track the list after each operation carefully.

Add rear 5: [5]. Add rear 15: [5, 15]. Add front 25: [25, 5, 15]. Remove rear removes 15: [25, 5]. Remove front removes 25: [5]. Add front 35: [35, 5].

🧠 Conceptual

expert

Why Use Doubly Linked List for Dequeue?

Why is a doubly linked list preferred over a singly linked list for implementing a dequeue?

A Because it only allows adding elements at the rear.

B Because it uses less memory than singly linked list.

C Because it allows adding and removing elements from both ends efficiently.

D Because it does not require pointers.

💡 Hint

Think about operations at both front and rear ends.

A doubly linked list has pointers to both next and previous nodes, enabling efficient insertions and deletions at both ends, which is essential for dequeue.

Practice

1. What is the main advantage of using a linked list to implement a dequeue compared to an array?

easy

A. It uses less memory than an array for the same number of elements.

B. It automatically sorts the elements when inserted.

C. It allows insertion and deletion from both ends in constant time without shifting elements.

D. It prevents duplicate elements from being added.

Solution

1. Step 1: Understand dequeue operations

   A dequeue allows insertion and deletion at both front and rear ends.

2. Step 2: Compare linked list and array

   Linked list supports these operations in constant time without shifting elements, unlike arrays.

3. Final Answer:

   It allows insertion and deletion from both ends in constant time without shifting elements. -> Option C

4. Quick Check:

   Linked list dequeue = fast insert/delete both ends [OK]

Hint: Linked list avoids shifting elements for front/rear operations [OK]

Common Mistakes:

• Thinking arrays handle front insertions efficiently
• Assuming linked list sorts elements automatically
• Confusing memory usage advantages

2. Which of the following Rust code snippets correctly defines a node struct for a doubly linked list used in a dequeue?

easy

A. struct Node<T> { data: T, prev: Option>, next: Option> }

B. struct Node<T> { data: T, prev: Option>>, next: Option>> }

C. struct Node<T> { data: T, prev: Option<*mut Node<T>>, next: Option<*mut Node<T>> }

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

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust needs smart pointers like Rc and RefCell for shared mutable ownership in doubly linked lists.

2. Step 2: Analyze options

   struct Node<T> { data: T, prev: Option>>, next: Option>> } uses Rc> for prev and next, allowing multiple owners and mutability safely.

3. Final Answer:

   struct Node<T> { data: T, prev: Option>>, next: Option>> } -> Option B

4. Quick Check:

   Use Rc<RefCell> for safe shared mutable nodes [OK]

Hint: Use Rc<RefCell> for doubly linked list nodes in Rust [OK]

Common Mistakes:

• Using Box alone causes ownership errors
• Using raw pointers without unsafe blocks
• Mixing Box and Rc incorrectly

3. Given the following Rust code for a dequeue implemented with a linked list, what will be printed after these operations?

let mut dq = Dequeue::new();
dq.push_front(10);
dq.push_rear(20);
dq.push_front(5);
dq.pop_rear();
dq.display();

medium

A. 5 -> 20 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> 5 -> null

D. 5 -> 10 -> null

Solution

1. Step 1: Trace insertions

   push_front(10) adds 10 at front: 10 -> null; push_rear(20) adds 20 at rear: 10 -> 20 -> null; push_front(5) adds 5 at front: 5 -> 10 -> 20 -> null.

2. Step 2: Trace pop_rear and display

   pop_rear() removes 20 from rear: 5 -> 10 -> null; display prints this sequence.

3. Final Answer:

   5 -> 10 -> null -> Option D

4. Quick Check:

   After pop_rear, rear 20 removed, list is 5 -> 10 [OK]

Hint: Track front/rear insertions and removals stepwise [OK]

Common Mistakes:

• Confusing push_front and push_rear order
• Forgetting pop_rear removes last element
• Printing outdated list state

4. The following Rust code for a dequeue using a linked list causes a runtime panic. What is the most likely cause?

fn pop_front(&mut self) -> Option<T> {
    let node = self.head.take().unwrap();
    self.head = node.next;
    Some(node.data)
}

medium

A. Calling unwrap() on null when dequeue is empty.

B. Incorrectly updating self.head with node.next which is a Box, not Option.

C. Not updating the tail pointer after popping front.

D. Returning node.data without cloning or moving.

Solution

1. Step 1: Analyze unwrap() usage

   unwrap() on self.head.take() will panic if self.head is null (empty dequeue).

2. Step 2: Understand runtime panic cause

   If dequeue is empty, calling pop_front causes unwrap() on null, triggering panic.

3. Final Answer:

   Calling unwrap() on null when dequeue is empty. -> Option A

4. Quick Check:

   unwrap() on null causes panic [OK]

Hint: Check unwrap() calls on possibly empty dequeue [OK]

Common Mistakes:

• Ignoring empty dequeue before unwrap()
• Assuming node.next is not Option
• Forgetting to update tail pointer

5. You want to implement a dequeue using a linked list in Rust that supports fast insertion and deletion at both ends and also allows iteration from front to rear. Which combination of Rust smart pointers and traits is best suited for this?

hard

A. Use Rc> for nodes and implement Iterator trait for traversal.

B. Use Box for nodes and implement Copy trait for traversal.

C. Use raw pointers (*mut Node<T>) for nodes and implement Drop trait for traversal.

D. Use Arc> for nodes and implement Send trait for traversal.

Solution

1. Step 1: Choose smart pointers for shared mutable ownership

   Rc> allows multiple owners and interior mutability needed for doubly linked list nodes.

2. Step 2: Implement Iterator trait for front-to-rear traversal

   Implementing Iterator trait enables easy iteration over dequeue elements from front to rear.

3. Final Answer:

   Use Rc> for nodes and implement Iterator trait for traversal. -> Option A

4. Quick Check:

   Rc<RefCell> + Iterator = safe mutable nodes + easy traversal [OK]

Hint: Combine Rc<RefCell> with Iterator for safe mutable traversal [OK]

Common Mistakes:

• Using Box alone prevents multiple ownership
• Raw pointers require unsafe code
• Arc<Mutex> is for concurrency, not needed here