Queue Implementation Using Linked List in DSA Go - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine you are managing a line of customers waiting for service at a bank. You want to keep track of who is next in line and who just joined the line. This project will help you build a queue using a linked list to manage this line efficiently.

🎯 Goal: Build a queue data structure using a linked list in Go. You will create nodes, link them, and implement enqueue and dequeue operations to add and remove customers from the line.

📋 What You'll Learn

Create a Node struct with an integer value and a pointer to the next node

Create a Queue struct with pointers to the front and rear nodes

Implement an Enqueue method to add a node to the rear of the queue

Implement a Dequeue method to remove a node from the front of the queue

Print the queue elements from front to rear after operations

💡 Why This Matters

🌍 Real World

Queues are used in real life to manage lines, like customers waiting for service, print jobs waiting to print, or tasks waiting to be processed.

💼 Career

Understanding queue implementation helps in software development roles where managing ordered tasks or events efficiently is important, such as backend development, systems programming, and real-time processing.

1

Create Node and Queue structs

Create a struct called Node with fields value int and next *Node. Then create a struct called Queue with fields front *Node and rear *Node.

DSA Go

type Node struct {
    value int
    next *Node
}

type Queue struct {
    front *Node
    rear *Node
}

// Your code here

Hint

Think of Node as a single person in line holding a number, and Queue as the whole line with pointers to the first and last person.

2

Add Enqueue method to Queue

Add a method called Enqueue to the Queue struct that takes an integer val and adds a new Node with this value to the rear of the queue.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

type Queue struct {
    front *Node
    rear *Node
}

func (q *Queue) Enqueue(val int) {
    // Your code here
}

func main() {
    // Your code here
}

Hint

When the queue is empty, both front and rear point to the new node. Otherwise, link the new node at the rear and update the rear pointer.

3

Add Dequeue method to Queue

Add a method called Dequeue to the Queue struct that removes the front node from the queue and returns its value. If the queue is empty, return -1.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

type Queue struct {
    front *Node
    rear *Node
}

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

func (q *Queue) Dequeue() int {
    // Your code here
}

func main() {
    // Your code here
}

Hint

Remove the front node by moving the front pointer to the next node. If the queue becomes empty, set rear to nil.

4

Test Queue by Enqueueing and Dequeueing

In the main function, create a Queue variable called q. Enqueue the values 10, 20, and 30 in that order. Then dequeue one value and print the remaining queue elements from front to rear separated by spaces.

DSA Go

package main

type Node struct {
    value int
    next *Node
}

type Queue struct {
    front *Node
    rear *Node
}

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

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

func main() {
    var q Queue
    // Your code here
}

Hint

After removing the first value (10), print the remaining values 20 and 30 separated by a space.

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