Queue Implementation Using Linked List in DSA Go - Time & Space Complexity

Time Complexity: Queue Implementation Using Linked List

O(1)

Understanding Time Complexity

We want to understand how the time taken by queue operations changes as the number of items grows.

Specifically, how fast can we add or remove items when using a linked list for a queue?

Scenario Under Consideration

Analyze the time complexity of the following queue operations using a linked list.

// Node structure
 type Node struct {
     value int
     next  *Node
 }

// Queue with front and rear pointers
 type Queue struct {
     front *Node
     rear  *Node
 }

// Enqueue adds to rear
 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
 }

// Dequeue removes from front
 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
 }
    

This code adds items to the end and removes items from the front of the queue using a linked list.

Identify Repeating Operations

Look for loops or repeated steps inside the operations.

• Primary operation: Adding or removing a single node pointer.
• How many times: Each enqueue or dequeue does a fixed number of steps, no loops.

How Execution Grows With Input

Each operation touches only a few nodes regardless of queue size.

Input Size (n)	Approx. Operations
10	5-6 steps per enqueue or dequeue
100	5-6 steps per enqueue or dequeue
1000	5-6 steps per enqueue or dequeue

Pattern observation: The number of steps stays about the same no matter how many items are in the queue.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing an item takes the same short time no matter how big the queue is.

Common Mistake

[X] Wrong: "Removing an item from the queue takes longer as the queue grows because we have to move through all nodes."

[OK] Correct: We keep a direct pointer to the front node, so removal is immediate without searching.

Interview Connect

Knowing that queue operations are constant time helps you explain efficient data handling clearly and confidently.

Self-Check

"What if we did not keep a rear pointer and had to find the end each time we enqueue? How would the time complexity change?"

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