Queue Using Linked List in C

A queue implemented with a linked list in C has no fixed size limit — it grows and shrinks dynamically using malloc and free. Each node holds a value and a pointer to the next node. Two pointers, front and rear, track the dequeue end and enqueue end respectively.

Linked List Queue vs Array Queue

Property	Array Queue	Linked List Queue
Max size	Fixed at compile time	Limited only by available memory
Memory	Pre-allocated (may waste space)	Allocated per node (no waste)
Wasted slots	Yes (linear queue)	No
Overhead	None	Pointer per node
Cache friendliness	High (contiguous memory)	Low (scattered nodes)

Queue Using Linked Lists in C

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

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

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

int isEmpty(void) { return front == NULL; }

void enqueue(int val)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) { fprintf(stderr, "malloc failed\n"); return; }
    newNode->data = val;
    newNode->next = NULL;

    if (rear == NULL) {
        front = rear = newNode;      /* first element */
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("Enqueued: %d\n", val);
}

int dequeue(void)
{
    int val;
    Node *temp;

    if (isEmpty()) {
        printf("Queue underflow.\n");
        return -1;
    }
    val   = front->data;
    temp  = front;
    front = front->next;
    if (front == NULL) rear = NULL;  /* queue is now empty */
    free(temp);
    return val;
}

int peek(void)
{
    if (isEmpty()) { printf("Queue is empty.\n"); return -1; }
    return front->data;
}

void display(void)
{
    Node *curr;
    if (isEmpty()) { printf("Queue is empty.\n"); return; }
    printf("Front → ");
    for (curr = front; curr != NULL; curr = curr->next)
        printf("%d → ", curr->data);
    printf("NULL (Rear)\n");
}

void freeQueue(void)
{
    while (!isEmpty()) dequeue();
}

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

    printf("Peek:     %d\n", peek());
    printf("Dequeued: %d\n", dequeue());
    printf("Dequeued: %d\n", dequeue());
    display();

    freeQueue();
    return 0;
}

How to Compile and Run

gcc -Wall -o llqueue llqueue.c
./llqueue

Sample Output

Enqueued: 10
Enqueued: 20
Enqueued: 30
Front → 10 → 20 → 30 → NULL (Rear)
Peek:     10
Dequeued: 10
Dequeued: 20
Front → 30 → NULL (Rear)

How the Implementation Works

Enqueue at rear: A new node is always appended to rear->next, then rear advances to the new node. O(1) because we hold a direct pointer to the tail.
Dequeue from front: Save front to a temp pointer, advance front to front->next, then free(temp). O(1).
Empty check after dequeue: If front becomes NULL after advancing, rear must also be set to NULL — otherwise rear dangles to a freed node.
freeQueue(): Calling dequeue() until empty is sufficient — each call frees one node.

Time and Space Complexity

Operation	Time	Space
ENQUEUE	O(1)	O(1) per node
DEQUEUE	O(1)	O(1)
Total storage (n elements)	—	O(n)

What This Program Teaches

Why keeping a rear pointer is essential — without it, enqueue would require O(n) traversal to find the tail
The dangling pointer trap: after the last dequeue, both front and rear must be NULL — forgetting to null rear causes a use-after-free bug on the next enqueue
Dynamic allocation for data structures: no pre-declared size, memory grows with demand

Related Programs

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Pointers, dynamic memory, and linked structures are covered in chapters 5 and 6 of The C Programming Language by Kernighan & Ritchie. Also on Amazon.com.

Queue Using Linked List in C – Dynamic with No Size Limit