Enqueue Operation in DSA C - Time & Space Complexity

Time Complexity: Enqueue Operation

O(1)

Understanding Time Complexity

We want to understand how the time to add an item to a queue changes as the queue grows.

How does the enqueue operation's time depend on the number of items already in the queue?

Scenario Under Consideration

Analyze the time complexity of the following enqueue code for a queue implemented with a linked list.

// Add a new node at the end of the queue
void enqueue(Queue* q, int value) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = newNode;
        q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}
    

This code adds a new element to the end of a queue using a linked list with front and rear pointers.

Identify Repeating Operations

Look for loops or repeated steps that depend on queue size.

• Primary operation: Creating a new node and updating pointers.
• How many times: This happens once per enqueue call, no loops involved.

How Execution Grows With Input

Adding one item always takes the same steps regardless of queue size.

Input Size (n)	Approx. Operations
10	5-6 steps
100	5-6 steps
1000	5-6 steps

Pattern observation: The number of steps stays about the same no matter how big the queue is.

Final Time Complexity

Time Complexity: O(1)

This means adding an item to the queue takes a constant amount of time, no matter how many items are already there.

Common Mistake

[X] Wrong: "Enqueue takes longer as the queue grows because it has to find the end each time."

[OK] Correct: The queue keeps a pointer to the last item, so it does not search; it directly adds the new item, keeping time constant.

Interview Connect

Understanding constant time operations like enqueue helps you design efficient data structures and shows you know how to keep operations fast as data grows.

Self-Check

"What if the queue was implemented using an array without a rear pointer? How would the enqueue time complexity change?"