Dequeue Using Linked List in DSA C# - Build from Scratch

Dequeue Using Linked List

📖 Scenario: Imagine you are managing a line of people waiting for a ride at an amusement park. Sometimes people join the line at the front or the back, and sometimes people leave from the front or the back. This line is like a dequeue (double-ended queue) where you can add or remove from both ends.

🎯 Goal: You will build a simple Dequeue using a linked list in C#. You will create the linked list nodes, set up the dequeue, add elements to the front and back, remove elements from the front and back, and finally print the current state of the dequeue.

📋 What You'll Learn

Create a linked list node class called Node with an integer value and a reference to the next and previous nodes.

Create a Dequeue class with methods to add to front, add to back, remove from front, and remove from back.

Use the linked list nodes to maintain the order of elements in the dequeue.

Print the dequeue elements from front to back showing the current state.

💡 Why This Matters

🌍 Real World

Dequeue structures are used in real-world applications like task scheduling, undo-redo operations, and managing buffers where elements need to be added or removed from both ends efficiently.

💼 Career

Understanding how to implement and use dequeue with linked lists is important for software developers working on performance-critical applications, system programming, and interview coding challenges.

1

Create the Node class and Dequeue class with head and tail

Create a class called Node with an integer Value, and two Node references called Next and Prev. Then create a class called Dequeue with two Node variables called Head and Tail, both initialized to null.

DSA C#

// Create Node class with Value, Next, Prev
// Create Dequeue class with Head and Tail

Hint

Think of Node as a box holding a number and links to the next and previous boxes. The Dequeue keeps track of the first and last boxes.

2

Add methods to add nodes to front and back

Inside the Dequeue class, add two methods: AddFront(int value) and AddBack(int value). These methods create a new Node with the given value and add it to the front or back of the dequeue, updating Head and Tail accordingly.

DSA C#

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

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

public class Dequeue
{
    public Node Head = null;
    public Node Tail = null;

    // Add AddFront method here
    // Add AddBack method here
}

Hint

When adding to the front, link the new node before the current head. When adding to the back, link the new node after the current tail.

3

Add methods to remove nodes from front and back

Inside the Dequeue class, add two methods: RemoveFront() and RemoveBack(). These methods remove the node from the front or back of the dequeue and update Head and Tail accordingly. If the dequeue is empty, do nothing.

DSA C#

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

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

public class Dequeue
{
    public Node Head = null;
    public Node Tail = null;

    public void AddFront(int value)
    {
        Node newNode = new Node(value);
        if (Head == null)
        {
            Head = newNode;
            Tail = newNode;
        }
        else
        {
            newNode.Next = Head;
            Head.Prev = newNode;
            Head = newNode;
        }
    }

    public void AddBack(int value)
    {
        Node newNode = new Node(value);
        if (Tail == null)
        {
            Head = newNode;
            Tail = newNode;
        }
        else
        {
            Tail.Next = newNode;
            newNode.Prev = Tail;
            Tail = newNode;
        }
    }

    // Add RemoveFront method here
    // Add RemoveBack method here
}

Hint

When removing from front, move the head forward and clear the previous link. When removing from back, move the tail backward and clear the next link. Handle empty and single-node cases carefully.

4

Print the dequeue from front to back

Add a method PrintDequeue() inside the Dequeue class that prints all node values from Head to Tail separated by -> and ending with null. Then create a Main method to test adding and removing nodes and print the dequeue after operations.

DSA C#

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

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

public class Dequeue
{
    public Node Head = null;
    public Node Tail = null;

    public void AddFront(int value)
    {
        Node newNode = new Node(value);
        if (Head == null)
        {
            Head = newNode;
            Tail = newNode;
        }
        else
        {
            newNode.Next = Head;
            Head.Prev = newNode;
            Head = newNode;
        }
    }

    public void AddBack(int value)
    {
        Node newNode = new Node(value);
        if (Tail == null)
        {
            Head = newNode;
            Tail = newNode;
        }
        else
        {
            Tail.Next = newNode;
            newNode.Prev = Tail;
            Tail = newNode;
        }
    }

    public void RemoveFront()
    {
        if (Head == null) return;
        if (Head == Tail)
        {
            Head = null;
            Tail = null;
        }
        else
        {
            Head = Head.Next;
            Head.Prev = null;
        }
    }

    public void RemoveBack()
    {
        if (Tail == null) return;
        if (Head == Tail)
        {
            Head = null;
            Tail = null;
        }
        else
        {
            Tail = Tail.Prev;
            Tail.Next = null;
        }
    }

    // Add PrintDequeue method here
}

class Program
{
    static void Main()
    {
        Dequeue dq = new Dequeue();
        // Add test operations here
    }
}

Hint

Traverse from Head to Tail, printing each node's value followed by -> . End with null. Test by adding and removing nodes, then print.

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