Deque in C Using a Doubly Linked List: Program and Explanation

A deque (double-ended queue) is a linear data structure that supports insertion and deletion at both the front and the rear. This guide shows how to implement a deque in C using a doubly linked list, with a complete menu-driven program, a worked example, and the time complexity of each operation.

The earlier singly linked-list approach can insert at either end efficiently, but deleting the rear element requires walking from the front to find its predecessor. That makes rear deletion O(n). A doubly linked list stores both next and prev pointers, so all four end operations take O(1) time.

Deque operations

• Insert front: add a value before the current first node.
• Insert rear: add a value after the current last node.
• Delete front: remove and return the first value.
• Delete rear: remove and return the last value.
• Display: traverse from front to rear.

Doubly linked-list representation

Each node stores an integer plus links to the previous and next nodes. The deque stores pointers to its front and rear nodes. When the deque is empty, both pointers are NULL. When it contains one node, both pointers refer to that same node.

Deque implementation in C

This version uses standard C99 headers and checks allocation and input failures. It does not depend on Turbo C functions such as clrscr() or getch().

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

typedef struct DequeNode {
    int data;
    struct DequeNode *prev;
    struct DequeNode *next;
} DequeNode;

typedef struct {
    DequeNode *front;
    DequeNode *rear;
} Deque;

static bool isEmpty(const Deque *deque)
{
    return deque->front == NULL;
}

static bool insertFront(Deque *deque, int value)
{
    DequeNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->data = value;
    node->prev = NULL;
    node->next = deque->front;

    if (deque->front != NULL) {
        deque->front->prev = node;
    } else {
        deque->rear = node;
    }

    deque->front = node;
    return true;
}

static bool insertRear(Deque *deque, int value)
{
    DequeNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->data = value;
    node->next = NULL;
    node->prev = deque->rear;

    if (deque->rear != NULL) {
        deque->rear->next = node;
    } else {
        deque->front = node;
    }

    deque->rear = node;
    return true;
}

static bool deleteFront(Deque *deque, int *removedValue)
{
    if (isEmpty(deque)) {
        return false;
    }

    DequeNode *node = deque->front;
    *removedValue = node->data;
    deque->front = node->next;

    if (deque->front != NULL) {
        deque->front->prev = NULL;
    } else {
        deque->rear = NULL;
    }

    free(node);
    return true;
}

static bool deleteRear(Deque *deque, int *removedValue)
{
    if (isEmpty(deque)) {
        return false;
    }

    DequeNode *node = deque->rear;
    *removedValue = node->data;
    deque->rear = node->prev;

    if (deque->rear != NULL) {
        deque->rear->next = NULL;
    } else {
        deque->front = NULL;
    }

    free(node);
    return true;
}

static void display(const Deque *deque)
{
    const DequeNode *current = deque->front;

    if (current == NULL) {
        puts("Deque is empty.");
        return;
    }

    printf("Front -> Rear: ");
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(" <-> ");
        }
        current = current->next;
    }
    putchar(10);
}

static void clearDeque(Deque *deque)
{
    int discardedValue;
    while (deleteFront(deque, &discardedValue)) {
        /* Each node is freed by deleteFront. */
    }
}

int main(void)
{
    Deque deque = { NULL, NULL };
    int choice;
    int value;

    for (;;) {
        puts("\nDeque using a doubly linked list");
        puts("1. Insert at rear");
        puts("2. Insert at front");
        puts("3. Delete from front");
        puts("4. Delete from rear");
        puts("5. Display deque");
        puts("6. Exit");
        printf("Enter your choice: ");

        if (scanf("%d", &choice) != 1) {
            fprintf(stderr, "Invalid menu input.\n");
            clearDeque(&deque);
            return 1;
        }

        switch (choice) {
        case 1:
        case 2:
            printf("Enter an integer: ");
            if (scanf("%d", &value) != 1) {
                fprintf(stderr, "Invalid value.\n");
                clearDeque(&deque);
                return 1;
            }
            if (!(choice == 1 ? insertRear(&deque, value)
                              : insertFront(&deque, value))) {
                fprintf(stderr, "Unable to allocate memory for the new node.\n");
            }
            break;

        case 3:
            if (deleteFront(&deque, &value)) {
                printf("Deleted from front: %d\n", value);
            } else {
                puts("Deque is empty.");
            }
            break;

        case 4:
            if (deleteRear(&deque, &value)) {
                printf("Deleted from rear: %d\n", value);
            } else {
                puts("Deque is empty.");
            }
            break;

        case 5:
            display(&deque);
            break;

        case 6:
            clearDeque(&deque);
            puts("Deque cleared. Goodbye.");
            return 0;

        default:
            puts("Choose a number from 1 to 6.");
        }
    }
}

Example deque operations

Starting with an empty deque, insert 10 at the rear, insert 5 at the front, then insert 20 at the rear. The deque is now 5 <-> 10 <-> 20. Deleting from the front returns 5; deleting from the rear then returns 20, leaving 10.

Compile and run the C program

Save the source as deque.c. Compile with GCC or Clang in C99 mode:

gcc -std=c99 -Wall -Wextra -pedantic deque.c -o deque
./deque

On Windows, run deque.exe. The program stores integers and asks for a menu choice each time. Enter 6 to exit; the remaining nodes are freed before the program ends.

Time and space complexity

• Insert at front or rear: O(1)
• Delete from front or rear: O(1)
• Check whether empty: O(1)
• Display all values: O(n)
• Storage: O(n) for n nodes, plus two links per node

The extra previous pointer uses more memory than a singly linked list, but it makes rear deletion constant time. With a singly linked list that stores only a front and rear pointer, deleting the rear node requires finding its predecessor, which takes O(n).

Common deque implementation mistakes

• Forgetting to update both front and rear when inserting into or deleting the only node.
• Not setting the new front node’s prev pointer or the new rear node’s next pointer to NULL.
• Accessing a node before checking whether the deque is empty.
• Ignoring the return value from malloc; allocation can fail.
• Using conio.h, clrscr(), or getch() in code intended for a standard compiler.

Summary

A deque supports insertion and deletion at both ends. A doubly linked list is a suitable implementation when you need O(1) insertions and deletions at the front and rear. The program above handles empty and single-node cases, checks input and memory allocation, and frees its nodes on exit.

For a deeper explanation of linked-list pointer operations and the space trade-off of doubly linked nodes, see the OpenDSA doubly linked list notes.