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.

Practice

1. What is the main advantage of using a linked list to implement a dequeue compared to an array?

easy

A. Dynamic size allows easy insertion and deletion at both ends

B. Faster access to elements by index

C. Uses less memory than arrays

D. Simpler to implement than arrays

Solution

1. Step 1: Understand linked list flexibility

   A linked list can grow or shrink dynamically without needing a fixed size.

2. Step 2: Compare with array limitations

   Arrays have fixed size and costly resizing; linked lists allow easy insertion/deletion at both ends.

3. Final Answer:

   Dynamic size allows easy insertion and deletion at both ends -> Option A

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked lists grow/shrink easily at ends [OK]

Common Mistakes:

• Confusing faster index access with linked list
• Thinking linked lists always use less memory
• Assuming arrays are simpler to implement

2. Which of the following is the correct way to declare a node structure for a dequeue using a linked list in C?

easy

A. struct Node { int data; struct Node* next; };

B. struct Node { int data; struct Node next; struct Node prev; };

C. struct Node { int data; int next; int prev; };

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

Solution

1. Step 1: Identify node fields for dequeue

   A dequeue node needs data and pointers to next and previous nodes for double linking.

2. Step 2: Check pointer types

   Correct syntax uses pointers (struct Node*) for next and prev, not int or struct Node directly.

3. Final Answer:

   struct Node { int data; struct Node* next; struct Node* prev; }; -> Option D

4. Quick Check:

   Double linked node = data + next ptr + prev ptr [OK]

Hint: Double linked nodes need next and prev pointers [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer for dequeue
• Declaring next/prev as struct Node instead of pointer

3. Consider the following operations on an empty dequeue implemented using a linked list:
insertFront(10); insertRear(20); insertFront(5); deleteRear();
What will be the state of the dequeue from front to rear after these operations?

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> null

D. 5 -> 20 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   Dequeue: 10 (front) -> 20 (rear)

2. Step 2: Perform insertFront(5) and deleteRear()

   After insertFront(5): 5 -> 10 -> 20
   After deleteRear(): removes 20, so 5 -> 10

3. Final Answer:

   5 -> 10 -> null -> Option A

4. Quick Check:

   Front insert adds at front, rear delete removes last [OK]

Hint: Track front and rear changes stepwise [OK]

Common Mistakes:

• Confusing insertFront and insertRear order
• Forgetting to delete rear element
• Mixing up front and rear positions

4. The following C code snippet for deleting from the front of a dequeue has an error. What is the error?

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

medium

A. Uses free() incorrectly

B. Does not check if dequeue is full

C. Does not update the prev pointer of new front node

D. Does not update rear pointer when dequeue becomes empty

Solution

1. Step 1: Analyze pointer updates after deletion

   After moving front to front->next, the new front's prev pointer still points to old node.

2. Step 2: Identify missing update

   Must set front->prev = NULL to maintain correct double link.

3. Final Answer:

   Does not update the prev pointer of new front node -> Option C

4. Quick Check:

   Update prev pointer after front deletion [OK]

Hint: Always reset prev of new front to NULL [OK]

Common Mistakes:

• Ignoring prev pointer update
• Checking dequeue full in delete function
• Not updating rear when empty (not shown here)

5. You want to implement a function to reverse a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue?

hard

A. Only swap front and rear pointers without changing node links

B. Swap next and prev pointers of each node, then swap front and rear pointers

C. Delete all nodes and re-insert them from rear to front

D. Traverse from front to rear and copy data into a new list in reverse order

Solution

1. Step 1: Understand reversing a doubly linked list

   Reversing means each node's next and prev pointers must be swapped to reverse direction.

2. Step 2: Swap front and rear pointers

   After swapping pointers in nodes, front and rear pointers must also be swapped to reflect new ends.

3. Final Answer:

   Swap next and prev pointers of each node, then swap front and rear pointers -> Option B

4. Quick Check:

   Swap links + swap ends = reverse dequeue [OK]

Hint: Swap next/prev in nodes, then swap front/rear [OK]

Common Mistakes:

• Only swapping front and rear pointers
• Rebuilding list instead of reversing links
• Copying data instead of changing pointers