Queue Implementation Using Linked List in DSA C

Mental Model

A queue is a line where elements wait their turn. Using a linked list means each element points to the next, so we can add at the end and remove from the front easily.

Analogy: Imagine a line of people waiting to buy tickets. The first person in line is served and leaves, and new people join at the end of the line. Each person holds the hand of the next person, so the line stays connected.

front -> [node1] -> [node2] -> [node3] -> null
rear ↑

Dry Run Walkthrough

Input: Start with empty queue, enqueue 10, enqueue 20, dequeue once

Goal: Show how elements are added at the rear and removed from the front in a linked list queue

Step 1: enqueue 10: create node with 10, front and rear point to it

front -> [10] -> null
rear ↑

Why: First element sets both front and rear pointers

Step 2: enqueue 20: create node with 20, link rear's next to new node, move rear to new node

front -> [10] -> [20] -> null
rear ↑

Why: Add new element at the end and update rear pointer

Step 3: dequeue: remove node at front (10), move front to next node (20)

front -> [20] -> null
rear ↑

Why: Remove from front to maintain queue order

Result:

front -> [20] -> null
rear ↑

Annotated Code

DSA C

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

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Queue structure with front and rear pointers
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// Create an empty queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

// Enqueue operation: add element at rear
void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) {
        // Queue empty, front and rear are same
        q->front = newNode;
        q->rear = newNode;
        return;
    }

    // Link new node at the end and update rear
    q->rear->next = newNode;
    q->rear = newNode;
}

// Dequeue operation: remove element from front
int dequeue(Queue* q) {
    if (q->front == NULL) {
        // Queue empty
        return -1; // Indicate empty queue
    }

    Node* temp = q->front;
    int value = temp->data;
    q->front = q->front->next;

    // If front becomes NULL, then queue is empty, update rear
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return value;
}

// Print queue elements from front to rear
void printQueue(Queue* q) {
    Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("null\n");
}

int main() {
    Queue* q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    printQueue(q); // Expected: 10 -> 20 -> null

    int val = dequeue(q);
    printf("Dequeued: %d\n", val); // Expected: Dequeued: 10

    printQueue(q); // Expected: 20 -> null

    return 0;
}

if (q->rear == NULL) {

Check if queue is empty to set front and rear to new node

q->rear->next = newNode;

Link new node at the end of queue

q->rear = newNode;

Update rear pointer to new node

if (q->front == NULL) {

Check if queue is empty before dequeue

q->front = q->front->next;

Move front pointer to next node to remove front element

if (q->front == NULL) { q->rear = NULL; }

If queue becomes empty after dequeue, update rear to NULL

Output

10 -> 20 -> null

Dequeued: 10

20 -> null

Complexity Analysis

Time: O(1) for both enqueue and dequeue because we add or remove nodes directly at rear or front without traversal

Space: O(n) because each element is stored in a separate node linked together

vs Alternative: Compared to array-based queue, linked list avoids shifting elements on dequeue, making operations faster and memory usage dynamic

Edge Cases

Dequeue from empty queue

Returns -1 indicating queue is empty, no crash

DSA C

if (q->front == NULL) { return -1; }

Enqueue first element into empty queue

Both front and rear pointers set to new node

DSA C

if (q->rear == NULL) { q->front = newNode; q->rear = newNode; return; }

Dequeue last element making queue empty

Front becomes NULL and rear is updated to NULL

DSA C

if (q->front == NULL) { q->rear = NULL; }

When to Use This Pattern

When you need a first-in-first-out structure with dynamic size and efficient add/remove at ends, use a linked list queue to avoid costly shifts.

Common Mistakes

Mistake: Not updating rear pointer to NULL when queue becomes empty after dequeue
Fix: Set rear to NULL when front becomes NULL after removing last element

Mistake: Linking new node incorrectly causing broken chain
Fix: Always set rear->next to new node before updating rear pointer

Summary

Implements a queue using a linked list with front and rear pointers.

Use when you want a queue that grows dynamically without shifting elements.

Remember to update both front and rear pointers correctly when queue becomes empty or when adding the first element.