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 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, dequeue from back

Goal: Show how items are added and removed from both ends of the dequeue

Step 1: enqueue 10 at front

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

Why: Add first element, front and back both point to it

Step 2: enqueue 20 at back

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

Why: Add element at back, link from last node to new node

Step 3: dequeue from front

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

Why: Remove front element, front pointer moves to next node

Step 4: dequeue from back

front -> null, back -> null

Why: Remove back element, dequeue becomes empty

Result:

front -> null, back -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Dequeue structure with front and back pointers
typedef struct Dequeue {
    Node* front;
    Node* back;
} Dequeue;

// Create a new empty dequeue
Dequeue* createDequeue() {
    Dequeue* dq = (Dequeue*)malloc(sizeof(Dequeue));
    dq->front = NULL;
    dq->back = NULL;
    return dq;
}

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Add element at front
void enqueueFront(Dequeue* dq, int data) {
    Node* newNode = createNode(data);
    if (dq->front == NULL) {
        dq->front = newNode;
        dq->back = newNode;
    } else {
        newNode->next = dq->front;
        dq->front->prev = newNode;
        dq->front = newNode;
    }
}

// Add element at back
void enqueueBack(Dequeue* dq, int data) {
    Node* newNode = createNode(data);
    if (dq->back == NULL) {
        dq->front = newNode;
        dq->back = newNode;
    } else {
        dq->back->next = newNode;
        newNode->prev = dq->back;
        dq->back = newNode;
    }
}

// Remove element from front
int dequeueFront(Dequeue* dq) {
    if (dq->front == NULL) {
        return -1; // empty dequeue
    }
    int val = dq->front->data;
    Node* temp = dq->front;
    dq->front = dq->front->next;
    if (dq->front != NULL) {
        dq->front->prev = NULL;
    } else {
        dq->back = NULL;
    }
    free(temp);
    return val;
}

// Remove element from back
int dequeueBack(Dequeue* dq) {
    if (dq->back == NULL) {
        return -1; // empty dequeue
    }
    int val = dq->back->data;
    Node* temp = dq->back;
    dq->back = dq->back->prev;
    if (dq->back != NULL) {
        dq->back->next = NULL;
    } else {
        dq->front = NULL;
    }
    free(temp);
    return val;
}

// Print dequeue from front to back
void printDequeue(Dequeue* dq) {
    Node* curr = dq->front;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    Dequeue* dq = createDequeue();

    enqueueFront(dq, 10);
    printDequeue(dq); // 10 -> null

    enqueueBack(dq, 20);
    printDequeue(dq); // 10 -> 20 -> null

    int val1 = dequeueFront(dq);
    printf("Dequeued from front: %d\n", val1);
    printDequeue(dq); // 20 -> null

    int val2 = dequeueBack(dq);
    printf("Dequeued from back: %d\n", val2);
    printDequeue(dq); // null

    return 0;
}

if (dq->front == NULL) { dq->front = newNode; dq->back = newNode; } else { newNode->next = dq->front; dq->front->prev = newNode; dq->front = newNode; }

add new node at front, update front pointer and link previous front

if (dq->back == NULL) { dq->front = newNode; dq->back = newNode; } else { dq->back->next = newNode; newNode->prev = dq->back; dq->back = newNode; }

add new node at back, update back pointer and link previous back

if (dq->front == NULL) { return -1; } int val = dq->front->data; Node* temp = dq->front; dq->front = dq->front->next; if (dq->front != NULL) { dq->front->prev = NULL; } else { dq->back = NULL; } free(temp); return val;

remove node from front, update front pointer and fix links, handle empty dequeue

if (dq->back == NULL) { return -1; } int val = dq->back->data; Node* temp = dq->back; dq->back = dq->back->prev; if (dq->back != NULL) { dq->back->next = NULL; } else { dq->front = NULL; } free(temp); return val;

remove node from back, update back pointer and fix links, handle empty dequeue

Output

10 -> null

10 -> 20 -> null

Dequeued from front: 10

20 -> null

Dequeued from back: 20

null

Complexity Analysis

Time: O(1) for all enqueue and dequeue operations because we only change pointers at the ends without traversing the list

Space: O(n) because we store n nodes in the linked list for n elements

vs Alternative: Compared to using arrays where adding/removing at front can be O(n), linked list dequeue is faster with O(1) operations

Edge Cases

empty dequeue

dequeue operations return -1 indicating empty, no crash

DSA C

if (dq->front == NULL) { return -1; }

single element dequeue

removing front or back empties dequeue and sets both pointers to NULL

DSA C

else { dq->back = NULL; } and else { dq->front = NULL; }

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 O(1) operations.

Common Mistakes

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

Mistake: Not fixing prev or next pointers after enqueue or dequeue causing broken links
Fix: Always update next and prev pointers of neighboring nodes after insertion or removal

Summary

Implements a dequeue using a doubly linked list allowing insertion and removal from both ends.

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

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

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