Queue Implementation Using Linked List in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with given data.

DSA Go

func newNode(data int) *Node {
    return &Node{
        data: [1],
        next: nil,
    }
}

Drag options to blanks, or click blank then click option'

Anil

Bnext

CNode

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'next' instead of 'data' for the node's data field.

Assigning nil to data field.

The new node's data field should be set to the input parameter 'data'.

2fill in blank

medium

Complete the code to check if the queue is empty.

DSA Go

func (q *Queue) isEmpty() bool {
    return [1] == nil
}

Drag options to blanks, or click blank then click option'

Aq.front

Bq.tail

Cq

Dq.next

Attempts:

3 left

💡 Hint

Common Mistakes

Checking tail instead of front.

Checking the queue struct itself instead of its pointers.

The queue is empty if the front pointer is nil.

3fill in blank

hard

Fix the error in the enqueue method to correctly add a new node at the end.

DSA Go

func (q *Queue) enqueue(data int) {
    node := newNode(data)
    if q.tail == nil {
        q.front = node
        q.tail = node
    } else {
        q.tail.[1] = node
        q.tail = node
    }
}

Drag options to blanks, or click blank then click option'

Adata

Bfront

Cnext

Dtail

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning to tail instead of tail.next.

Assigning to front instead of tail.next.

The current tail's next pointer should point to the new node.

4fill in blank

hard

Fill both blanks to correctly dequeue an element and update the queue pointers.

DSA Go

func (q *Queue) dequeue() (int, bool) {
    if q.isEmpty() {
        return 0, false
    }
    data := q.front.data
    q.front = q.front.[1]
    if q.front == [2] {
        q.tail = nil
    }
    return data, true
}

Drag options to blanks, or click blank then click option'

Anext

Bfront

Cnil

Dtail

Attempts:

3 left

💡 Hint

Common Mistakes

Setting tail to front instead of nil.

Not updating front pointer correctly.

After removing the front node, move front to front.next. If front becomes nil, set tail to nil.

5fill in blank

hard

Fill all three blanks to implement a method that returns the queue elements as a slice.

DSA Go

func (q *Queue) toSlice() []int {
    var result []int
    current := q.front
    for current != [1] {
        result = append(result, current.[2])
        current = current.[3]
    }
    return result
}

Drag options to blanks, or click blank then click option'

Anil

Bdata

Cnext

Dfront

Attempts:

3 left

💡 Hint

Common Mistakes

Using front instead of nil as loop end condition.

Appending next instead of data.

Moving current to data instead of next.

Traverse nodes until current is nil, appending current.data and moving to current.next each 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