Enqueue Using Linked List in DSA C#

Mental Model

Add new items to the end of a line so the first who came stays first. We keep track of the last item to add quickly.

Analogy: Imagine a queue of people waiting to buy tickets. New people join at the end, and the person at the front is served first. We remember who is last to add new people fast.

front -> 1 -> 2 -> 3 -> null ← rear
↑

Dry Run Walkthrough

Input: queue: 1 -> 2 -> 3 -> null, enqueue value 4

Goal: Add value 4 to the end of the queue so it becomes 1 -> 2 -> 3 -> 4 -> null

Step 1: Create new node with value 4

front -> 1 -> 2 -> 3 -> null ← rear
newNode(4) isolated

Why: We need a new node to add to the queue

Step 2: Link current rear node (3) to new node (4)

front -> 1 -> 2 -> 3 -> [rear->4] -> null
↑

Why: Attach new node at the end to keep queue order

Step 3: Update rear pointer to new node (4)

front -> 1 -> 2 -> 3 -> 4 -> null ← rear
↑

Why: Rear must point to the last node for future enqueues

Result:

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Annotated Code

DSA C#

using System;

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

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

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

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

    public void PrintQueue()
    {
        Node curr = front;
        while (curr != null)
        {
            Console.Write(curr.data);
            if (curr.next != null) Console.Write(" -> ");
            curr = curr.next;
        }
        Console.WriteLine(" -> null");
    }
}

public class Program
{
    public static void Main()
    {
        Queue q = new Queue();
        q.Enqueue(1);
        q.Enqueue(2);
        q.Enqueue(3);
        q.Enqueue(4); // enqueue value 4
        q.PrintQueue();
    }
}

Node newNode = new Node(value); // create new node

create a new node to add to the queue

if (rear == null) // queue empty

check if queue is empty to initialize front and rear

front = newNode; // front and rear both point to new node

set front to new node when queue was empty

rear = newNode; // update rear pointer

set rear to new node when queue was empty or after linking

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

link new node after current rear to keep order

Output

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) because we add the new node directly at the rear without traversing the queue

Space: O(1) because we only create one new node for each enqueue operation

vs Alternative: Compared to using an array where adding at the end might require resizing or shifting, linked list enqueue is faster and uses constant time

Edge Cases

empty queue

front and rear both point to the new node

DSA C#

if (rear == null) // queue empty

single element queue

rear.next links new node, rear updates to new node

DSA C#

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

When to Use This Pattern

When you need to add items to the end of a queue efficiently, use the enqueue linked list pattern to keep track of the rear pointer for O(1) insertion.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always set rear = newNode after linking to keep rear at the last node

Mistake: Not handling empty queue case where front and rear are null
Fix: Check if rear is null and set both front and rear to new node

Summary

Adds a new element to the end of a queue implemented with a linked list.

Use when you want fast insertion at the end of a queue without shifting elements.

Keep track of the rear pointer to add new nodes in constant time.

Practice

1. What does the Enqueue operation do in a linked list implementation of a queue?

easy

A. Adds an element at the front of the linked list

B. Removes an element from the front of the linked list

C. Deletes the last element of the linked list

D. Adds an element at the end of the linked list

Solution

1. Step 1: Understand enqueue operation

   Enqueue means adding an element to the queue.

2. Step 2: Identify linked list behavior for enqueue

   In a linked list queue, enqueue adds the new node at the end (tail).

3. Final Answer:

   Adds an element at the end of the linked list -> Option D

4. Quick Check:

   Enqueue = Add at tail [OK]

Hint: Enqueue always adds at the tail in linked list queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue operation
• Adding element at the front instead of the end
• Thinking enqueue removes elements

2. Which of the following is the correct syntax to create a new node and enqueue it in a linked list queue in C#?

easy

A. Node newNode = new Node(data); tail.next = newNode; tail = newNode;

B. Node newNode = Node(data); tail.next = newNode; tail = newNode;

C. Node newNode = new Node(); tail = newNode; tail.next = data;

D. Node newNode = new Node(data); head.next = newNode; head = newNode;

Solution

1. Step 1: Create new node with data

   Use 'new Node(data)' to create a node with the given data.

2. Step 2: Link new node at tail and update tail

   Set 'tail.next = newNode' and then update 'tail = newNode' to keep tail at last node.

3. Final Answer:

   Node newNode = new Node(data); tail.next = newNode; tail = newNode; -> Option A

4. Quick Check:

   Correct node creation and tail update [OK]

Hint: Use 'new' keyword and update tail pointer [OK]

Common Mistakes:

• Forgetting 'new' keyword when creating node
• Updating head instead of tail
• Assigning data to next pointer

3. What will be the state of the queue after executing the following C# code?

QueueLinkedList queue = new QueueLinkedList();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);

Assuming the queue prints elements from head to tail.

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 20 -> 30 -> 10 -> null

Solution

1. Step 1: Enqueue 10, 20, 30 in order

   Each enqueue adds element at the tail, so order is 10, then 20, then 30.

2. Step 2: Print queue from head to tail

   Head points to 10, followed by 20, then 30, ending with null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Enqueue order preserved from head to tail [OK]

Hint: Enqueue adds at tail, print from head to tail [OK]

Common Mistakes:

• Reversing the order of elements
• Confusing head and tail pointers
• Assuming enqueue adds at head

4. Identify the error in the following enqueue method for a linked list queue in C#:

public void Enqueue(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
    } else {
        tail.next = newNode;
    }
}

medium

A. New node should be created outside the method

B. The tail pointer is not updated after adding new node

C. The head pointer should be updated instead of tail

D. The if condition should check tail instead of head

Solution

1. Step 1: Check tail update after enqueue

   After adding newNode at tail.next, tail must be updated to newNode.

2. Step 2: Identify missing tail update

   Code does not update tail, so tail still points to old last node, causing errors.

3. Final Answer:

   The tail pointer is not updated after adding new node -> Option B

4. Quick Check:

   Always update tail after enqueue [OK]

Hint: Update tail pointer after adding new node [OK]

Common Mistakes:

• Forgetting to update tail pointer
• Updating head instead of tail
• Creating node outside enqueue method

5. Given a linked list queue with elements 5 -> 15 -> 25 -> null, what will be the queue state after enqueueing 35 and then dequeueing one element?

hard

A. 25 -> 35 -> null

B. 5 -> 15 -> 25 -> 35 -> null

C. 15 -> 25 -> 35 -> null

D. 35 -> 5 -> 15 -> 25 -> null

Solution

1. Step 1: Enqueue 35 at tail

   Queue becomes 5 -> 15 -> 25 -> 35 -> null after enqueue.

2. Step 2: Dequeue removes from head

   Removing 5 from head leaves 15 -> 25 -> 35 -> null.

3. Final Answer:

   15 -> 25 -> 35 -> null -> Option C

4. Quick Check:

   Enqueue adds tail, dequeue removes head [OK]

Hint: Enqueue tail, dequeue head to update queue [OK]

Common Mistakes:

• Removing from tail instead of head
• Not updating head after dequeue
• Adding new element at head instead of tail