Enqueue Using Linked List in DSA Python - Execution Trace

Concept Flow - Enqueue Using Linked List

Create new node with value

↓

Is queue empty?

Yes→Set head and tail to new node

No↓

Set tail.next to new node

↓

Update tail to new node

↓

Done

This flow shows how a new node is created and added at the end of the linked list queue, updating pointers accordingly.

Execution Sample

DSA Python

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

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

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

This code adds a new value to the end of a queue implemented with a linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with value 10	None	None	null
2	Queue empty? Yes	None	head -> new_node(10), tail -> new_node(10)	10 -> null
3	Create new node with value 20	10	None	10 -> null
4	Queue empty? No	10	tail.next -> new_node(20)	10 -> 20 -> null
5	Update tail to new_node(20)	10 -> 20	tail -> new_node(20)	10 -> 20 -> null
6	Create new node with value 30	10 -> 20	None	10 -> 20 -> null
7	Queue empty? No	10 -> 20	tail.next -> new_node(30)	10 -> 20 -> 30 -> null
8	Update tail to new_node(30)	10 -> 20 -> 30	tail -> new_node(30)	10 -> 20 -> 30 -> null
9	End of enqueue operations	10 -> 20 -> 30	No changes	10 -> 20 -> 30 -> null

💡 All enqueue operations completed, queue updated with new nodes at tail.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	Final
head	None	Node(10)	Node(10)	Node(10)	Node(10)
tail	None	Node(10)	Node(20)	Node(30)	Node(30)
new_node	None	Node(10)	Node(20)	Node(30)	Node(30)

Key Moments - 3 Insights

Why do we check if the queue is empty before adding a new node?

Because if the queue is empty (head is None), both head and tail must point to the new node. This is shown in step 2 where head and tail are set to the new node.

Why do we update tail.next before moving tail to the new node?

Updating tail.next links the current last node to the new node, maintaining the chain. Then tail moves to the new node to mark the new end. This is shown in steps 4 and 5.

What happens if we forget to update the tail pointer after enqueue?

The tail pointer would still point to the old last node, breaking the queue's structure and causing incorrect enqueue behavior. Step 8 shows the correct tail update.

Visual Quiz - 3 Questions

Look at the execution table, what is the state of the queue after step 5?

A 10 -> null

B 10 -> 20 -> null

C 20 -> null

D null

💡 Hint

Check the Visual State column at step 5 in the execution_table.

At which step does the tail pointer first change from Node(10) to Node(20)?

A Step 2

B Step 4

C Step 5

D Step 7

💡 Hint

Look at the Pointer Changes and variable_tracker for tail pointer updates.

If the queue was initially empty, what pointers are set when the first node is enqueued?

A Both head and tail are set to new node

B Only head is set to new node

C Only tail is set to new node

D Neither head nor tail is set

💡 Hint

Refer to step 2 in execution_table where queue is empty and pointers are set.

Concept Snapshot

Enqueue Using Linked List:
- Create a new node with the value.
- If queue is empty, set head and tail to new node.
- Else, set tail.next to new node and update tail.
- This adds elements at the end efficiently.
- Maintains FIFO order in queue.

Full Transcript

Enqueue operation in a linked list queue involves creating a new node with the given value. If the queue is empty, both head and tail pointers are set to this new node. Otherwise, the current tail's next pointer is linked to the new node, and then the tail pointer is updated to the new node. This process ensures new elements are added at the end, maintaining the queue's FIFO order. The execution table shows step-by-step how nodes are created, pointers updated, and the visual state of the queue after each operation. Key moments clarify why checking for empty queue and updating tail pointer are essential. The visual quiz tests understanding of pointer updates and queue state during enqueue.