Queue Using Linked List

A linked-list queue stores each element in a node and keeps two pointers: front and rear. Enqueue inserts at rear, dequeue removes from front. Both operations are O(1), and the queue grows dynamically until memory limits are reached.

On this page

Representation — node structure with front and rear pointers
Operations — tail insert, head remove
Example in C — malloc/free and queue API
Trade-offs — dynamic size vs array locality

1) Representation

Typical pieces for a linked-list queue in C
Component	Role	Notes
`struct Node`	Stores value and `next` pointer.	One node per enqueued item.
`front`	Points to first node to dequeue.	`NULL` when empty.
`rear`	Points to last node for fast enqueue.	Must be updated on enqueue/dequeue.

2) Mapping operations

Queue operations with linked list
Operation	Steps	Failure case
`enqueue(x)`	Allocate node, append at `rear`, move `rear`.	`malloc` failure.
`dequeue()`	Read `front`, move `front=front->next`, free old node.	Underflow if empty.
`peek()`	Read `front->data` without removing.	Underflow if empty.

3) Example in C

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

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

static Node *front;
static Node *rear;
static int queue_last;

void queue_init(void) {
    front = NULL;
    rear = NULL;
}

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

int queue_enqueue(int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL) return 0;
    n->data = value;
    n->next = NULL;
    if (rear == NULL) {
        front = n;
        rear = n;
    } else {
        rear->next = n;
        rear = n;
    }
    return 1;
}

int queue_dequeue(void) {
    if (queue_is_empty()) return 0;
    Node *old = front;
    queue_last = old->data;
    front = old->next;
    if (front == NULL) rear = NULL;
    free(old);
    return 1;
}

int queue_peek(void) {
    if (queue_is_empty()) return 0;
    queue_last = front->data;
    return 1;
}

void queue_destroy(void) {
    while (queue_dequeue()) { }
}

int main(void) {
    queue_init();
    queue_enqueue(10);
    queue_enqueue(20);
    queue_enqueue(30);

    if (queue_peek())    printf("peek: %d\n", queue_last);
    if (queue_dequeue()) printf("dequeue: %d\n", queue_last);
    if (queue_peek())    printf("peek: %d\n", queue_last);

    queue_destroy();
    return 0;
}

Enqueue operation

Enqueue trace for `queue_enqueue`
Step	Operation	Value	Condition	Action	Front	Rear	Queue state
1	`queue_enqueue(10)`	10	`rear == NULL` (empty)	`front = n, rear = n`	points to 10	points to 10	`[10]`
2	`queue_enqueue(20)`	20	`rear != NULL`	`rear->next = n, rear = n`	points to 10	points to 20	`[10, 20]`
3	`queue_enqueue(30)`	30	`rear != NULL`	`rear->next = n, rear = n`	points to 10	points to 30	`[10, 20, 30]`

Enqueue steps in detail

Allocate new node n with given value.
Set n->next = NULL.
If queue empty → set both front and rear to n.
If queue not empty → link current rear->next to n, then move rear to n.

Dequeue operation

Dequeue trace for `queue_dequeue`
Step	Queue state (before)	Operation	Action	`queue_last` set to	Old front	New front	Queue state (after)
1	`[10, 20, 30]`	`queue_dequeue()`	`front = front->next`, `free(old)`	10	node(10)	node(20)	`[20, 30]`
2	`[20, 30]`	`queue_dequeue()`	`front = front->next`, `free(old)`	20	node(20)	node(30)	`[30]`
3	`[30]`	`queue_dequeue()`	`front = front->next`, `free(old)`, `rear = NULL`	30	node(30)	NULL	empty

Dequeue steps in detail

Check if queue empty (return 0 if empty).
Save old front node to old.
Store old->data in queue_last (global variable).
Move front to front->next.
If queue becomes empty → set rear = NULL.
Free the old front node.
Return 1 (success).

Visual representation

Enqueue 10:    Enqueue 20:       Enqueue 30:
front → [10]   front → [10] → [20]   front → [10] → [20] → [30]
rear  → [10]   rear        → [20]   rear                 → [30]

Dequeue:       Dequeue:           Dequeue:
front → [20] → [30]   front → [30]   front → NULL
rear        → [30]   rear  → [30]   rear  → NULL
(removed 10)          (removed 20)   (removed 30)

Key points

FIFO (First In, First Out) behavior.
Enqueue adds to rear.
Dequeue removes from front.
Both operations are O(1) time complexity.

Explanation of the program output

Program execution trace
Step	Operation	Queue state (front → rear)	Output
1	`enqueue(10), enqueue(20), enqueue(30)`	`10 → 20 → 30`	(none)
2	`peek()`	`10 → 20 → 30` (unchanged)	`peek: 10`
3	`dequeue()`	`20 → 30`	`dequeue: 10`
4	`peek()`	`20 → 30` (unchanged)	`peek: 20`

4) Trade-offs

Pros — Dynamic growth and O(1) enqueue/dequeue.
Cons — Extra pointer memory and weaker cache locality than arrays.

Compare with Queue using array when fixed capacity and contiguous storage are acceptable.

Key takeaway

Use front for dequeue and rear for enqueue to keep both operations O(1). Always free dequeued nodes and reset both pointers when queue becomes empty.

Next up: Simple queue · Circular queue · Deque