Queue Implementation Using Linked List in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after enqueue and dequeue operations?

Consider a queue implemented using a linked list. After performing the following operations, what is the printed state of the queue?

Enqueue(10)
Enqueue(20)
Enqueue(30)
Dequeue()
Enqueue(40)

Print the queue from front to rear.

DSA C#

class Node {
    public int data;
    public Node next;
    public Node(int d) { data = d; next = null; }
}

class Queue {
    private Node front, rear;

    public Queue() { front = rear = null; }

    public void Enqueue(int item) {
        Node temp = new Node(item);
        if (rear == null) {
            front = rear = temp;
            return;
        }
        rear.next = temp;
        rear = temp;
    }

    public int Dequeue() {
        if (front == null) return -1;
        int item = front.data;
        front = front.next;
        if (front == null) rear = null;
        return item;
    }

    public string PrintQueue() {
        Node temp = front;
        string result = "";
        while (temp != null) {
            result += temp.data + " -> ";
            temp = temp.next;
        }
        return result + "null";
    }
}

Queue q = new Queue();
q.Enqueue(10);
q.Enqueue(20);
q.Enqueue(30);
q.Dequeue();
q.Enqueue(40);
Console.WriteLine(q.PrintQueue());

A 20 -> 30 -> 40 -> null

B 20 -> 30 -> null

C 30 -> 40 -> null

D 10 -> 20 -> 30 -> 40 -> null

💡 Hint

Remember that dequeue removes the front element.

Initially, queue is empty.
Enqueue 10, queue: 10 -> null
Enqueue 20, queue: 10 -> 20 -> null
Enqueue 30, queue: 10 -> 20 -> 30 -> null
Dequeue removes 10, queue: 20 -> 30 -> null
Enqueue 40, queue: 20 -> 30 -> 40 -> null

🧠 Conceptual

intermediate

What happens when dequeue is called on an empty queue?

In a queue implemented using a linked list, what is the expected behavior when Dequeue() is called but the queue is empty?

A Throws a NullReferenceException

B Returns -1 indicating the queue is empty

C Returns 0 as default value

D Adds a new node with value 0 to the queue

💡 Hint

Check the Dequeue method's return value when front is null.

The Dequeue method checks if the front node is null. If yes, it returns -1 to indicate the queue is empty and no element can be dequeued.

🔧 Debug

advanced

Identify the bug in this enqueue method

What is the bug in the following enqueue method for a linked list queue?

public void Enqueue(int item) {
    Node temp = new Node(item);
    if (front == null) {
        front = temp;
    }
    rear.next = temp;
    rear = temp;
}

A temp node is not created properly

B front is not updated when queue is empty

C rear is not updated after enqueue

D rear.next will cause NullReferenceException when queue is empty

💡 Hint

Think about what happens when the queue is empty and rear is null.

If the queue is empty, rear is null. Trying to access rear.next causes a NullReferenceException. The code should return after setting front and rear to temp.

❓ Predict Output

advanced

What is the queue state after multiple dequeues?

Given the following operations on a linked list queue, what is the printed queue?

Enqueue(5)
Enqueue(15)
Enqueue(25)
Dequeue()
Dequeue()
Enqueue(35)

Print the queue from front to rear.

DSA C#

class Node {
    public int data;
    public Node next;
    public Node(int d) { data = d; next = null; }
}

class Queue {
    private Node front, rear;

    public Queue() { front = rear = null; }

    public void Enqueue(int item) {
        Node temp = new Node(item);
        if (rear == null) {
            front = rear = temp;
            return;
        }
        rear.next = temp;
        rear = temp;
    }

    public int Dequeue() {
        if (front == null) return -1;
        int item = front.data;
        front = front.next;
        if (front == null) rear = null;
        return item;
    }

    public string PrintQueue() {
        Node temp = front;
        string result = "";
        while (temp != null) {
            result += temp.data + " -> ";
            temp = temp.next;
        }
        return result + "null";
    }
}

Queue q = new Queue();
q.Enqueue(5);
q.Enqueue(15);
q.Enqueue(25);
q.Dequeue();
q.Dequeue();
q.Enqueue(35);
Console.WriteLine(q.PrintQueue());

A 25 -> 35 -> null

B 15 -> 25 -> 35 -> null

C 25 -> null

D 35 -> null

💡 Hint

Track the front pointer after each dequeue.

Queue after enqueues: 5 -> 15 -> 25 -> null
After first dequeue: removes 5, queue: 15 -> 25 -> null
After second dequeue: removes 15, queue: 25 -> null
Enqueue 35: queue: 25 -> 35 -> null
But note the code sets rear to null if front is null after dequeue. Here front is 25, so rear is not null.
Output is 25 -> 35 -> null

🧠 Conceptual

expert

Why is a linked list preferred over an array for queue implementation in some cases?

Which of the following is the best reason to use a linked list instead of an array to implement a queue?

A Linked list provides faster random access than arrays

B Linked list uses less memory than arrays always

C Linked list allows dynamic size without resizing overhead

D Linked list is easier to implement than arrays

💡 Hint

Think about resizing and memory allocation.

Arrays have fixed size or require resizing which is costly. Linked lists grow dynamically without resizing overhead, making them suitable for queues with unknown or changing size.

Practice

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

easy

A. Dynamic size without fixed capacity

B. Faster access to elements by index

C. Uses less memory for small queues

D. Simpler syntax for enqueue operation

Solution

1. Step 1: Understand array limitations

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

2. Step 2: Linked list flexibility

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

3. Final Answer:

   Dynamic size without fixed capacity -> Option A

4. Quick Check:

   Linked list queues grow dynamically = D [OK]

Hint: Linked lists grow dynamically, arrays do not [OK]

Common Mistakes:

• Thinking arrays allow dynamic resizing easily
• Confusing access speed with size flexibility
• Assuming linked lists use less memory always

2. Which of the following is the correct way to declare a node class for a linked list queue in C#?

easy

A. class Node { int data; Node next; }

B. public class Node { public int data; public Node next; }

C. public struct Node { public int data; public Node next; }

D. public class Node { private int data; private Node next; }

Solution

1. Step 1: Check access modifiers

   For queue operations, node fields must be accessible; public allows this.

2. Step 2: Class vs struct

   Node should be a class to allow reference behavior; struct is value type and not suitable here.

3. Final Answer:

   public class Node { public int data; public Node next; } -> Option B

4. Quick Check:

   Public class with public fields = A [OK]

Hint: Use public class with public fields for linked list nodes [OK]

Common Mistakes:

• Using struct instead of class for nodes
• Omitting public keyword causing access errors
• Making fields private without accessors

3. What will be the output after executing the following C# code for a linked list queue?

Queue queue = new Queue();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);
int first = queue.Dequeue();
queue.Enqueue(40);
int second = queue.Dequeue();
Console.WriteLine(first + ", " + second);

medium

A. 10, 30

B. 20, 30

C. 10, 20

D. 20, 40

Solution

1. Step 1: Trace enqueue and dequeue operations

   Enqueue 10, 20, 30 adds these in order. Dequeue removes 10 (first). Enqueue 40 adds at end. Dequeue removes 20 (next).

2. Step 2: Identify values of first and second

   first = 10, second = 20. Output prints "10, 20".

3. Final Answer:

   10, 20 -> Option C

4. Quick Check:

   FIFO order = 10, 20 [OK]

Hint: Remember queue removes oldest element first (FIFO) [OK]

Common Mistakes:

• Confusing enqueue and dequeue order
• Assuming dequeue removes last element
• Mixing values after enqueue and dequeue

4. Identify the error in the following dequeue method of a linked list queue and select the fix:

public int Dequeue() {
  if (front == null) throw new InvalidOperationException("Queue is empty");
  int value = front.data;
  front = front.next;
  return value;
}

medium

A. Should set rear to null when queue becomes empty

B. Should throw NullReferenceException instead

C. No error; method is correct

D. Should update front.next to null before returning

Solution

1. Step 1: Analyze dequeue when one element remains

   If front moves to null after removing last node, rear still points to old node, causing inconsistency.

2. Step 2: Fix by setting rear to null when queue is empty

   When front is null, rear must also be set to null to indicate empty queue properly.

3. Final Answer:

   Should set rear to null when queue becomes empty -> Option A

4. Quick Check:

   Rear must be null if front is null [OK]

Hint: Set rear null when queue empties after dequeue [OK]

Common Mistakes:

• Ignoring rear pointer update on empty queue
• Throwing wrong exception type
• Unnecessary null assignment to front.next

5. You want to implement a method ReverseQueue() that reverses the order of elements in a linked list queue without using extra data structures. Which approach is best?

hard

A. Dequeue all elements and enqueue them back in reverse order using a stack

B. Swap data values between front and rear nodes repeatedly

C. Create a new queue and enqueue elements in reverse order by traversing original queue

D. Iteratively reverse the linked list nodes by changing next pointers

Solution

1. Step 1: Understand reversing linked list nodes

   Changing next pointers of nodes reverses the linked list in place without extra space.

2. Step 2: Compare with other options

   Using stack or new queue uses extra space; swapping data is inefficient and error-prone.

3. Final Answer:

   Iteratively reverse the linked list nodes by changing next pointers -> Option D

4. Quick Check:

   In-place reversal changes pointers = B [OK]

Hint: Reverse linked list by pointer changes, no extra space [OK]

Common Mistakes:

• Using extra data structures despite constraint
• Swapping data instead of pointers
• Creating new queues unnecessarily