Queue Implementation Using Linked List in DSA Go

Mental Model

A queue is a line where elements wait their turn. Using a linked list means each element points to the next, so we can add at the end and remove from the front easily.

Analogy: Imagine a line of people waiting to buy tickets. The first person in line is served and leaves, and new people join at the end of the line.

front -> [1] -> [2] -> [3] -> null ← rear
↑front points here
               ↑rear points here

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, dequeue once, enqueue 3

Goal: Show how elements enter at the rear and leave from the front using linked list pointers

Step 1: enqueue 1: create node with value 1, front and rear point to it

front -> [1] -> null ← rear

Why: First element added, so front and rear both point to it

Step 2: enqueue 2: create node with value 2, link rear.next to new node, move rear to new node

front -> [1] -> [2] -> null ← rear

Why: Add new element at rear, update rear pointer

Step 3: dequeue: remove node at front (1), move front to next node (2)

front -> [2] -> null ← rear

Why: Remove element from front, update front pointer

Step 4: enqueue 3: create node with value 3, link rear.next to new node, move rear to new node

front -> [2] -> [3] -> null ← rear

Why: Add new element at rear, update rear pointer

Result:

front -> [2] -> [3] -> null ← rear

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

type Queue struct {
	front *Node
	rear  *Node
}

func (q *Queue) Enqueue(val int) {
	node := &Node{value: val}
	if q.rear == nil {
		q.front = node
		q.rear = node
		return
	}
	q.rear.next = node
	q.rear = node
}

func (q *Queue) Dequeue() (int, bool) {
	if q.front == nil {
		return 0, false
	}
	val := q.front.value
	q.front = q.front.next
	if q.front == nil {
		q.rear = nil
	}
	return val, true
}

func (q *Queue) Print() {
	curr := q.front
	for curr != nil {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next
	}
	fmt.Println("null")
}

func main() {
	q := &Queue{}
	q.Enqueue(1) // step 1
	q.Enqueue(2) // step 2
	q.Dequeue()  // step 3
	q.Enqueue(3) // step 4
	q.Print()
}

if q.rear == nil { q.front = node q.rear = node return }

handle empty queue by setting front and rear to new node

q.rear.next = node q.rear = node

link new node at rear and update rear pointer

if q.front == nil { q.rear = nil }

if queue becomes empty after dequeue, reset rear pointer

q.front = q.front.next

move front pointer forward to remove element

Output

2 -> 3 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only update pointers without traversing the list

Space: O(n) where n is number of elements because each element is stored in a node

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making dequeue O(1) instead of O(n)

Edge Cases

dequeue from empty queue

returns false and zero value, no crash

DSA Go

if q.front == nil {
	return 0, false
}

enqueue first element into empty queue

front and rear both point to new node

DSA Go

if q.rear == nil {
	q.front = node
	q.rear = node
	return
}

dequeue last element making queue empty

front and rear both become nil

DSA Go

if q.front == nil {
	q.rear = nil
}

When to Use This Pattern

When you need a first-in-first-out structure with efficient add and remove, use a queue with linked list to avoid costly shifts.

Common Mistakes

Mistake: Not updating rear pointer when queue becomes empty after dequeue
Fix: Set rear to nil when front becomes nil after dequeue

Mistake: Not handling empty queue case in enqueue, causing nil pointer errors
Fix: Check if rear is nil and set front and rear to new node

Summary

Implements a queue using a linked list with pointers to front and rear nodes.

Use when you want efficient enqueue and dequeue operations without shifting elements.

The key is to keep track of both front and rear pointers to add at rear and remove from front in O(1) time.

Practice

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

easy

A. Uses less memory for small queues

B. Dynamic size allows unlimited enqueue without resizing

C. Faster access to middle elements

D. Simpler to implement than arrays

Solution

1. Step 1: Understand queue size limitations in arrays

   Arrays have fixed size, so queues implemented with arrays need resizing or have limited capacity.

2. Step 2: Linked list dynamic size advantage

   Linked lists grow dynamically by adding nodes, so queues can grow without size limits.

3. Final Answer:

   Dynamic size allows unlimited enqueue without resizing -> Option B

4. Quick Check:

   Linked list queues grow dynamically [OK]

Hint: Linked list queues grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked list queues have faster random access
• Assuming linked lists use less memory always
• Confusing simplicity of implementation

2. Which of the following is the correct way to declare a node struct for a linked list queue in Go?

easy

A. type Node struct { data int; next *Node }

B. type Node struct { data int; next Node }

C. type Node struct { data *int; next *Node }

D. type Node struct { data int; next interface{} }

Solution

1. Step 1: Understand pointer usage in linked list nodes

   Each node's next field must be a pointer to another node to link nodes dynamically.

2. Step 2: Check each option's next field type

   type Node struct { data int; next *Node } uses *Node pointer correctly; B uses Node (value) causing infinite size; C uses *int for data unnecessarily; D uses interface{} which is not type-safe.

3. Final Answer:

   type Node struct { data int; next *Node } -> Option A

4. Quick Check:

   Node next must be *Node pointer [OK]

Hint: Node next must be pointer to Node type [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Using interface{} instead of *Node
• Making data a pointer unnecessarily

3. What will be the output after executing the following Go code that enqueues 10, 20, then dequeues one element from a linked list queue?

package main
import "fmt"

type Node struct {
  data int
  next *Node
}

type Queue struct {
  front *Node
  rear  *Node
}

func (q *Queue) Enqueue(val int) {
  newNode := &Node{data: val}
  if q.rear == nil {
    q.front = newNode
    q.rear = newNode
  } else {
    q.rear.next = newNode
    q.rear = newNode
  }
}

func (q *Queue) Dequeue() int {
  if q.front == nil {
    return -1
  }
  val := q.front.data
  q.front = q.front.next
  if q.front == nil {
    q.rear = nil
  }
  return val
}

func main() {
  q := &Queue{}
  q.Enqueue(10)
  q.Enqueue(20)
  fmt.Println(q.Dequeue())
  fmt.Println(q.front.data)
}

medium

A. 10
20

B. 20
10

C. 10
10

D. 20
20

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10: front and rear point to node with 10. Enqueue 20: rear.next points to node with 20, rear updated to 20.

2. Step 2: Trace dequeue and print operations

   Dequeue removes front node (10), returns 10. Now front points to node with 20. Printing q.front.data prints 20.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Dequeue returns 10, front data is 20 [OK]

Hint: Dequeue returns front, front moves to next [OK]

Common Mistakes:

• Confusing front and rear after dequeue
• Printing dequeued value twice
• Assuming rear changes on dequeue

4. Identify the bug in this Dequeue method of a linked list queue in Go:

func (q *Queue) Dequeue() int {
  if q.front == nil {
    return -1
  }
  val := q.front.data
  q.front = q.front.next
  return val
}

medium

A. Does not check if queue is empty before dequeue

B. Returns wrong value from front node

C. Does not update rear when queue becomes empty

D. Incorrectly assigns front to rear

Solution

1. Step 1: Analyze queue empty condition after dequeue

   If after removing front node, front becomes nil, rear must also be set to nil to avoid dangling pointer.

2. Step 2: Check code for rear update

   Code does not update rear when front is nil, causing rear to point to old node incorrectly.

3. Final Answer:

   Does not update rear when queue becomes empty -> Option C

4. Quick Check:

   Rear must be nil if front is nil after dequeue [OK]

Hint: Set rear to nil when front becomes nil [OK]

Common Mistakes:

• Forgetting to update rear on empty queue
• Returning wrong value from front
• Not checking for empty queue before dequeue

5. You want to implement a function to print all elements of a linked list queue from front to rear. Which approach is correct in Go?

func (q *Queue) PrintQueue() {
  current := q.front
  for current != nil {
    fmt.Print(current.data, " -> ")
    current = current.next
  }
  fmt.Println("null")
}

What will be the output after enqueueing 5, 15, 25 and calling PrintQueue()?

medium

A. 25 -> 15 -> 5 -> null

B. 5 -> 15 -> null

C. null

D. 5 -> 15 -> 25 -> null

Solution

1. Step 1: Understand enqueue order in linked list queue

   Enqueue adds nodes at rear, so order is 5 (front), then 15, then 25 (rear).

2. Step 2: Trace PrintQueue traversal

   PrintQueue starts at front and prints each node's data until nil, so prints 5 -> 15 -> 25 -> null.

3. Final Answer:

   5 -> 15 -> 25 -> null -> Option D

4. Quick Check:

   Print from front to rear = 5 -> 15 -> 25 -> null [OK]

Hint: Traverse from front to rear printing data [OK]

Common Mistakes:

• Printing in reverse order
• Stopping before last node
• Not printing null at end