Dequeue Using Linked List in DSA C#

Mental Model

A dequeue lets you add or remove items from both ends quickly using a linked list.

Analogy: Think of a train where you can add or remove cars from the front or back without rearranging the whole train.

null ← 10 ↔ 20 ↔ 30 -> null
↑front                 ↑rear

Dry Run Walkthrough

Input: Start with empty dequeue, then add 10 at rear, add 20 at front, add 30 at rear, remove from front, remove from rear

Goal: Show how elements are added and removed from both ends using linked list pointers

Step 1: Add 10 at rear on empty dequeue

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

Why: First element becomes both front and rear

Step 2: Add 20 at front

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

Why: New node links before current front and becomes new front

Step 3: Add 30 at rear

null ← 20 ↔ 10 ↔ [30] -> null
↑front           ↑rear

Why: New node links after current rear and becomes new rear

Step 4: Remove from front (remove 20)

null ← [10] ↔ 30 -> null
↑front       ↑rear

Why: Front moves to next node, old front is removed

Step 5: Remove from rear (remove 30)

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

Why: Rear moves to previous node, old rear is removed

Result:

null ← 10 -> null
↑front ↑rear

Annotated Code

DSA C#

using System;

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

public class Dequeue
{
    private Node front, rear;

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

    public void AddFront(int val)
    {
        Node newNode = new Node(val);
        if (front == null)
        {
            front = rear = newNode;
            return;
        }
        newNode.next = front; // link new node to current front
        front.prev = newNode; // link current front back to new node
        front = newNode;      // update front pointer
    }

    public void AddRear(int val)
    {
        Node newNode = new Node(val);
        if (rear == null)
        {
            front = rear = newNode;
            return;
        }
        rear.next = newNode;  // link current rear to new node
        newNode.prev = rear;  // link new node back to current rear
        rear = newNode;       // update rear pointer
    }

    public int RemoveFront()
    {
        if (front == null) throw new InvalidOperationException("Dequeue is empty");
        int val = front.data;
        front = front.next;   // move front forward
        if (front != null) front.prev = null; // disconnect old front
        else rear = null;     // if empty now, rear also null
        return val;
    }

    public int RemoveRear()
    {
        if (rear == null) throw new InvalidOperationException("Dequeue is empty");
        int val = rear.data;
        rear = rear.prev;     // move rear backward
        if (rear != null) rear.next = null; // disconnect old rear
        else front = null;    // if empty now, front also null
        return val;
    }

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

class Program
{
    static void Main()
    {
        Dequeue dq = new Dequeue();
        dq.AddRear(10);
        dq.AddFront(20);
        dq.AddRear(30);
        Console.WriteLine(dq.ToString());
        dq.RemoveFront();
        Console.WriteLine(dq.ToString());
        dq.RemoveRear();
        Console.WriteLine(dq.ToString());
    }
}

newNode.next = front; // link new node to current front

link new node before current front to insert at front

front.prev = newNode; // link current front back to new node

connect current front back pointer to new node

front = newNode; // update front pointer

update front pointer to new node

rear.next = newNode; // link current rear to new node

link current rear forward pointer to new node

newNode.prev = rear; // link new node back to current rear

connect new node back pointer to current rear

rear = newNode; // update rear pointer

update rear pointer to new node

front = front.next; // move front forward

advance front pointer to next node to remove front

if (front != null) front.prev = null; // disconnect old front

disconnect old front's backward link

rear = rear.prev; // move rear backward

move rear pointer backward to remove rear

if (rear != null) rear.next = null; // disconnect old rear

disconnect old rear's forward link

Output

20 -> 10 -> 30 -> null

10 -> 30 -> null

10 -> null

Complexity Analysis

Time: O(1) for all add and remove operations because pointers are updated directly without traversal

Space: O(n) because each element is stored in a node linked by pointers

vs Alternative: Compared to array-based dequeue, linked list avoids shifting elements and allows constant time insertions/removals at both ends

Edge Cases

Empty dequeue when removing front or rear

Throws InvalidOperationException to signal no elements to remove

DSA C#

if (front == null) throw new InvalidOperationException("Dequeue is empty");

Removing last element makes dequeue empty

Both front and rear pointers set to null to reflect empty state

DSA C#

else rear = null; // if empty now, rear also null

Adding first element to empty dequeue

Both front and rear point to the new single node

DSA C#

if (front == null) { front = rear = newNode; return; }

When to Use This Pattern

When a problem needs fast insertions and deletions at both ends, use a dequeue with a doubly linked list to keep operations in constant time.

Common Mistakes

Mistake: Not updating both prev and next pointers when adding or removing nodes
Fix: Always update both forward and backward links to keep the list consistent

Mistake: Not handling empty dequeue case when removing elements
Fix: Check if front or rear is null before removing and handle empty state properly

Summary

Implements a dequeue using a doubly linked list allowing add/remove at both ends.

Use when you need quick insertions and deletions from front and rear without shifting elements.

The key is to update both next and prev pointers and keep track of front and rear nodes.

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