Dequeue Using Linked List in DSA Rust

Mental Model

A dequeue lets you add or remove items from both ends quickly using a linked list.

Analogy: Imagine a line of people where you can add or remove people from the front or the back easily without shifting everyone.

front -> [node1] -> [node2] -> [node3] -> back
↑head                         ↑tail

Dry Run Walkthrough

Input: Start with empty dequeue, then add 1 at front, add 2 at back, remove from front, add 3 at front

Goal: Show how elements are added and removed from both ends using linked list pointers

Step 1: Add 1 at front

front -> [1] -> null ← back
↑head/tail

Why: First element becomes both front and back

Step 2: Add 2 at back

front -> [1] -> [2] -> null ← back
↑head                 ↑tail

Why: Add new node after tail and update tail pointer

Step 3: Remove from front

front -> [2] -> null ← back
↑head/tail

Why: Remove head node and update head pointer

Step 4: Add 3 at front

front -> [3] -> [2] -> null ← back
↑head                 ↑tail

Why: Add new node before head and update head pointer

Result:

front -> [3] -> [2] -> null ← back

Annotated Code

DSA Rust

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

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

#[derive(Debug)]
struct Dequeue {
    head: Option<Rc<RefCell<Node>>>,
    tail: Option<Rc<RefCell<Node>>>,
}

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

    fn add_front(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: self.head.clone(), prev: None }));
        if let Some(old_head) = &self.head {
            old_head.borrow_mut().prev = Some(new_node.clone());
        } else {
            self.tail = Some(new_node.clone());
        }
        self.head = Some(new_node);
    }

    fn add_back(&mut self, val: i32) {
        let new_node = Rc::new(RefCell::new(Node { value: val, next: None, prev: self.tail.clone() }));
        if let Some(old_tail) = &self.tail {
            old_tail.borrow_mut().next = Some(new_node.clone());
        } else {
            self.head = Some(new_node.clone());
        }
        self.tail = Some(new_node);
    }

    fn remove_front(&mut self) -> Option<i32> {
        self.head.take().map(|old_head| {
            if let Some(next_node) = &old_head.borrow().next {
                next_node.borrow_mut().prev = None;
                self.head = Some(next_node.clone());
            } else {
                self.tail = None;
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().value
        })
    }

    fn remove_back(&mut self) -> Option<i32> {
        self.tail.take().map(|old_tail| {
            if let Some(prev_node) = &old_tail.borrow().prev {
                prev_node.borrow_mut().next = None;
                self.tail = Some(prev_node.clone());
            } else {
                self.head = None;
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().value
        })
    }

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

fn main() {
    let mut dq = Dequeue::new();
    dq.add_front(1);
    dq.add_back(2);
    dq.remove_front();
    dq.add_front(3);
    dq.print();
}

let new_node = Rc::new(RefCell::new(Node { value: val, next: self.head.clone(), prev: None }));

create new node pointing next to current head for add_front

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

link old head's prev to new node to maintain double links

self.head = Some(new_node);

update head pointer to new node

let new_node = Rc::new(RefCell::new(Node { value: val, next: None, prev: self.tail.clone() }));

create new node pointing prev to current tail for add_back

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

link old tail's next to new node

self.tail = Some(new_node);

update tail pointer to new node

self.head.take().map(|old_head| { ... })

remove front node and update head pointer

self.tail.take().map(|old_tail| { ... })

remove back node and update tail pointer

Output

3 -> 2 -> null

Complexity Analysis

Time: O(1) for add or remove operations because we only change pointers at ends

Space: O(n) because we store n nodes in the linked list

vs Alternative: Compared to arrays where adding/removing at front can be O(n), linked list dequeue is faster at both ends

Edge Cases

empty dequeue

add_front or add_back sets both head and tail to new node

DSA Rust

else { self.tail = Some(new_node.clone()); } in add_front

single element dequeue

removing front or back empties the dequeue by setting head and tail to None

DSA Rust

else { self.tail = None; } in remove_front

When to Use This Pattern

When you need to add or remove items from both ends efficiently, use a dequeue with a linked list to avoid shifting elements.

Common Mistakes

Mistake: Not updating both head and tail pointers when dequeue becomes empty
Fix: Set both head and tail to None when last element is removed

Mistake: Forgetting to update prev or next pointers when adding/removing nodes
Fix: Always update both next and prev links to keep list consistent

Summary

A dequeue using linked list allows adding and removing elements from both front and back efficiently.

Use it when you need fast insertions and deletions at both ends without shifting elements.

The key is to keep track of head and tail pointers and update next and prev links carefully.

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