Enqueue Using Linked List in DSA Go - Execution Trace

Concept Flow - Enqueue Using Linked List

Create new node with data

↓

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 representing the queue. If empty, head and tail point to it; otherwise, tail's next points to it and tail moves.

Execution Sample

DSA Go

func Enqueue(data int) {
  newNode := &Node{data: data}
  if tail == nil {
    head = newNode
    tail = newNode
  } else {
    tail.next = newNode
    tail = newNode
  }
}

This code adds a new node with given data to the end of the linked list queue.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	None	None	null
2	Check if tail is nil (queue empty)	None	tail=nil	null
3	Set head and tail to new node	10	head->10, tail->10	10 -> null
4	Create new node with data=20	10	None	10 -> null
5	Check if tail is nil	10	tail->10 (not nil)	10 -> null
6	Set tail.next to new node	10, 20	tail.next->20	10 -> 20 -> null
7	Update tail to new node	10, 20	tail->20	10 -> 20 -> null
8	Create new node with data=30	10, 20	None	10 -> 20 -> null
9	Check if tail is nil	10, 20	tail->20 (not nil)	10 -> 20 -> null
10	Set tail.next to new node	10, 20, 30	tail.next->30	10 -> 20 -> 30 -> null
11	Update tail to new node	10, 20, 30	tail->30	10 -> 20 -> 30 -> null
12	End of enqueue operations	10, 20, 30	tail->30	10 -> 20 -> 30 -> null

💡 All nodes enqueued; tail points to last node; list represents queue order.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	nil	Node(10)	Node(10)	Node(10)	Node(10)
tail	nil	Node(10)	Node(20)	Node(30)	Node(30)
newNode	nil	Node(10)	Node(20)	Node(30)	nil (reset after each enqueue)
List Size	0	1	2	3	3

Key Moments - 3 Insights

Why do we check if tail is nil before adding a new node?

Because if tail is nil, the queue is empty, so both head and tail must point to the new node. This is shown in execution_table rows 2 and 3.

Why do we update tail.next before moving tail?

We must link the current last node (tail) to the new node before moving tail, so the list stays connected. See execution_table rows 6 and 7.

What happens if we forget to update tail after enqueue?

The tail pointer would still point to the old last node, breaking the queue's end. New nodes won't be added correctly. This is avoided by step 7 and 11.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what pointer change happens?

A tail moves to node with data 10

B head points to new node with data 20

C tail.next points to new node with data 20

D newNode is deleted

💡 Hint

Check the 'Pointer Changes' column at step 6 in execution_table.

At which step does the queue first have two nodes?

A Step 6

B Step 7

C Step 3

D Step 10

💡 Hint

Look at 'Nodes in List' and 'Visual State' columns to see when two nodes appear.

If we enqueue a new node when tail is nil, what happens to head?

A head remains nil

B head points to the new node

C head points to old node

D head points to tail.next

💡 Hint

Refer to execution_table rows 2 and 3 where tail is nil and head is set.

Concept Snapshot

Enqueue Using Linked List:
- Create new node with data
- If queue empty (tail nil), set head and tail to new node
- Else, set tail.next to new node
- Update tail to new node
- Queue order maintained by linked nodes
- Tail always points to last node

Full Transcript

Enqueue operation in a linked list queue adds a new node at the end. First, a new node is created with the given data. If the queue is empty (tail is nil), both head and tail point to this new node. Otherwise, the current tail's next pointer is set to the new node, and then tail is updated to this new node. This keeps the queue order intact. The execution table shows each step with pointer changes and the visual linked list state. The variable tracker follows head, tail, newNode, and list size changes. Key moments clarify why checking tail nil is important and why tail.next must be updated before moving tail. The visual quiz tests understanding of pointer changes and queue state at different steps.

Practice

1. What does the enqueue operation do in a queue implemented using a linked list?

easy

A. Deletes the last element from the linked list

B. Adds a new element at the end of the linked list

C. Removes the first element from the linked list

D. Checks if the linked list is empty

Solution

1. Step 1: Understand enqueue operation

   Enqueue means adding an element to the queue.

2. Step 2: Enqueue in linked list context

   In a linked list queue, enqueue adds the new node at the end (tail).

3. Final Answer:

   Adds a new element at the end of the linked list -> Option B

4. Quick Check:

   Enqueue = Add at end [OK]

Hint: Enqueue always adds at the tail of the linked list [OK]

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding element at the head instead of tail
• Thinking enqueue removes elements
• Assuming enqueue checks emptiness

2. Which of the following is the correct syntax to create a new node and enqueue it in Go using a linked list?

easy

A. node := &Node{data: value, next: nil}
queue.tail.next = node
queue.tail = node

B. node := Node{value, nil}
queue.head = node

C. node := &Node{value}
queue.head.next = node

D. node := Node{data: value}
queue.tail = node.next

Solution

1. Step 1: Create new node correctly

   Use pointer to Node with data and next set to nil.

2. Step 2: Link new node at tail and update tail

   Set current tail's next to new node, then update tail pointer.

3. Final Answer:

   node := &Node{data: value, next: nil} queue.tail.next = node queue.tail = node -> Option A

4. Quick Check:

   New node pointer + update tail = A [OK]

Hint: Always use pointer and update tail's next and tail itself [OK]

Common Mistakes:

• Not using pointer for new node
• Assigning new node to head instead of tail
• Forgetting to update tail pointer
• Incorrect struct initialization syntax

3. What will be the state of the queue after executing the following Go code?

type Node struct {
    data int
    next *Node
}

type Queue struct {
    head *Node
    tail *Node
}

func (q *Queue) enqueue(value int) {
    node := &Node{data: value}
    if q.tail == nil {
        q.head = node
        q.tail = node
    } else {
        q.tail.next = node
        q.tail = node
    }
}

func main() {
    q := &Queue{}
    q.enqueue(10)
    q.enqueue(20)
    q.enqueue(30)
    // Print queue
    current := q.head
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

medium

A. 30 -> 20 -> 10 -> null

B. null

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

D. 10 -> 20 -> 30 -> null

Solution

1. Step 1: Enqueue elements in order

   Elements 10, 20, 30 are added at the tail one by one.

2. Step 2: Traverse from head to tail

   Traversal prints nodes in order: 10, then 20, then 30, then null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option D

4. Quick Check:

   Enqueue order preserved in linked list [OK]

Hint: Enqueue adds at tail, print from head to tail [OK]

Common Mistakes:

• Assuming new elements added at head
• Printing tail to head order
• Forgetting to print 'null' at end
• Confusing enqueue with dequeue output

4. Identify the error in the following Go enqueue function for a linked list queue and select the fix.

func (q *Queue) enqueue(value int) {
    node := &Node{data: value}
    if q.head == nil {
        q.head = node
    } else {
        q.tail.next = node
    }
}

medium

A. Missing update of q.tail to new node after adding

B. Should check q.tail == nil instead of q.head == nil

C. Node should be created without pointer

D. Should assign q.head.next = node instead of q.tail.next

Solution

1. Step 1: Analyze enqueue logic

   Function sets head if empty, else links new node after tail.

2. Step 2: Check tail pointer update

   Function does not update q.tail to new node, so tail remains old node.

3. Final Answer:

   Missing update of q.tail to new node after adding -> Option A

4. Quick Check:

   Update tail pointer after enqueue [OK]

Hint: Always update tail pointer after adding new node [OK]

Common Mistakes:

• Not updating tail pointer after enqueue
• Checking wrong pointer for empty queue
• Creating node without pointer
• Linking new node to head instead of tail

5. You want to implement a queue using a linked list in Go that supports enqueue and dequeue efficiently. Which of the following changes will improve the enqueue operation's time complexity from O(n) to O(1)?

hard

A. Add new nodes at the head instead of the tail

B. Use a doubly linked list instead of singly linked list

C. Maintain a tail pointer to the last node and update it on enqueue

D. Traverse the list to find the last node each time before enqueue

Solution

1. Step 1: Understand enqueue time complexity

   Without tail pointer, enqueue requires traversal to last node, O(n).

2. Step 2: Using tail pointer

   Maintaining tail pointer allows direct access to last node, making enqueue O(1).

3. Final Answer:

   Maintain a tail pointer to the last node and update it on enqueue -> Option C

4. Quick Check:

   Tail pointer reduces enqueue to O(1) [OK]

Hint: Keep tail pointer to avoid traversal on enqueue [OK]

Common Mistakes:

• Thinking doubly linked list alone improves enqueue
• Adding at head breaks queue order
• Traversing list each time causes O(n) complexity
• Ignoring tail pointer update