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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations on Linked List

What is the printed state of the dequeue after the following operations?

Operations:
1. EnqueueRear(10)
2. EnqueueRear(20)
3. EnqueueFront(5)
4. DequeueRear()
5. EnqueueFront(3)
6. DequeueFront()

DSA C#

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

public class Dequeue {
    private Node front, rear;

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

    public void EnqueueFront(int x) {
        Node temp = new Node(x);
        if (front == null) {
            front = rear = temp;
        } else {
            temp.next = front;
            front.prev = temp;
            front = temp;
        }
    }

    public void EnqueueRear(int x) {
        Node temp = new Node(x);
        if (rear == null) {
            front = rear = temp;
        } else {
            rear.next = temp;
            temp.prev = rear;
            rear = temp;
        }
    }

    public void DequeueFront() {
        if (front == null) return;
        if (front == rear) {
            front = rear = null;
        } else {
            front = front.next;
            front.prev = null;
        }
    }

    public void DequeueRear() {
        if (rear == null) return;
        if (front == rear) {
            front = rear = null;
        } else {
            rear = rear.prev;
            rear.next = null;
        }
    }

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

Dequeue dq = new Dequeue();
dq.EnqueueRear(10);
dq.EnqueueRear(20);
dq.EnqueueFront(5);
dq.DequeueRear();
dq.EnqueueFront(3);
dq.DequeueFront();
string output = dq.Print();
Console.WriteLine(output);

A 3 -> 5 -> null

B 3 -> 5 -> 10 -> null

C 5 -> 10 -> null

D 5 -> 10 -> 20 -> null

💡 Hint

Trace each operation step-by-step, updating the front and rear pointers.

After all operations, the dequeue contains nodes with values 5 and 10 in that order from front to rear.

🧠 Conceptual

intermediate

Understanding Dequeue Front and Rear Removal

In a dequeue implemented using a doubly linked list, what happens when you perform DequeueFront() on a dequeue with only one element?

A Both front and rear pointers become null, making the dequeue empty.

B Only the front pointer becomes null; rear remains pointing to the removed node.

C Only the rear pointer becomes null; front remains pointing to the removed node.

D The dequeue throws an error because it cannot remove the only element.

💡 Hint

Think about what it means for the dequeue to be empty after removing the only element.

When the only element is removed, both front and rear must be set to null to indicate the dequeue is empty.

🔧 Debug

advanced

Identify the Bug in DequeueRear Method

What error will occur when running the following DequeueRear method if the dequeue has only one element?

DSA C#

public void DequeueRear() {
    if (rear == null) return;
    rear = rear.prev;
    rear.next = null;
}

A No error; the method works correctly for all cases.

B StackOverflowException due to infinite recursion.

C IndexOutOfRangeException due to invalid pointer access.

D NullReferenceException because rear becomes null and rear.next is accessed.

💡 Hint

Consider what happens when rear.prev is null.

If the dequeue has one element, rear.prev is null, so rear becomes null. Then rear.next causes a NullReferenceException.

❓ Predict Output

advanced

Result of Mixed Enqueue and Dequeue Operations

What is the printed state of the dequeue after these operations?

Operations:
EnqueueFront(1)
EnqueueRear(2)
EnqueueRear(3)
DequeueFront()
DequeueRear()
EnqueueFront(4)
EnqueueRear(5)

DSA C#

Dequeue dq = new Dequeue();
dq.EnqueueFront(1);
dq.EnqueueRear(2);
dq.EnqueueRear(3);
dq.DequeueFront();
dq.DequeueRear();
dq.EnqueueFront(4);
dq.EnqueueRear(5);
string output = dq.Print();
Console.WriteLine(output);

A 4 -> 5 -> null

B 4 -> 2 -> 5 -> null

C 1 -> 2 -> 3 -> null

D 2 -> 4 -> 5 -> null

💡 Hint

Track the front and rear after each operation carefully.

After all operations, the dequeue contains 4 at front, then 2, then 5 at rear.

🧠 Conceptual

expert

Why Use Doubly Linked List for Dequeue Implementation?

Why is a doubly linked list preferred over a singly linked list for implementing a dequeue?

A Because it allows efficient insertion and deletion at both front and rear in O(1) time.

B Because doubly linked lists use less memory than singly linked lists.

C Because singly linked lists cannot store integer data efficiently.

D Because singly linked lists do not support traversal.

💡 Hint

Think about operations at both ends of the dequeue.

Doubly linked lists have pointers to both next and previous nodes, enabling O(1) insertions and deletions at both ends.

Practice

1. What is the main advantage of implementing a Dequeue using a linked list compared to an array?

easy

A. It automatically sorts the elements.

B. It uses less memory than an array.

C. It allows insertion and deletion from both ends in constant time.

D. It prevents duplicate elements.

Solution

1. Step 1: Understand Dequeue operations

   A dequeue allows adding and removing elements from both front and rear ends.

2. Step 2: Compare linked list vs array

   Linked list supports constant time insertion and deletion at both ends, unlike arrays which may require shifting elements.

3. Final Answer:

   It allows insertion and deletion from both ends in constant time. -> Option C

4. Quick Check:

   Linked list dequeue = O(1) insert/delete both ends [OK]

Hint: Linked list supports fast add/remove at both ends [OK]

Common Mistakes:

• Thinking arrays allow O(1) insertion at front
• Confusing memory usage advantage
• Assuming automatic sorting

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

easy

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

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

C. class Node { public int data; Node next; Node prev; }

D. public struct Node { int data; Node next; Node prev; }

Solution

1. Step 1: Check access modifiers and fields

   For linked list nodes, fields should be public to access from dequeue class.

2. Step 2: Verify presence of next and prev pointers

   Doubly linked list nodes need both next and prev references.

3. Final Answer:

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

4. Quick Check:

   Public fields + next + prev = correct node class [OK]

Hint: Node needs public data, next, and prev for dequeue [OK]

Common Mistakes:

• Missing public keyword for fields
• Using struct instead of class
• Omitting prev pointer

3. Consider the following C# code snippet implementing a dequeue using a linked list. What will be printed after these operations?

Dequeue dq = new Dequeue();
dq.InsertFront(10);
dq.InsertRear(20);
dq.InsertFront(5);
dq.DeleteRear();
dq.Display();

medium

A. 5 -> 10 -> 20 -> null

B. 10 -> 5 -> null

C. 10 -> 20 -> null

D. 5 -> 10 -> null

Solution

1. Step 1: Trace insertions

   InsertFront(10) adds 10 at front: 10 -> null InsertRear(20) adds 20 at rear: 10 -> 20 -> null InsertFront(5) adds 5 at front: 5 -> 10 -> 20 -> null

2. Step 2: Trace deletion and display

   DeleteRear() removes 20 from rear: 5 -> 10 -> null Display prints elements from front to rear.

3. Final Answer:

   5 -> 10 -> null -> Option D

4. Quick Check:

   After delete rear, list = 5 -> 10 [OK]

Hint: Track insert/delete order carefully [OK]

Common Mistakes:

• Forgetting delete rear removes last element
• Mixing front and rear insertions
• Incorrect display order

4. The following C# method is intended to delete the front node of a dequeue implemented using a doubly linked list. What is the error?

public void DeleteFront() {
    if (front == null) return;
    front = front.next;
    front.prev = null;
}

medium

A. It does not handle the case when the list becomes empty after deletion.

B. It should update rear pointer instead of front.

C. It should set front.next to null before updating.

D. It should not set front.prev to null.

Solution

1. Step 1: Analyze deletion steps

   After moving front to front.next, if front becomes null (list empty), front.prev = null causes NullReferenceException.

2. Step 2: Identify missing null check

   Code must check if front is null before setting front.prev = null to avoid error.

3. Final Answer:

   It does not handle the case when the list becomes empty after deletion. -> Option A

4. Quick Check:

   Null check needed after front update [OK]

Hint: Check for empty list after deletion [OK]

Common Mistakes:

• Ignoring null after front update
• Updating rear pointer incorrectly
• Setting pointers in wrong order

5. You want to implement a method ReverseDisplay() for a dequeue using a doubly linked list that prints elements from rear to front. Which approach is correct?

hard

A. Start from rear node and traverse using prev pointers until null, printing each node's data.

B. Start from front node and traverse using next pointers until null, printing each node's data.

C. Use recursion starting from front node to print in reverse order.

D. Swap front and rear pointers and then traverse from front using next pointers.

Solution

1. Step 1: Understand doubly linked list structure

   Each node has next and prev pointers; rear node's next is null, front node's prev is null.

2. Step 2: Reverse traversal logic

   To print from rear to front, start at rear and move backward using prev pointers until null.

3. Final Answer:

   Start from rear node and traverse using prev pointers until null, printing each node's data. -> Option A

4. Quick Check:

   Traverse backward from rear using prev [OK]

Hint: Traverse prev pointers from rear to front [OK]

Common Mistakes:

• Traversing next pointers from front for reverse
• Swapping pointers incorrectly
• Using recursion unnecessarily