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

OutputSuccess

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.