How to Implement Queue Using Linked List in C

To implement a queue using a linked list in C, create a node structure with data and a pointer to the next node. Maintain pointers to the front and rear of the queue, and implement enqueue to add nodes at the rear and dequeue to remove nodes from the front.

Syntax

A queue using a linked list requires a struct Node to hold data and a pointer to the next node. You also need two pointers: front for the first element and rear for the last element. The main operations are:

• enqueue: Add a new node at the rear.
• dequeue: Remove a node from the front.

c

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

Node* front = NULL;
Node* rear = NULL;

void enqueue(int value);
int dequeue();

Example

This example shows a complete queue implementation using a linked list in C. It includes enqueue, dequeue, and a simple test in main.

c

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

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

Node* front = NULL;
Node* rear = NULL;

void enqueue(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
        return;
    }
    rear->next = newNode;
    rear = newNode;
}

int dequeue() {
    if (front == NULL) {
        printf("Queue is empty\n");
        return -1; // Indicates empty queue
    }
    Node* temp = front;
    int value = temp->data;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
    return value;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue()); // Queue empty

    return 0;
}

Output

Dequeued: 10
Dequeued: 20
Dequeued: 30
Queue is empty
Dequeued: -1

Common Pitfalls

Common mistakes when implementing a queue with a linked list include:

• Not updating rear to NULL when the queue becomes empty after dequeue.
• Forgetting to check if the queue is empty before dequeue, which can cause errors.
• Not allocating memory properly for new nodes, leading to crashes.
• Memory leaks by not freeing nodes after dequeue.

c

/* Wrong: Not updating rear when queue becomes empty */
void dequeue_wrong() {
    if (front == NULL) return;
    Node* temp = front;
    front = front->next;
    // rear not updated if front is NULL
    free(temp);
}

/* Right: Update rear when queue is empty */
void dequeue_right() {
    if (front == NULL) return;
    Node* temp = front;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
}

Quick Reference

Queue with Linked List Summary:

• enqueue: Add node at rear, update rear pointer.
• dequeue: Remove node from front, update front pointer.
• Set both front and rear to NULL when queue is empty.
• Always free memory of dequeued nodes.

Key Takeaways

Use two pointers, front and rear, to track the queue ends in a linked list.

Enqueue adds nodes at rear; dequeue removes nodes from front.

Always check for empty queue before dequeue to avoid errors.

Update rear to NULL when queue becomes empty after dequeue.

Free memory of removed nodes to prevent memory leaks.