Queue Implementation Using Linked List in DSA C - Time & Space Complexity

Time Complexity: Queue Implementation Using Linked List

O(1)

Understanding Time Complexity

We want to understand how the time taken by queue operations changes as the number of items grows.

How does adding or removing items affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following queue operations using a linked list.

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Enqueue operation
void enqueue(struct Node** front, struct Node** rear, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (*rear == NULL) {
        *front = *rear = newNode;
        return;
    }
    (*rear)->next = newNode;
    *rear = newNode;
}

// Dequeue operation
int dequeue(struct Node** front, struct Node** rear) {
    if (*front == NULL) return -1; // Queue empty
    struct Node* temp = *front;
    int val = temp->data;
    *front = (*front)->next;
    if (*front == NULL) *rear = NULL;
    free(temp);
    return val;
}
    

This code adds items to the end and removes from the front of a linked list to implement a queue.

Identify Repeating Operations

Look for loops or repeated steps inside enqueue and dequeue.

• Primary operation: Adding or removing a single node pointer.
• How many times: Each enqueue or dequeue does a fixed number of steps, no loops.

How Execution Grows With Input

Each operation works with only the front or rear pointer, so the work stays the same no matter how many items are in the queue.

Input Size (n)	Approx. Operations
10	5-7 steps per enqueue or dequeue
100	5-7 steps per enqueue or dequeue
1000	5-7 steps per enqueue or dequeue

Pattern observation: The number of steps does not increase with more items; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means each enqueue or dequeue takes the same amount of time regardless of queue size.

Common Mistake

[X] Wrong: "Enqueue or dequeue takes longer as the queue grows because we have to move through the list."

[OK] Correct: We keep track of front and rear pointers, so we never walk through the whole list during these operations.

Interview Connect

Knowing that queue operations with linked lists run in constant time shows you understand efficient data structure design, a key skill in coding interviews.

Self-Check

"What if we did not keep a rear pointer and only had a front pointer? How would the time complexity of enqueue change?"