Double Ended Queue Deque in DSA C#

Mental Model

A deque lets you add or remove items from both ends easily, like a line where people can join or leave from front or back.

Analogy: Imagine a hallway where people can enter or exit from either door at the front or the back, not just one side.

front -> [item1] -> [item2] -> [item3] -> back
↑ front pointer
↑ back pointer

Dry Run Walkthrough

Input: Start with empty deque, add 1 at front, add 2 at back, remove from front, add 3 at front

Goal: Show how items are added and removed from both ends and how the deque changes

Step 1: Add 1 at front

front -> [1] -> back
↑ front pointer
↑ back pointer

Why: Deque was empty, so front and back both point to the new item

Step 2: Add 2 at back

front -> [1] -> [2] -> back
↑ front pointer
↑ back pointer

Why: Add new item after back, update back pointer to new item

Step 3: Remove from front

front -> [2] -> back
↑ front pointer
↑ back pointer

Why: Remove first item, front pointer moves to next item

Step 4: Add 3 at front

front -> [3] -> [2] -> back
↑ front pointer
↑ back pointer

Why: Add new item before front, update front pointer

Result:

front -> [3] -> [2] -> back

Annotated Code

DSA C#

using System;

public class DequeNode
{
    public int Value;
    public DequeNode Prev;
    public DequeNode Next;

    public DequeNode(int value)
    {
        Value = value;
        Prev = null;
        Next = null;
    }
}

public class Deque
{
    private DequeNode front;
    private DequeNode back;

    public Deque()
    {
        front = null;
        back = null;
    }

    public void AddFront(int value)
    {
        DequeNode newNode = new DequeNode(value);
        if (front == null) // empty deque
        {
            front = back = 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 AddBack(int value)
    {
        DequeNode newNode = new DequeNode(value);
        if (back == null) // empty deque
        {
            front = back = newNode;
            return;
        }
        back.Next = newNode; // link current back to new node
        newNode.Prev = back; // link new node back to current back
        back = newNode; // update back pointer
    }

    public int? RemoveFront()
    {
        if (front == null) return null; // empty deque
        int val = front.Value;
        front = front.Next; // move front pointer forward
        if (front != null)
            front.Prev = null; // disconnect old front
        else
            back = null; // deque became empty
        return val;
    }

    public int? RemoveBack()
    {
        if (back == null) return null; // empty deque
        int val = back.Value;
        back = back.Prev; // move back pointer backward
        if (back != null)
            back.Next = null; // disconnect old back
        else
            front = null; // deque became empty
        return val;
    }

    public override string ToString()
    {
        DequeNode curr = front;
        string result = "";
        while (curr != null)
        {
            result += curr.Value + " -> ";
            curr = curr.Next;
        }
        result += "null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        Deque deque = new Deque();
        deque.AddFront(1); // step 1
        deque.AddBack(2);  // step 2
        deque.RemoveFront(); // step 3
        deque.AddFront(3); // step 4
        Console.WriteLine(deque.ToString());
    }
}

if (front == null) // empty deque

check if deque is empty to initialize front and back pointers

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

connect new node before current front to add at front

front = newNode; // update front pointer

move front pointer to new node after adding at front

if (back == null) // empty deque

check if deque is empty to initialize front and back pointers

back.Next = newNode; // link current back to new node

connect new node after current back to add at back

back = newNode; // update back pointer

move back pointer to new node after adding at back

front = front.Next; // move front pointer forward

remove front node by moving front pointer forward

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

disconnect old front node to avoid dangling pointer

back = back.Prev; // move back pointer backward

remove back node by moving back pointer backward

if (back != null) back.Next = null; // disconnect old back

disconnect old back node to avoid dangling pointer

Output

3 -> 2 -> null

Complexity Analysis

Time: O(1) for add and remove operations because we only change pointers at ends without traversing

Space: O(n) because we store n elements in nodes linked by pointers

vs Alternative: Compared to a normal queue that only allows one end insertion/removal, deque supports both ends with same O(1) cost

Edge Cases

empty deque

Add operations initialize front and back pointers; remove operations return null safely

DSA C#

if (front == null) // empty deque

deque with single element

Removing front or back empties deque and resets pointers to null

DSA C#

else
    back = null; // deque became empty

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, use a deque to handle both ends in constant time.

Common Mistakes

Mistake: Not updating both front and back pointers when deque becomes empty after removal
Fix: Set both front and back to null when last element is removed

Mistake: Forgetting to disconnect old nodes' pointers after removal causing memory leaks or bugs
Fix: Set removed node's Prev or Next to null after pointer updates

Summary

A deque lets you add or remove items from both front and back ends efficiently.

Use it when you need flexible insertion and deletion at both ends of a list.

The key is to keep track of front and back pointers and update them carefully on each operation.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A data structure where elements can be added or removed from both ends

B. A queue where elements can only be added at the rear

C. A stack where elements are added and removed from the top only

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows insertion and deletion at both front and rear ends, unlike a queue or stack.

2. Step 2: Compare with other data structures

   Queue restricts insertion to rear and deletion from front; stack restricts both to one end.

3. Final Answer:

   A data structure where elements can be added or removed from both ends -> Option A

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Deque means double-ended queue, both ends usable [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque allows random access
• Assuming insertion only at one end

2. Which of the following is the correct way to declare a Deque of integers in C# using System.Collections.Generic?

easy

A. LinkedList<int> dq = new LinkedList<int>();

B. Queue<int> dq = new Queue<int>();

C. Deque<int> dq = new Deque<int>();

D. List<int> dq = new List<int>();

Solution

1. Step 1: Recall C# standard library support for Deque

   C# does not have a built-in Deque class, but LinkedList can be used as a deque.

2. Step 2: Analyze options

   Deque<int> dq = new Deque<int>(); is invalid as Deque class does not exist; Queue<int> dq = new Queue<int>(); is a queue, not deque; List<int> dq = new List<int>(); is a list, not deque.

3. Final Answer:

   LinkedList<int> dq = new LinkedList<int>(); -> Option A

4. Quick Check:

   LinkedList supports deque operations [OK]

Hint: Use LinkedList for deque in C# as no built-in Deque [OK]

Common Mistakes:

• Trying to use non-existent Deque class
• Using Queue which is single-ended
• Using List which lacks efficient front operations

3. What will be the output of the following C# code snippet?

var dq = new LinkedList<int>();
dq.AddLast(10);
dq.AddFirst(20);
dq.AddLast(30);
dq.RemoveFirst();
foreach(var item in dq) Console.Write(item + " ");

medium

A. 20 10 30

B. 30 10

C. 20 30

D. 10 30

Solution

1. Step 1: Trace the additions to the deque

   Added 10 at last: [10]; Added 20 at first: [20, 10]; Added 30 at last: [20, 10, 30]

2. Step 2: Remove first element

   RemoveFirst removes 20; deque becomes [10, 30]

3. Step 3: Print elements

   Output is "10 30 "

4. Final Answer:

   10 30 -> Option D

5. Quick Check:

   After RemoveFirst, deque = 10 30 [OK]

Hint: AddFirst adds front, RemoveFirst removes front [OK]

Common Mistakes:

• Confusing AddFirst and AddLast positions
• Forgetting RemoveFirst removes front element
• Assuming RemoveFirst removes last element

4. Identify the error in the following C# code using LinkedList as a deque:

var dq = new LinkedList<int>();
dq.AddFirst(5);
dq.RemoveLast();
dq.RemoveLast();
Console.WriteLine(dq.Count);

medium

A. No error, output is 0

B. InvalidOperationException at second RemoveLast call

C. Compile-time error due to RemoveLast misuse

D. Output is 1

Solution

1. Step 1: Trace the operations on deque

   Added 5 at front: deque = [5]; RemoveLast removes 5: deque = []

2. Step 2: Second RemoveLast on empty deque

   Calling RemoveLast on empty LinkedList throws InvalidOperationException

3. Final Answer:

   InvalidOperationException at second RemoveLast call -> Option B

4. Quick Check:

   Removing from empty deque throws exception [OK]

Hint: Removing from empty deque causes exception [OK]

Common Mistakes:

• Assuming RemoveLast on empty deque does nothing
• Expecting output 0 instead of exception
• Confusing compile-time and runtime errors

5. You want to implement a task scheduler using a deque where urgent tasks are added to the front and normal tasks to the rear. Which sequence of operations correctly adds urgent task 1, normal task 2, urgent task 3, then removes one task from the front?

var dq = new LinkedList<int>();
// Fill in operations below

hard

A. dq.AddFirst(1); dq.AddFirst(2); dq.AddLast(3); dq.RemoveLast();

B. dq.AddLast(1); dq.AddFirst(2); dq.AddLast(3); dq.RemoveLast();

C. dq.AddFirst(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst();

D. dq.AddLast(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst();

Solution

1. Step 1: Add urgent tasks to front and normal tasks to rear

   Urgent task 1: AddFirst(1); Normal task 2: AddLast(2); Urgent task 3: AddFirst(3)

2. Step 2: Remove one task from front

   RemoveFirst removes the front urgent task 3

3. Final Answer:

   dq.AddFirst(1); dq.AddLast(2); dq.AddFirst(3); dq.RemoveFirst(); -> Option C

4. Quick Check:

   Urgent front, normal rear, remove front [OK]

Hint: Urgent = AddFirst, Normal = AddLast, Remove from front [OK]

Common Mistakes:

• Mixing AddFirst and AddLast for task priority
• Removing from wrong end
• Incorrect order of operations