Queue Implementation Using Linked List in DSA C#

Mental Model

A queue is a line where you add items at the back and remove from the front, like waiting in line. Using a linked list means each item points to the next, so we can easily add or remove without shifting everything.

Analogy: Imagine a line of people waiting to buy tickets. New people join at the end, and the person at the front gets served and leaves. Each person holds the hand of the next person, so you can find who is next easily.

front -> [Node1] -> [Node2] -> [Node3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how items are added at the rear and removed from the front using linked list pointers

Step 1: enqueue 10: create node with value 10, set front and rear to this node

front -> [10] -> null
rear ↑

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

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

front -> [10] -> [20] -> null
rear ↑

Why: Add new item at the end, update rear pointer

Step 3: dequeue: remove node at front (10), move front to next node (20)

front -> [20] -> null
rear ↑

Why: Remove from front, update front pointer

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

front -> [20] -> [30] -> null
rear ↑

Why: Add new item at the end, update rear pointer

Result:

front -> [20] -> [30] -> null
rear ↑

Annotated Code

DSA C#

using System;

public class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class QueueLinkedList
{
    private Node front;
    private Node rear;

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

    public void Enqueue(int value)
    {
        Node newNode = new Node(value);
        if (rear == null) // queue empty
        {
            front = newNode; // front and rear point to new node
            rear = newNode;
            return;
        }
        rear.Next = newNode; // link new node at end
        rear = newNode; // move rear to new node
    }

    public int Dequeue()
    {
        if (front == null) // queue empty
            throw new InvalidOperationException("Queue is empty");

        int value = front.Data; // get front value
        front = front.Next; // move front to next node

        if (front == null) // if queue became empty
            rear = null; // update rear to null

        return value;
    }

    public override string ToString()
    {
        Node current = front;
        string result = "";
        while (current != null)
        {
            result += current.Data + " -> ";
            current = current.Next;
        }
        result += "null";
        return result;
    }
}

class Program
{
    static void Main()
    {
        QueueLinkedList queue = new QueueLinkedList();
        queue.Enqueue(10);
        queue.Enqueue(20);
        Console.WriteLine(queue.ToString());
        int removed = queue.Dequeue();
        Console.WriteLine("Dequeued: " + removed);
        queue.Enqueue(30);
        Console.WriteLine(queue.ToString());
    }
}

if (rear == null) // queue empty

check if queue is empty to set front and rear to new node

rear.Next = newNode; // link new node at end

link new node after current rear

rear = newNode; // move rear to new node

update rear pointer to new node

if (front == null) // queue empty

check if queue is empty before dequeue

front = front.Next; // move front to next node

remove front node by moving front pointer

if (front == null) // if queue became empty rear = null; // update rear to null

if queue is empty after dequeue, reset rear pointer

Output

10 -> 20 -> null

Dequeued: 10

20 -> 30 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we only change pointers at front or rear without traversing the list

Space: O(n) because each element is stored as a node in the linked list

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making operations faster and more efficient

Edge Cases

dequeue from empty queue

throws InvalidOperationException to indicate queue is empty

DSA C#

if (front == null) // queue empty

enqueue first element into empty queue

front and rear both point to the new node

DSA C#

if (rear == null) // queue empty

dequeue last element making queue empty

front becomes null and rear is reset to null

DSA C#

if (front == null) // if queue became empty
    rear = null;

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating rear to null when last element is dequeued, causing rear to point to invalid node
Fix: After moving front, check if front is null and set rear to null as well

Mistake: Not handling empty queue case in dequeue, leading to null reference errors
Fix: Check if front is null before dequeue and throw exception or handle gracefully

Summary

Implements a queue using a linked list where elements are added at the rear and removed from the front.

Use when you want a queue with dynamic size and efficient enqueue and dequeue operations.

The key insight is to keep track of both front and rear pointers to add and remove nodes in constant time.

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