Queue Implementation Using Linked List in DSA Rust - Execution Trace

Concept Flow - Queue Implementation Using Linked List

Create new node

↓

Is queue empty?

Yes→Set head and tail to new node

No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

↓

Dequeue operation

↓

Is queue empty?

Yes→Return None

No↓

Save head data

↓

Move head to head.next

↓

If head is None, set tail to None

↓

Return saved data

This flow shows how enqueue adds nodes at the tail and dequeue removes nodes from the head, updating pointers accordingly.

Execution Sample

DSA Rust

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

// Enqueue adds node at tail
// Dequeue removes node from head

This code snippet shows the basic node structure and the enqueue/dequeue operations in a linked list queue.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Enqueue 10	10	head -> Node(10), tail -> Node(10)	10 -> null
2	Enqueue 20	10 -> 20	tail.next -> Node(20), tail -> Node(20)	10 -> 20 -> null
3	Enqueue 30	10 -> 20 -> 30	tail.next -> Node(30), tail -> Node(30)	10 -> 20 -> 30 -> null
4	Dequeue	20 -> 30	head -> Node(20)	20 -> 30 -> null
5	Dequeue	30	head -> Node(30)	30 -> null
6	Dequeue	empty	head -> None, tail -> None	null
7	Dequeue	empty	No change	null

💡 Step 7 dequeue stops because queue is empty (head is None).

Variable Tracker

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

Key Moments - 3 Insights

Why do we update tail.next when enqueueing a new node?

Because tail.next points to the new last node, linking the new node to the queue. See Step 2 and 3 in execution_table where tail.next changes.

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

Both head and tail become None, indicating the queue is empty. This is shown in Step 6 where after dequeue head and tail are None.

Why does dequeue remove from head and not tail?

Queue removes from the front (head) to maintain FIFO order. The execution_table shows head moving forward each dequeue (Steps 4, 5, 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after Step 3?

A 10 -> 20 -> 30 -> null

B 20 -> 30 -> null

C 30 -> null

D null

💡 Hint

Check the Visual State column at Step 3 in execution_table.

At which step does the queue become empty?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the Nodes in List and Pointer Changes columns in execution_table.

If we enqueue 40 after Step 6, what will tail point to?

A Node(30)

B Node(40)

C None

D Node(10)

💡 Hint

After Step 6, queue is empty, so tail should point to the new node. See concept_flow for enqueue.

Concept Snapshot

Queue using linked list:
- Enqueue adds node at tail
- Dequeue removes node from head
- Update head and tail pointers
- Empty queue: head and tail are None
- Maintains FIFO order

Full Transcript

This visualization shows how a queue is implemented using a linked list. Enqueue adds a new node at the tail, updating the tail pointer. Dequeue removes the node at the head, moving the head pointer forward. When the last node is dequeued, both head and tail become None, indicating the queue is empty. The execution table traces each step with the nodes present, pointer changes, and the visual state of the queue. Variable tracker shows how head, tail, and size change after each operation. Key moments clarify why tail.next is updated during enqueue, why head and tail become None when empty, and why dequeue removes from head to maintain FIFO order. The quiz tests understanding of queue state at different steps and pointer updates.

Practice

1. What is the main advantage of implementing a Queue using a linked list instead of an array?

easy

A. Simpler to implement than arrays

B. Faster access to elements by index

C. Dynamic size without fixed capacity limit

D. Uses less memory for small queues

Solution

1. Step 1: Understand queue size behavior

   Arrays have fixed size or require resizing, linked lists grow dynamically.

2. Step 2: Compare memory and resizing

   Linked lists allocate nodes as needed, so no fixed capacity limit exists.

3. Final Answer:

   Dynamic size without fixed capacity limit -> Option C

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked lists grow dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking linked lists allow fast random access
• Assuming arrays use less memory always
• Confusing implementation simplicity

2. Which of the following is the correct Rust syntax to define a node struct for a linked list queue?

easy

A. struct Node { data: i32, next: Option }

B. struct Node { data: i32, next: Node }

C. struct Node { data: i32, next: &Node }

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

Solution

1. Step 1: Understand Rust ownership for linked lists

   Rust requires heap allocation for recursive types using Box and Option for nullable links.

2. Step 2: Analyze options

   struct Node { data: i32, next: Option } uses Option which is correct for nullable next pointer; others cause infinite size or borrowing issues.

3. Final Answer:

   struct Node { data: i32, next: Option } -> Option A

4. Quick Check:

   Use Option for nullable next in Rust [OK]

Hint: Use Option for next pointer in Rust linked list [OK]

Common Mistakes:

• Using direct Node type causes infinite size error
• Using references (&Node) without lifetime causes errors
• Omitting Option for nullable next pointer

3. Given the following Rust code snippet for a queue implemented with a linked list, what will be printed after enqueueing 10, 20 and then dequeueing once?

let mut queue = Queue::new();
queue.enqueue(10);
queue.enqueue(20);
let val = queue.dequeue();
println!("Dequeued: {:?}", val);
queue.print();

medium

A. Dequeued: Some(10)
20 -> null

B. Dequeued: Some(20)
10 -> null

C. Dequeued: None
10 -> 20 -> null

D. Dequeued: Some(10)
10 -> 20 -> null

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10 adds node with 10, then enqueue 20 adds node with 20 at the end.

2. Step 2: Trace dequeue operation

   Dequeue removes front node (10), returns Some(10). Remaining queue has 20 only.

3. Final Answer:

   Dequeued: Some(10) 20 -> null -> Option A

4. Quick Check:

   First in first out, dequeue returns 10, queue left with 20 [OK]

Hint: Dequeue removes front, so first enqueued is first out [OK]

Common Mistakes:

• Assuming dequeue removes last element
• Printing queue before dequeue
• Confusing Some and None return values

4. Identify the bug in this Rust enqueue method for a linked list queue:

fn enqueue(&mut self, data: i32) {
    let new_node = Box::new(Node { data, next: None });
    if self.tail.is_none() {
        self.head = Some(new_node);
    } else {
        self.tail.as_mut().unwrap().next = Some(new_node);
    }
    self.tail = Some(new_node);
}

medium

A. Not updating head when queue is empty

B. Using Box instead of Rc for nodes

C. Missing return statement in enqueue

D. Assigning new_node to tail after moving it causes use-after-move error

Solution

1. Step 1: Analyze ownership of new_node

   new_node is moved into head or tail.next, so cannot be moved again.

2. Step 2: Identify use-after-move error

   Assigning self.tail = Some(new_node) after moving new_node causes compile error.

3. Final Answer:

   Assigning new_node to tail after moving it causes use-after-move error -> Option D

4. Quick Check:

   Moving new_node twice causes error [OK]

Hint: Don't move ownership twice; clone or restructure [OK]

Common Mistakes:

• Ignoring Rust ownership rules
• Not updating tail pointer correctly
• Confusing Box and Rc usage

5. You want to implement a method peek for your linked list queue in Rust that returns the front element without removing it. Which approach is correct?

hard

A. Return Option<i32> by cloning data from head node

B. Return Option<&i32> by borrowing data from head node

C. Return i32 directly, panicking if queue is empty

D. Return Option by moving head node

Solution

1. Step 1: Understand peek method goal

   Peek returns front element without removing it, so no ownership transfer.

2. Step 2: Choose correct return type

   Borrowing data with Option<&i32> avoids cloning or moving, safe and efficient.

3. Final Answer:

   Return Option<&i32> by borrowing data from head node -> Option B

4. Quick Check:

   Peek borrows front data, no ownership change [OK]

Hint: Peek borrows front data, don't move or clone unnecessarily [OK]

Common Mistakes:

• Moving head node causing queue modification
• Returning owned data causing unnecessary clone
• Panicking instead of returning Option