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.