Dequeue Using Linked List in DSA Rust - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is Dequeue empty?

Yes→Set head and tail to new node

|No↓

Insert at front or rear?

↓

Front Insert

↓

New node.next = head

↓

head = new node

↓

Done

Shows how nodes are added at front or rear in a dequeue using a linked list, updating head and tail pointers accordingly.

Execution Sample

DSA Rust

struct Node {
    data: i32,
    next: Option<Box<Node>>,
}

// Insert at rear
fn enqueue_rear(head: &mut Option<Box<Node>>, tail: &mut Option<*mut Node>, data: i32) {
    // ...

This code inserts a new node at the rear of a dequeue implemented with a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize empty dequeue	None	head = None, tail = None	null
2	Enqueue 10 at rear	10	head -> Node(10), tail -> Node(10)	10 -> null
3	Enqueue 20 at rear	10 -> 20	tail moves to Node(20)	10 -> 20 -> null
4	Enqueue 5 at front	5 -> 10 -> 20	head moves to Node(5)	5 -> 10 -> 20 -> null
5	Dequeue from front (remove 5)	10 -> 20	head moves to Node(10)	10 -> 20 -> null
6	Dequeue from rear (remove 20)	10	tail moves to Node(10)	10 -> null
7	Dequeue from front (remove 10)	None	head = None, tail = None	null
8	Attempt dequeue from empty	None	No change	null

💡 Execution stops after dequeue attempts on empty list; no nodes remain.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
head	None	Node(10)	Node(10)	Node(5)	Node(10)	Node(10)	None	None
tail	None	Node(10)	Node(20)	Node(20)	Node(20)	Node(10)	None	None
list_size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why does the tail pointer move when we enqueue at the rear but not when we enqueue at the front?

Because when adding at the rear, the new node becomes the last node, so tail must update (see Step 3). When adding at the front, the head pointer moves to the new node but tail stays the same (see Step 4).

What happens to head and tail when the last node is dequeued?

Both head and tail become None, indicating the list is empty (see Step 7). This is important to avoid dangling pointers.

Why can't we dequeue from an empty dequeue?

Because head is None, meaning no nodes exist to remove (see Step 8). The operation does nothing and pointers remain unchanged.

Visual Quiz - 3 Questions

Look at the execution table at Step 4. What is the visual state of the list?

A 5 -> 10 -> 20 -> null

B 10 -> 20 -> null

C 20 -> 10 -> 5 -> null

D null

💡 Hint

Check the 'Visual State' column at Step 4 in the execution table.

At which step does the tail pointer move to Node(10)?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Pointer Changes' column for tail updates in the execution table.

If we enqueue 15 at the rear after Step 7, what will be the new visual state?

A 15 -> null

B 10 -> 15 -> null

C null

D 15 -> 10 -> null

💡 Hint

After Step 7, the list is empty; adding one node sets head and tail to that node only.

Concept Snapshot

Dequeue Using Linked List:
- Supports insertion/removal at both ends.
- Use head pointer for front, tail pointer for rear.
- Enqueue front: new node points to head, head updated.
- Enqueue rear: tail.next points to new node, tail updated.
- Dequeue front: head moves to next node.
- Dequeue rear: traverse to node before tail, update tail.
- Empty dequeue: head and tail are None.

Full Transcript

This visual execution traces a dequeue implemented with a linked list. We start with an empty dequeue where head and tail pointers are None. When we enqueue at the rear, if the list is empty, head and tail both point to the new node. Otherwise, tail.next points to the new node and tail moves to it. Enqueueing at the front sets the new node's next to head and updates head. Dequeueing from front moves head to the next node; dequeueing from rear moves tail to the previous node. When the last node is removed, both head and tail become None. Attempting to dequeue from an empty dequeue does nothing. The execution table shows each step's operation, pointer changes, and the visual linked list state. Variable tracker shows how head, tail, and list size change. Key moments clarify pointer updates and empty list handling. Quizzes test understanding of list state and pointer movements.

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