Queue Implementation Using Linked List in DSA Python - 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 or error

|No↓

Save head node data

↓

Move head to head.next

↓

If head is None, set tail to None

↓

Return saved data

This flow shows how nodes are added at the tail and removed from the head in a linked list queue.

Execution Sample

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def dequeue(self):
        if not self.head:
            return None
        removed_data = self.head.data
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return removed_data

This code adds elements to the end and removes from the front of 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 -> None
2	Enqueue 20	10 -> 20	tail.next=Node(20), tail=Node(20)	10 -> 20 -> None
3	Enqueue 30	10 -> 20 -> 30	tail.next=Node(30), tail=Node(30)	10 -> 20 -> 30 -> None
4	Dequeue	20 -> 30	head=Node(20)	20 -> 30 -> None
5	Dequeue	30	head=Node(30)	30 -> None
6	Dequeue		head=None, tail=None	Empty
7	Dequeue on empty		No change	Empty

💡 Execution stops after dequeue on empty queue returns 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
List Size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why do we update tail to None when the last element is dequeued?

Because after removing the last node, the queue becomes empty. Both head and tail must be None to show the queue is empty, as shown in step 6 of the execution_table.

Why do we add new nodes at tail and remove from head?

This keeps the queue order correct: first in, first out. Enqueue adds at tail (steps 1-3), dequeue removes from head (steps 4-6), maintaining order.

What happens if we dequeue when the queue is empty?

The dequeue method returns None and does not change pointers, as shown in step 7 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the head pointer after step 3?

A Node with data 10

B Node with data 20

C Node with data 30

D None

💡 Hint

Check the 'head' row in variable_tracker after step 3.

At which step does the queue become empty?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look at the 'Visual State' column in execution_table where it shows 'Empty'.

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

A Node with data 30

B Node with data 40

C None

D Node with data 10

💡 Hint

After emptying the queue, enqueue sets both head and tail to the new node.

Concept Snapshot

Queue using linked list:
- Enqueue adds node at tail
- Dequeue removes node from head
- If queue empty, head and tail are None
- Maintains FIFO order
- Tail pointer updated on enqueue
- Head pointer updated on dequeue

Full Transcript

This visualization shows how a queue is implemented using a linked list. Nodes are added at the tail and removed from the head to keep the first-in-first-out order. When enqueueing, if the queue is empty, both head and tail point to the new node. Otherwise, the new node is linked at the tail and tail pointer moves. When dequeueing, the head pointer moves to the next node. If the queue becomes empty after dequeue, tail is set to None. Dequeue on an empty queue returns None without changes. The execution table tracks each step's nodes, pointer changes, and visual state. The variable tracker shows how head, tail, and size change over time. Key moments clarify why tail is updated on empty and why enqueue and dequeue operate at tail and head respectively. The quiz tests understanding of pointer positions and queue state changes.

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 middle elements

C. Uses less memory for small queues

D. Dynamic size without fixed capacity limit

Solution

1. Step 1: Understand queue size limitation in arrays

   Arrays have fixed size, so queues implemented with arrays have a maximum capacity.

2. Step 2: Linked list dynamic sizing

   Linked lists can grow or shrink dynamically as nodes are added or removed, so no fixed size limit.

3. Final Answer:

   Dynamic size without fixed capacity limit -> Option D

4. Quick Check:

   Linked list queues grow dynamically = A [OK]

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

Common Mistakes:

• Thinking linked lists allow faster middle access
• Assuming linked lists always use less memory
• Confusing implementation simplicity

2. Which of the following is the correct way to initialize an empty queue using a linked list in Python?

easy

A. queue = LinkedList()

B. queue = None

C. queue = Queue() with head and tail as None

D. queue = []

Solution

1. Step 1: Understand queue initialization

   An empty queue using linked list usually has head and tail pointers set to None.

2. Step 2: Identify correct initialization

   queue = Queue() with head and tail as None correctly describes a Queue class with head and tail as None, representing empty queue.

3. Final Answer:

   queue = Queue() with head and tail as None -> Option C

4. Quick Check:

   Empty queue has head and tail None = B [OK]

Hint: Empty linked list queue has head and tail as None [OK]

Common Mistakes:

• Using list [] instead of linked list
• Setting queue to None without structure
• Confusing linked list with array initialization

3. What will be the output after performing these operations on an empty linked list queue?

enqueue(10)
enqueue(20)
dequeue()
enqueue(30)
dequeue()

Print the queue elements from front to rear.

medium

A. 30 -> null

B. 20 -> 30 -> null

C. 10 -> 20 -> 30 -> null

D. 20 -> null

Solution

1. Step 1: Perform enqueue(10) and enqueue(20)

   Queue becomes 10 -> 20 -> null.

2. Step 2: Perform dequeue()

   Removes 10, queue is now 20 -> null.

3. Step 3: Perform enqueue(30)

   Queue becomes 20 -> 30 -> null.

4. Step 4: Perform dequeue()

   Removes 20, queue is now 30 -> null.

5. Final Answer:

   30 -> null -> Option A

6. Quick Check:

   After operations, queue front is 30 [OK]

Hint: Track enqueue/dequeue stepwise to find final queue [OK]

Common Mistakes:

• Forgetting to remove front element on dequeue
• Appending dequeue element instead of removing
• Mixing order of operations

4. Identify the error in this dequeue method of a linked list queue:

def dequeue(self):
    if self.head is None:
        return None
    temp = self.head
    self.head = self.head.next
    return temp.data
    self.tail = None

medium

A. The tail is set to None after return, so never updated

B. The method does not check if queue is empty

C. It should update head before returning data

D. temp.data is not a valid attribute

Solution

1. Step 1: Analyze the order of statements

   The return statement occurs before setting tail to None, so tail update never happens.

2. Step 2: Understand impact on queue state

   If last element is dequeued, tail should be set to None to mark empty queue, but it is skipped.

3. Final Answer:

   The tail is set to None after return, so never updated -> Option A

4. Quick Check:

   Return before tail update skips tail reset [OK]

Hint: Return ends function; update tail before return [OK]

Common Mistakes:

• Placing return before all updates
• Not resetting tail when queue becomes empty
• Ignoring empty queue check

5. You want to implement a method to reverse the queue implemented using a linked list without using extra data structures. Which approach is best?

hard

A. Create a new linked list and enqueue elements from old queue in reverse

B. Use recursion to dequeue and enqueue elements in reverse order

C. Traverse the linked list and swap data of nodes pairwise

D. Use a stack to store elements and then enqueue back

Solution

1. Step 1: Understand constraints

   No extra data structures allowed, so stack or new list are not options.

2. Step 2: Use recursion to reverse queue

   Recursion uses call stack implicitly to dequeue all elements, then enqueue them back in reverse order.

3. Final Answer:

   Use recursion to dequeue and enqueue elements in reverse order -> Option B

4. Quick Check:

   Recursion reverses queue without extra structures [OK]

Hint: Recursion uses call stack to reverse without extra structures [OK]

Common Mistakes:

• Using extra data structures despite constraints
• Swapping data pairs does not reverse queue order
• Creating new linked list violates no extra structure rule