Queue using Linked List

Why a linked-list queue?

A queue follows FIFO — First In, First Out. You can build one with an array (see queue in C), but a simple array queue has two weaknesses: a fixed size, and wasted slots after several dequeues. A linked-list queue fixes both by allocating a node for each item and freeing it when removed.

If linked lists are new, read linked list in C first — this lesson builds directly on nodes.

front and rear pointers

We track the queue with two pointers into the node chain:

Both start as NULL for an empty queue.

Enqueue at the rear

Create a node, attach it after rear, and move rear forward.

void enqueue(int x) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x; n->next = NULL;
    if (rear == NULL) { front = rear = n; return; }  // empty
    rear->next = n;       // link after current rear
    rear = n;            // new rear
}

Dequeue at the front

Take the front node, advance front, and free the old node.

int dequeue() {
    if (front == NULL) { printf("Queue empty\n"); return -1; }
    struct Node *temp = front;
    int x = temp->data;
    front = front->next;
    if (front == NULL) rear = NULL;   // was the last node!
    free(temp);
    return x;
}

The complete program

#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
struct Node *front = NULL, *rear = NULL;

void enqueue(int x) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x; n->next = NULL;
    if (rear == NULL) { front = rear = n; return; }
    rear->next = n; rear = n;
}
int dequeue() {
    if (front == NULL) { printf("Empty\n"); return -1; }
    struct Node *temp = front;
    int x = temp->data;
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
    return x;
}
int main() {
    enqueue(10); enqueue(20); enqueue(30);
    printf("Removed: %d\n", dequeue());  // 10
    printf("Removed: %d\n", dequeue());  // 20
    return 0;
}

Dry run

Common mistakes

• Forgetting to set rear = NULL when the last node is dequeued.
• Not handling the empty case in enqueue (both pointers start NULL).
• Forgetting to free the dequeued node, causing a memory leak.
• Adding at the front or removing at the rear — that breaks FIFO order.

Summary

• A linked-list queue uses front and rear node pointers.
• Enqueue adds a node at the rear; dequeue removes from the front.
• It grows and shrinks at run time — no fixed size, no wasted slots.
• Reset rear to NULL when the last node leaves.
• Always free the removed node to avoid leaks.