Dequeue Using Linked List in DSA Rust - Build from Scratch

Dequeue Using Linked List

📖 Scenario: You are building a simple double-ended queue (dequeue) using a linked list. This data structure lets you add and remove items from both ends, like a line where people can join or leave from front or back.

🎯 Goal: Create a linked list based dequeue with basic operations to add elements at front and back, and then show the current state of the dequeue.

📋 What You'll Learn

Create a struct called Node with an integer value and optional next and previous links

Create a struct called Dequeue with optional head and tail pointers

Add a method push_front to add a node at the front

Add a method push_back to add a node at the back

Add a method print_dequeue to display all values from front to back

💡 Why This Matters

🌍 Real World

Double-ended queues are used in scheduling tasks, undo functionality, and buffering data streams where adding or removing from both ends is needed.

💼 Career

Understanding linked list based dequeue implementations helps in roles involving system programming, embedded systems, and performance-critical applications.

1

Create Node and Dequeue structs

Create a struct called Node with a field value: i32, and two optional boxed pointers next and prev of type Option>. Also create a struct called Dequeue with two optional boxed pointers head and tail of type Option>.

DSA Rust

# Define Node and Dequeue structs here
// Your code here

Hint

Use Option> for next and prev pointers to allow linking nodes.

2

Add push_front and push_back methods

Inside an impl Dequeue block, add two methods: push_front(&mut self, value: i32) and push_back(&mut self, value: i32). These methods should create a new Node with the given value and add it to the front or back of the dequeue respectively.

DSA Rust

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

struct Dequeue {
    head: Option>,
    tail: Option>,
}

impl Dequeue {
    // Add push_front and push_back methods here
    // Your code here
}

Hint

Use self.head.take() and self.tail.take() to move ownership when linking nodes.

3

Add print_dequeue method

Add a method print_dequeue(&self) inside impl Dequeue that prints all node values from head to tail separated by -> and ending with null.

DSA Rust

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

struct Dequeue {
    head: Option>,
    tail: Option>,
}

impl Dequeue {
    fn push_front(&mut self, value: i32) {
        let mut new_node = Box::new(Node {
            value,
            next: self.head.take(),
            prev: None,
        });
        if let Some(ref mut old_head) = new_node.next {
            old_head.prev = Some(new_node.clone());
        }
        if self.tail.is_none() {
            self.tail = Some(new_node.clone());
        }
        self.head = Some(new_node);
    }

    fn push_back(&mut self, value: i32) {
        let mut new_node = Box::new(Node {
            value,
            next: None,
            prev: self.tail.take(),
        });
        if let Some(ref mut old_tail) = new_node.prev {
            old_tail.next = Some(new_node.clone());
        }
        if self.head.is_none() {
            self.head = Some(new_node.clone());
        }
        self.tail = Some(new_node);
    }

    // Add print_dequeue method here
    // Your code here
}

Hint

Use a while let loop to traverse from head to tail and print values.

4

Test Dequeue by adding elements and printing

Create a main function. Inside it, create a mutable Dequeue instance with head and tail set to None. Use push_front to add 10 and 20, then use push_back to add 30. Finally, call print_dequeue() to display the dequeue.

DSA Rust

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

struct Dequeue {
    head: Option>,
    tail: Option>,
}

impl Dequeue {
    fn push_front(&mut self, value: i32) {
        let mut new_node = Box::new(Node {
            value,
            next: self.head.take(),
            prev: None,
        });
        if let Some(ref mut old_head) = new_node.next {
            old_head.prev = Some(new_node.clone());
        }
        if self.tail.is_none() {
            self.tail = Some(new_node.clone());
        }
        self.head = Some(new_node);
    }

    fn push_back(&mut self, value: i32) {
        let mut new_node = Box::new(Node {
            value,
            next: None,
            prev: self.tail.take(),
        });
        if let Some(ref mut old_tail) = new_node.prev {
            old_tail.next = Some(new_node.clone());
        }
        if self.head.is_none() {
            self.head = Some(new_node.clone());
        }
        self.tail = Some(new_node);
    }

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

fn main() {
    // Create Dequeue and add elements
    // Your code here
}

Hint

Remember to create Dequeue with head: None and tail: None. Then call push_front(10), push_front(20), push_back(30), and finally print_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