Dequeue Using Linked List in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new empty Dequeue.

DSA Rust

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

impl<T> Dequeue<T> {
    fn new() -> Self {
        Dequeue {
            head: [1],
            tail: None,
        }
    }
}

Drag options to blanks, or click blank then click option'

ANone

BSome(Box::new(Node::new()))

CSome(Box::new(Node { value: T::default(), next: None }))

DSome(Box::new(Node { value: 0, next: None }))

Attempts:

3 left

💡 Hint

Common Mistakes

Setting head to Some(...) creates a node when the list should be empty.

Using default values without initializing properly.

The Dequeue starts empty, so head should be None.

2fill in blank

medium

Complete the code to add a new node at the front of the Dequeue.

DSA Rust

fn push_front(&mut self, value: T) {
    let mut new_node = Box::new(Node {
        value,
        next: self.head.take(),
    });
    let raw_node: *mut _ = &mut *new_node;
    self.head = Some(new_node);
    if self.tail.is_none() {
        self.tail = [1];
    }
}

Drag options to blanks, or click blank then click option'

ASome(Box::new(Node::new()))

BNone

CSome(&mut *new_node)

DSome(raw_node)

Attempts:

3 left

💡 Hint

Common Mistakes

Setting tail to None leaves the list inconsistent.

Trying to use Box::new() again instead of the raw pointer.

When the list was empty, tail should point to the new node's raw pointer.

3fill in blank

hard

Fix the error in the code to correctly remove a node from the back of the Dequeue.

DSA Rust

fn pop_back(&mut self) -> Option<T> {
    if self.head.is_none() {
        return None;
    }
    let mut current = self.head.as_mut().unwrap();
    while let Some(ref mut next_node) = current.next {
        if next_node.next.is_none() {
            let last_value = [1];
            current.next = None;
            self.tail = Some(current as *mut _);
            return Some(last_value);
        }
        current = next_node;
    }
    // Single element case
    let head = self.head.take().unwrap();
    self.tail = None;
    Some(head.value)
}

Drag options to blanks, or click blank then click option'

Astd::mem::replace(&mut next_node.value, unsafe { std::mem::zeroed() })

Bnext_node.value.clone()

Cstd::mem::replace(&mut next_node.value, Default::default())

Dreturn Some(next_node.value);

Attempts:

3 left

💡 Hint

Common Mistakes

Trying to return a reference instead of owned value.

Using unsafe zeroed memory which is unsafe for all types.

We must replace the value to move it out safely. Using Default::default() is safe for generic types.

4fill in blank

hard

Fill both blanks to complete the method that checks if the Dequeue is empty.

DSA Rust

fn is_empty(&self) -> bool {
    self.head [1] None && self.tail [2] None
}

Drag options to blanks, or click blank then click option'

A==

B!=

C&&

D||

Attempts:

3 left

💡 Hint

Common Mistakes

Using != instead of == causes wrong empty check.

Using || instead of && allows partial emptiness.

The Dequeue is empty if both head and tail are None.

5fill in blank

hard

Fill all three blanks to complete the method that adds a node at the back of the Dequeue.

DSA Rust

fn push_back(&mut self, value: T) {
    let mut new_node = Box::new(Node {
        value,
        next: None,
    });
    let raw_node: *mut _ = &mut *new_node;
    if self.tail.is_none() {
        self.head = Some(new_node);
        self.tail = Some(raw_node);
    } else {
        unsafe {
            (*self.tail.unwrap()).[1] = Some(new_node);
        }
        self.tail = [2];
    }
}

// Helper method to get raw pointer from Box
fn get_raw(node: &mut Box<Node<T>>) -> *mut Node<T> {
    [3]
}

Drag options to blanks, or click blank then click option'

Anext

BSome(raw_node)

C&mut **self.tail.unwrap()

D&mut *node

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to update tail after adding new node.

Using wrong pointer dereference syntax.

Returning wrong pointer in helper function.

1. Set the next of the current tail to the new node.
2. Update tail to point to the new node's raw pointer.
3. Return raw pointer from the Box by dereferencing.

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