Dequeue Using Linked List in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Dequeue (Double-Ended Queue)?

A Dequeue is a data structure where elements can be added or removed from both the front and the rear ends.

beginner

Why use a linked list to implement a Dequeue?

A linked list allows efficient insertion and deletion at both ends without shifting elements, making it ideal for Dequeue operations.

intermediate

In a linked list based Dequeue, what pointers are typically maintained?

Two pointers: one to the front node and one to the rear node, to allow quick access for insertion and deletion at both ends.

beginner

What happens when you remove an element from an empty Dequeue?

It results in an underflow condition; no element can be removed because the Dequeue is empty.

intermediate

How does the Dequeue maintain order when inserting at the front and rear?

Inserting at the front adds a new node before the current front, and inserting at the rear adds a new node after the current rear, preserving the order of elements.

Which operation is NOT supported efficiently by a linked list based Dequeue?

A Insertion at front

B Random access by index

C Deletion at rear

D Insertion at rear

Linked lists do not support efficient random access by index; accessing elements by position requires traversal.

What pointers are essential in a linked list Dequeue to allow O(1) insertion and deletion?

A Only front pointer

B Only rear pointer

C No pointers needed

D Both front and rear pointers

Both front and rear pointers are needed to perform insertion and deletion at both ends efficiently.

What is the time complexity of inserting an element at the front of a linked list Dequeue?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Insertion at the front of a linked list is done in constant time O(1) by adjusting pointers.

What happens to the rear pointer when the last element is removed from the Dequeue?

A It points to the previous node

B It points to the front node

C It becomes null

D It remains unchanged

When the last element is removed, both front and rear pointers become null indicating the Dequeue is empty.

Which of these is a valid operation in a Dequeue?

A Insert and delete at both front and rear

B Delete only at front

C Insert only at rear

D Insert and delete only in the middle

Dequeue supports insertion and deletion at both front and rear ends.

Explain how insertion at the front of a linked list based Dequeue works.

Think about how to add a new node before the current front node.

Describe the steps to remove an element from the rear of a linked list based Dequeue.

Consider how to update pointers when the last node is removed.

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