Enqueue Using Linked List in DSA C

Mental Model

Add a new item to the end of a line by linking it to the last item.

Analogy: Imagine people standing in a queue; when a new person arrives, they join at the back, holding the hand of the last person.

front -> 1 -> 2 -> 3 -> null
rear ↑

Dry Run Walkthrough

Input: queue: 1 -> 2 -> 3 -> null, enqueue value 4

Goal: Add value 4 to the end of the queue

Step 1: Create new node with value 4

new_node: 4 -> null

Why: We need a new node to add to the queue

Step 2: Link current rear node (3) to new node (4)

front -> 1 -> 2 -> 3 -> [rear->4] -> null

Why: Attach new node at the end of the queue

Step 3: Update rear pointer to new node (4)

front -> 1 -> 2 -> 3 -> 4 -> null
rear ↑

Why: Rear must always point to the last node

Result:

front -> 1 -> 2 -> 3 -> 4 -> null
rear ↑

Annotated Code

DSA C

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

// Node structure
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 a new node with given value
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

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

// Enqueue operation: add value at the rear
void enqueue(Queue* q, int value) {
    Node* newNode = createNode(value); // create new node
    if (q->rear == NULL) { // queue empty
        q->front = newNode; // front and rear both point to new node
        q->rear = newNode;
        return;
    }
    q->rear->next = newNode; // link last node to new node
    q->rear = newNode;       // update rear to new node
}

// Print queue 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, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    printf("Queue before enqueue: ");
    printQueue(q);
    enqueue(q, 4);
    printf("Queue after enqueue 4: ");
    printQueue(q);
    return 0;
}

Node* newNode = createNode(value); // create new node

create a new node to add at the rear

if (q->rear == NULL) { // queue empty q->front = newNode; // front and rear both point to new node q->rear = newNode; return; }

handle empty queue by setting front and rear to new node

q->rear->next = newNode; // link last node to new node

attach new node after current rear

q->rear = newNode; // update rear to new node

move rear pointer to new last node

Output

Queue before enqueue: 1 -> 2 -> 3 -> null

Queue after enqueue 4: 1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) because we add the new node directly at the rear without traversal

Space: O(1) because we only create one new node for each enqueue

vs Alternative: Compared to using an array where adding at the end might require shifting or resizing, linked list enqueue is faster and uses constant time

Edge Cases

Empty queue

Front and rear both point to the new node after enqueue

DSA C

if (q->rear == NULL) { // queue empty

When to Use This Pattern

When you need to add items to the end of a queue efficiently, use the enqueue linked list pattern because it keeps track of the rear pointer for quick insertion.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always set rear to the new node after linking it

Mistake: Not handling empty queue case separately
Fix: Check if rear is NULL and set both front and rear to new node

Summary

Adds a new element at the end of a linked list queue.

Use when you want to insert items in a queue efficiently without traversing.

Keep track of the rear pointer to add new nodes in constant time.