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.

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