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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations

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

Operations:
1. Insert 10 at rear
2. Insert 20 at front
3. Insert 30 at rear
4. Delete from front
5. Insert 40 at front
6. Delete from rear

DSA C++

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

class Dequeue {
    Node* front;
    Node* rear;
public:
    Dequeue() : front(nullptr), rear(nullptr) {}
    void insertFront(int x) {
        Node* temp = new Node(x);
        if (!front) {
            front = rear = temp;
        } else {
            temp->next = front;
            front->prev = temp;
            front = temp;
        }
    }
    void insertRear(int x) {
        Node* temp = new Node(x);
        if (!rear) {
            front = rear = temp;
        } else {
            rear->next = temp;
            temp->prev = rear;
            rear = temp;
        }
    }
    void deleteFront() {
        if (!front) return;
        Node* temp = front;
        front = front->next;
        if (front) front->prev = nullptr;
        else rear = nullptr;
        delete temp;
    }
    void deleteRear() {
        if (!rear) return;
        Node* temp = rear;
        rear = rear->prev;
        if (rear) rear->next = nullptr;
        else front = nullptr;
        delete temp;
    }
    void print() {
        Node* temp = front;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    Dequeue dq;
    dq.insertRear(10);
    dq.insertFront(20);
    dq.insertRear(30);
    dq.deleteFront();
    dq.insertFront(40);
    dq.deleteRear();
    dq.print();
    return 0;
}

A 20 -> 10 -> 30 -> null

B 40 -> 10 -> null

C 10 -> 30 -> null

D 40 -> 20 -> 10 -> null

💡 Hint

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

After all operations, the dequeue contains 40 at front and 10 at rear. The sequence is 40 -> 10 -> null.

🧠 Conceptual

intermediate

Understanding Dequeue Front and Rear Pointers

In a dequeue implemented using a doubly linked list, which statement is TRUE about the front and rear pointers after deleting the last element?

A Both front and rear pointers become nullptr

B Front pointer points to the last node, rear becomes nullptr

C Both front and rear pointers remain unchanged

D Rear pointer points to the last node, front becomes nullptr

💡 Hint

Think about what happens when the dequeue becomes empty.

When the last element is deleted, the dequeue is empty, so both front and rear pointers must be set to nullptr to indicate emptiness.

🔧 Debug

advanced

Identify the Bug in Dequeue Insert Front Method

What error will occur when running this insertFront method in a dequeue implemented with a doubly linked list?

DSA C++

void insertFront(int x) {
    Node* temp = new Node(x);
    if (!front) {
        front = temp;
    } else {
        temp->next = front;
        front->prev = temp;
        front = temp;
    }
}

A No error, code works correctly

B Memory leak due to missing delete

C Null pointer dereference on front->prev assignment

D Rear pointer remains nullptr causing errors on rear operations

💡 Hint

Check what happens when the dequeue is initially empty.

When the dequeue is empty, rear pointer is not set, so rear remains nullptr causing errors when rear operations are called.

❓ Predict Output

advanced

Result of Mixed Dequeue Operations

What is the output after performing these operations on an empty dequeue?
1. insertRear(5)
2. insertRear(15)
3. insertFront(25)
4. deleteRear()
5. insertFront(35)
6. deleteFront()
7. insertRear(45)
Print the dequeue from front to rear.

DSA C++

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

class Dequeue {
    Node* front;
    Node* rear;
public:
    Dequeue() : front(nullptr), rear(nullptr) {}
    void insertFront(int x) {
        Node* temp = new Node(x);
        if (!front) {
            front = rear = temp;
        } else {
            temp->next = front;
            front->prev = temp;
            front = temp;
        }
    }
    void insertRear(int x) {
        Node* temp = new Node(x);
        if (!rear) {
            front = rear = temp;
        } else {
            rear->next = temp;
            temp->prev = rear;
            rear = temp;
        }
    }
    void deleteFront() {
        if (!front) return;
        Node* temp = front;
        front = front->next;
        if (front) front->prev = nullptr;
        else rear = nullptr;
        delete temp;
    }
    void deleteRear() {
        if (!rear) return;
        Node* temp = rear;
        rear = rear->prev;
        if (rear) rear->next = nullptr;
        else front = nullptr;
        delete temp;
    }
    void print() {
        Node* temp = front;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "null" << std::endl;
    }
};

int main() {
    Dequeue dq;
    dq.insertRear(5);
    dq.insertRear(15);
    dq.insertFront(25);
    dq.deleteRear();
    dq.insertFront(35);
    dq.deleteFront();
    dq.insertRear(45);
    dq.print();
    return 0;
}

A 25 -> 5 -> 45 -> null

B 35 -> 25 -> 5 -> 45 -> null

C 25 -> 5 -> null

D 5 -> 45 -> null

💡 Hint

Track each operation carefully and update front and rear pointers.

After all operations, the dequeue contains 25 at front, then 5, then 45 at rear.

🧠 Conceptual

expert

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of insertFront, insertRear, deleteFront, and deleteRear operations in a dequeue implemented using a doubly linked list with front and rear pointers?

A Insert operations are O(1), delete operations are O(n)

B All operations are O(n) time complexity

C All operations are O(1) time complexity

D Insert operations are O(n), delete operations are O(1)

💡 Hint

Consider how front and rear pointers allow direct access.

With front and rear pointers, all insert and delete operations at both ends take constant time O(1).

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