Dequeue Using Linked List in DSA C - Build from Scratch

Dequeue Using Linked List

📖 Scenario: You are building a simple double-ended queue (dequeue) using a linked list. This data structure allows adding and removing elements from both ends.Imagine a line of people where you can add or remove people from the front or the back.

🎯 Goal: Create a linked list based dequeue with basic operations to add and remove elements from both front and rear.

📋 What You'll Learn

Create a linked list node structure with an integer data field and a next pointer

Create a dequeue structure with pointers to the front and rear nodes

Implement functions to insert at front and rear

Implement functions to delete from front and rear

Print the dequeue elements from front to rear

💡 Why This Matters

🌍 Real World

Dequeue is used in real-world applications like task scheduling, undo operations in software, and managing buffers where insertion and deletion happen at both ends.

💼 Career

Understanding linked list based dequeue helps in roles involving system programming, embedded systems, and software development where efficient data structure manipulation is required.

1

Create Node and Dequeue Structures

Create a struct Node with an int data and a struct Node* next. Then create a struct Dequeue with two pointers: front and rear of type struct Node*. Initialize both pointers to NULL.

DSA C

// Define struct Node and struct Dequeue with front and rear pointers
// Initialize front and rear to NULL

Hint

Use struct keyword to define Node and Dequeue. Initialize pointers to NULL in main.

2

Add Insert Functions for Front and Rear

Write two functions: void insertFront(struct Dequeue* dq, int value) and void insertRear(struct Dequeue* dq, int value). Each should create a new node with value and add it to the front or rear of the dequeue respectively. Update front and rear pointers accordingly.

DSA C

#include 
#include 

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

struct Dequeue {
    struct Node* front;
    struct Node* rear;
};

// Write insertFront and insertRear functions here

int main() {
    struct Dequeue dq;
    dq.front = NULL;
    dq.rear = NULL;
    return 0;
}

Hint

Use malloc to create new nodes. For insertFront, link new node to current front. For insertRear, link current rear to new node.

3

Add Delete Functions for Front and Rear

Write two functions: int deleteFront(struct Dequeue* dq) and int deleteRear(struct Dequeue* dq). Each should remove a node from the front or rear of the dequeue respectively and return its data. Update front and rear pointers accordingly. If dequeue is empty, return -1.

DSA C

#include 
#include 

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

struct Dequeue {
    struct Node* front;
    struct Node* rear;
};

void insertFront(struct Dequeue* dq, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = dq->front;
    dq->front = newNode;
    if (dq->rear == NULL) {
        dq->rear = newNode;
    }
}

void insertRear(struct Dequeue* dq, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (dq->rear == NULL) {
        dq->front = newNode;
        dq->rear = newNode;
    } else {
        dq->rear->next = newNode;
        dq->rear = newNode;
    }
}

// Write deleteFront and deleteRear functions here

int main() {
    struct Dequeue dq;
    dq.front = NULL;
    dq.rear = NULL;
    return 0;
}

Hint

For deleteFront, remove the front node and update pointers. For deleteRear, traverse to the last node, remove it, and update rear pointer.

4

Print Dequeue Elements

Write a function void printDequeue(struct Dequeue* dq) that prints all elements from front to rear separated by -> and ending with NULL. Then in main, insert these values in order: insertRear(&dq, 10), insertFront(&dq, 20), insertRear(&dq, 30). Finally, call printDequeue(&dq) to display the dequeue.

DSA C

#include 
#include 

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

struct Dequeue {
    struct Node* front;
    struct Node* rear;
};

void insertFront(struct Dequeue* dq, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = dq->front;
    dq->front = newNode;
    if (dq->rear == NULL) {
        dq->rear = newNode;
    }
}

void insertRear(struct Dequeue* dq, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (dq->rear == NULL) {
        dq->front = newNode;
        dq->rear = newNode;
    } else {
        dq->rear->next = newNode;
        dq->rear = newNode;
    }
}

int deleteFront(struct Dequeue* dq) {
    if (dq->front == NULL) {
        return -1;
    }
    struct Node* temp = dq->front;
    int val = temp->data;
    dq->front = dq->front->next;
    if (dq->front == NULL) {
        dq->rear = NULL;
    }
    free(temp);
    return val;
}

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

// Your code here

int main() {
    struct Dequeue dq;
    dq.front = NULL;
    dq.rear = NULL;

    insertRear(&dq, 10);
    insertFront(&dq, 20);
    insertRear(&dq, 30);

    // Your code here

    return 0;
}

Hint

Traverse from front to rear printing each node's data followed by ->. End with NULL.