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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations on Linked List

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

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

DSA C

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

// After operations, print from front to rear
// Format: data1 -> data2 -> ... -> null

// Initial dequeue is empty

A 20 -> 30 -> 40 -> null

B 40 -> 10 -> 30 -> null

C 40 -> 30 -> null

D 20 -> 10 -> 30 -> null

💡 Hint

Remember that insert at front adds before current front, and delete from front removes the front node.

Step-by-step:
1. Insert 10 at rear: 10 -> null
2. Insert 20 at front: 20 -> 10 -> null
3. Insert 30 at rear: 20 -> 10 -> 30 -> null
4. Delete from front: removes 20, so 10 -> 30 -> null
5. Insert 40 at front: 40 -> 10 -> 30 -> null
Final state is 40 -> 10 -> 30 -> null (option B).

❓ Predict Output

intermediate

Result of Mixed Insert and Delete in Dequeue

Given an empty dequeue implemented using a doubly linked list, what is the state after these operations?
1. Insert 5 at front
2. Insert 15 at rear
3. Insert 25 at rear
4. Delete from rear
5. Insert 35 at front

DSA C

// Print dequeue from front to rear after operations
// Format: data1 -> data2 -> ... -> null

A 35 -> 15 -> null

B 15 -> 5 -> 35 -> null

C 5 -> 15 -> 35 -> null

D 35 -> 5 -> 15 -> null

💡 Hint

Deleting from rear removes the last element inserted at rear.

Step-by-step:
1. Insert 5 at front: 5 -> null
2. Insert 15 at rear: 5 -> 15 -> null
3. Insert 25 at rear: 5 -> 15 -> 25 -> null
4. Delete from rear: removes 25, so 5 -> 15 -> null
5. Insert 35 at front: 35 -> 5 -> 15 -> null
Final state matches option D.

🔧 Debug

advanced

Identify the Bug in Dequeue Delete from Front

Consider this function to delete from front in a dequeue implemented with a doubly linked list. What is the bug causing a crash or incorrect behavior?

DSA C

void deleteFront(struct Node** front, struct Node** rear) {
    if (*front == NULL) {
        printf("Dequeue is empty\n");
        return;
    }
    struct Node* temp = *front;
    *front = (*front)->next;
    free(temp);
    if (*front != NULL) {
        (*front)->prev = NULL;
    } else {
        *rear = NULL;
    }
}

A No bug, function works correctly

B Missing check for empty dequeue before freeing temp

C Does not set front pointer to NULL when dequeue becomes empty

D Does not update rear pointer when dequeue becomes empty

💡 Hint

Check what happens when the dequeue has only one node.

The function checks if front is NULL at start, so no freeing NULL pointer.
It updates front to next node.
If front becomes NULL after deletion, it sets rear to NULL.
It sets new front's prev to NULL if front is not NULL.
All steps are correct, so no bug.

🧠 Conceptual

advanced

Time Complexity of Dequeue Operations Using Linked List

What is the time complexity of inserting or deleting an element at either end of a dequeue implemented using a doubly linked list?

A O(1) for insertions at front, O(n) for deletions at rear

B O(n) for insertions at rear, O(1) for deletions at front

C O(1) for all insertions and deletions at front and rear

D O(n) for all insertions and deletions

💡 Hint

Think about how pointers are updated in a doubly linked list.

In a doubly linked list with pointers to front and rear, insertions and deletions at both ends only involve updating a few pointers.
There is no need to traverse the list.
Therefore, all these operations take constant time O(1).

🚀 Application

expert

Design a Function to Reverse a Dequeue Using Linked List

You have a dequeue implemented as a doubly linked list with front and rear pointers. Which of the following code snippets correctly reverses the dequeue so that front becomes rear and vice versa, and the order of elements is reversed?

A

void reverseDequeue(struct Node** front, struct Node** rear) {
    struct Node* current = *front;
    struct Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *rear = *front;
        *front = temp->prev;
    }
}

B

void reverseDequeue(struct Node** front, struct Node** rear) {
    struct Node* current = *front;
    struct Node* temp = NULL;
    while (current != NULL) {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *rear = *front;
        *front = temp->prev;
    }
}

C

void reverseDequeue(struct Node** front, struct Node** rear) {
    struct Node* current = *front;
    struct Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *front = *rear;
        *rear = temp->prev;
    }
}

D

void reverseDequeue(struct Node** front, struct Node** rear) {
    struct Node* current = *front;
    struct Node* temp = NULL;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *front = temp->prev;
        *rear = *front;
    }
}

💡 Hint

Swapping next and prev pointers reverses the list. Then update front and rear pointers accordingly.

The correct approach:
- For each node, swap prev and next.
- Move current to previous next (which is current->prev after swap).
- After loop, temp points to the old front's previous node.
- Set rear to old front.
- Set front to temp->prev (new front).
Option A matches this logic.
Other options have incorrect pointer swaps or front/rear assignments.