Queue Implementation Using Linked List in DSA C# - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line at a coffee shop where customers wait their turn. We want to create a program that manages this line using a queue. A queue is a data structure where the first person to join the line is the first to be served.

🎯 Goal: Build a queue using a linked list in C#. You will create nodes, add customers to the queue, remove them when served, and finally display the queue.

📋 What You'll Learn

Create a Node class with a string data field and a Node reference for the next node.

Create a Queue class with methods to enqueue (add), dequeue (remove), and display the queue.

Use linked list logic to manage the queue.

Print the queue after operations to show the current state.

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding queues and linked lists is important for software developers working on scheduling, resource management, and real-time systems.

1

Create Node and Queue Classes

Create a class called Node with a public string field data and a public Node field next. Then create a class called Queue with two private Node fields: front and rear, both initialized to null.

DSA C#

// Your code here

Hint

Think of Node as a box holding a customer's name and a pointer to the next box. The Queue keeps track of the first and last boxes.

2

Add Enqueue Method

Inside the Queue class, create a public method Enqueue that takes a string parameter data. This method should create a new Node with the given data and add it to the end of the queue. Update front and rear accordingly.

DSA C#

public class Node
{
    public string data;
    public Node next;

    public Node(string data)
    {
        this.data = data;
        this.next = null;
    }
}

public class Queue
{
    private Node front = null;
    private Node rear = null;

    // Add Enqueue method below
    // Your code here
}

Hint

When the queue is empty, both front and rear point to the new node. Otherwise, add the new node after rear and update rear.

3

Add Dequeue Method

Inside the Queue class, create a public method Dequeue that removes and returns the string data from the front node. Update front and rear accordingly. If the queue is empty, return null.

DSA C#

public class Node
{
    public string data;
    public Node next;

    public Node(string data)
    {
        this.data = data;
        this.next = null;
    }
}

public class Queue
{
    private Node front = null;
    private Node rear = null;

    public void Enqueue(string data)
    {
        Node newNode = new Node(data);
        if (rear == null)
        {
            front = newNode;
            rear = newNode;
        }
        else
        {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // Add Dequeue method below
    // Your code here
}

Hint

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

4

Add Display Method and Test Queue

Inside the Queue class, create a public method Display that prints all the data in the queue nodes separated by -> and ending with null. Then, in the Main method, create a Queue object, enqueue these strings in order: "Alice", "Bob", "Charlie". Dequeue one element, then call Display to print the current queue.

DSA C#

public class Node
{
    public string data;
    public Node next;

    public Node(string data)
    {
        this.data = data;
        this.next = null;
    }
}

public class Queue
{
    private Node front = null;
    private Node rear = null;

    public void Enqueue(string data)
    {
        Node newNode = new Node(data);
        if (rear == null)
        {
            front = newNode;
            rear = newNode;
        }
        else
        {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public string Dequeue()
    {
        if (front == null)
        {
            return null;
        }
        string result = front.data;
        front = front.next;
        if (front == null)
        {
            rear = null;
        }
        return result;
    }

    // Add Display method below
    // Your code here
}

public class Program
{
    public static void Main()
    {
        // Create Queue and test
        // Your code here
    }
}

Hint

Traverse from front to rear, printing each node's data followed by ->. End with null. Then test by adding three names, removing one, and displaying.

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