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 the back easily without rearranging the whole train.

front -> [node1] -> [node2] -> [node3] -> back -> null

Dry Run Walkthrough

Input: Start with empty dequeue, then enqueue 10 at front, enqueue 20 at back, dequeue from front, enqueue 30 at front

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

Step 1: enqueue 10 at front

front -> [10] -> back -> null

Why: First element becomes both front and back

Step 2: enqueue 20 at back

front -> [10] -> [20] -> back -> null

Why: Add new node after back to keep order

Step 3: dequeue from front

front -> [20] -> back -> null

Why: Remove front node and update front pointer

Step 4: enqueue 30 at front

front -> [30] -> [20] -> back -> null

Why: Add new node before current front

Result:

front -> [30] -> [20] -> back -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

class Dequeue {
private:
    Node* front;
    Node* back;
public:
    Dequeue() : front(nullptr), back(nullptr) {}

    void enqueueFront(int val) {
        Node* newNode = new Node(val);
        if (!front) { // empty dequeue
            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
    }

    void enqueueBack(int val) {
        Node* newNode = new Node(val);
        if (!back) { // empty dequeue
            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
    }

    int dequeueFront() {
        if (!front) return -1; // empty dequeue
        int val = front->data;
        Node* temp = front;
        front = front->next;   // move front forward
        if (front) front->prev = nullptr; // disconnect old front
        else back = nullptr;   // dequeue is empty now
        delete temp;
        return val;
    }

    int dequeueBack() {
        if (!back) return -1; // empty dequeue
        int val = back->data;
        Node* temp = back;
        back = back->prev;     // move back backward
        if (back) back->next = nullptr; // disconnect old back
        else front = nullptr;  // dequeue is empty now
        delete temp;
        return val;
    }

    void print() {
        Node* curr = front;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " -> ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    }
};

int main() {
    Dequeue dq;
    dq.enqueueFront(10);
    dq.enqueueBack(20);
    cout << "After enqueueFront(10) and enqueueBack(20):" << endl;
    dq.print();

    int val = dq.dequeueFront();
    cout << "Dequeued from front: " << val << endl;
    cout << "After dequeueFront():" << endl;
    dq.print();

    dq.enqueueFront(30);
    cout << "After enqueueFront(30):" << endl;
    dq.print();

    return 0;
}

if (!front) { front = back = newNode; return; }

handle empty dequeue by setting front and back to new node

newNode->next = front; front->prev = newNode; front = newNode;

insert new node before current front and update front pointer

if (!back) { front = back = newNode; return; }

handle empty dequeue by setting front and back to new node

back->next = newNode; newNode->prev = back; back = newNode;

insert new node after current back and update back pointer

front = front->next; if (front) front->prev = nullptr; else back = nullptr;

remove front node and update pointers accordingly

back = back->prev; if (back) back->next = nullptr; else front = nullptr;

remove back node and update pointers accordingly

Output

After enqueueFront(10) and enqueueBack(20):

10 -> 20 -> null

Dequeued from front: 10

After dequeueFront():

20 -> null

After enqueueFront(30):

30 -> 20 -> null

Complexity Analysis

Time: O(1) for all enqueue and dequeue operations because we only update pointers at ends 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, making operations at both ends faster and constant time

Edge Cases

empty dequeue

enqueue sets front and back to new node; dequeue returns -1

DSA C++

if (!front) { front = back = newNode; return; }

single element dequeue

dequeue removes the only node and sets front and back to nullptr

DSA C++

if (front) front->prev = nullptr; else back = nullptr;

dequeue after removing all elements

further dequeue returns -1 as dequeue is empty

DSA C++

if (!front) return -1;

When to Use This Pattern

When you need to add or remove items from both ends efficiently, use a dequeue with a doubly linked list to get constant time operations.

Common Mistakes

Mistake: Not updating both front and back pointers when dequeue becomes empty
Fix: Set both front and back to nullptr when last element is removed

Mistake: Forgetting to update prev or next pointers when inserting or removing nodes
Fix: Always update both next and prev pointers to maintain correct links

Summary

Implements a dequeue using a doubly linked list allowing insertions and deletions at both ends.

Use when you want fast add/remove operations from front and back without shifting elements.

The key is to keep track of front and back pointers and update next and prev links carefully.

Practice

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

easy

A. It allows insertion and deletion from both ends in O(1) time without shifting elements.

B. It uses less memory than an array.

C. It automatically sorts the elements.

D. It restricts insertion to only one end.

Solution

1. Step 1: Understand Dequeue operations

   A dequeue allows insertion and deletion from both front and rear ends.

2. Step 2: Compare linked list and array

   Linked list supports O(1) insertion/deletion at both ends without shifting, unlike arrays.

3. Final Answer:

   It allows insertion and deletion from both ends in O(1) time without shifting elements. -> Option A

4. Quick Check:

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

Hint: Linked list avoids shifting, so both ends are fast [OK]

Common Mistakes:

• Thinking arrays allow O(1) insert/delete at both ends
• Assuming linked list sorts elements automatically
• Confusing memory usage advantages

2. Which of the following is the correct syntax to insert an element at the front of a dequeue implemented using a linked list in C++?

easy

A. void insertFront(int data) { front = data; }

B. void insertFront(int data) { Node* newNode = new Node(data); newNode->next = front; front = newNode; }

C. void insertFront(int data) { front->data = data; }

D. void insertFront(int data) { delete front; front = new Node(data); }

Solution

1. Step 1: Create new node with data

   We allocate a new node and assign the data to it.

2. Step 2: Link new node to current front and update front pointer

   Set newNode->next to current front, then update front to newNode.

3. Final Answer:

   void insertFront(int data) { Node* newNode = new Node(data); newNode->next = front; front = newNode; } -> Option B

4. Quick Check:

   New node points to old front, front updated [OK]

Hint: New node next points to old front, then front updated [OK]

Common Mistakes:

• Assigning data directly to front pointer
• Deleting front before inserting
• Not linking new node to old front

3. Consider the following code snippet for a dequeue using linked list:

Dequeue dq;
dq.insertRear(10);
dq.insertFront(20);
dq.insertRear(30);
dq.deleteFront();
dq.insertFront(40);
dq.deleteRear();
dq.display();

What will be the output of dq.display()?

medium

A. 40 -> 10 -> null

B. 40 -> 20 -> 10 -> null

C. 20 -> 40 -> null

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

Solution

1. Step 1: Trace insertions and deletions step-by-step

   insertRear(10): 10 insertFront(20): 20 -> 10 insertRear(30): 20 -> 10 -> 30 deleteFront(): removes 20, now 10 -> 30 insertFront(40): 40 -> 10 -> 30 deleteRear(): removes 30, now 40 -> 10

2. Step 2: Final list after all operations

   40 -> 10 -> null

3. Final Answer:

   40 -> 10 -> null -> Option A

4. Quick Check:

   Trace insert/delete carefully for final list [OK]

Hint: Trace each operation stepwise to find final list [OK]

Common Mistakes:

• Forgetting to update front or rear after deletion
• Mixing order of insertFront and insertRear
• Assuming deleted elements remain

4. The following code snippet for deleting from rear in a dequeue using linked list has a bug:

void deleteRear() {
  if (rear == nullptr) return;
  Node* temp = front;
  while (temp->next != rear) {
    temp = temp->next;
  }
  delete rear;
  rear = temp;
  rear->next = nullptr;
}

What is the bug in this code?

medium

A. It sets rear->next to non-null value.

B. It deletes the front node instead of rear.

C. It does not handle the case when there is only one node in the dequeue.

D. It causes memory leak by not deleting any node.

Solution

1. Step 1: Analyze the loop for single node case

   If only one node exists, front == rear, so while loop condition temp->next != rear fails immediately, temp = front.

2. Step 2: Check what happens after loop

   Deleting rear node, then setting rear = temp (which is front). But if only one node, temp == rear, so deleting rear deletes the only node, then rear points to deleted memory, causing dangling pointer.

3. Final Answer:

   It does not handle the case when there is only one node in the dequeue. -> Option C

4. Quick Check:

   Single node case needs special handling [OK]

Hint: Check single-node case separately before loop [OK]

Common Mistakes:

• Ignoring single-node edge case
• Assuming loop always runs at least once
• Not updating rear pointer correctly

5. You want to implement a function reverseDequeue() that reverses the order of elements in a dequeue implemented using a linked list. Which approach is best to reverse the dequeue efficiently?

hard

A. Delete all nodes and re-insert them in reverse order.

B. Create a new linked list and insert elements from the original dequeue at the rear one by one.

C. Use an auxiliary stack to push all elements, then pop and insert back into the dequeue.

D. Traverse the linked list once, reversing the next pointers of each node, then swap front and rear pointers.

Solution

1. Step 1: Reverse linked list pointers in one traversal

   Reversing next pointers of each node in one pass efficiently reverses the list.

2. Step 2: Swap front and rear pointers

   After reversal, front and rear pointers must be swapped to reflect new ends.

3. Final Answer:

   Traverse the linked list once, reversing the next pointers of each node, then swap front and rear pointers. -> Option D

4. Quick Check:

   In-place reversal with pointer swap is most efficient [OK]

Hint: Reverse pointers in one pass, then swap front and rear [OK]

Common Mistakes:

• Using extra memory unnecessarily
• Re-inserting nodes instead of reversing pointers
• Not swapping front and rear after reversal