Dequeue Using Linked List in DSA C - Time & Space Complexity

Time Complexity: Dequeue Using Linked List

O(n)

Understanding Time Complexity

We want to understand how the time to perform operations on a dequeue using a linked list changes as the number of elements grows.

Specifically, how fast can we add or remove items from either end?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert at front
void insertFront(Deque* dq, int value) {
    Node* newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = dq->front;
    dq->front = newNode;
    if (dq->rear == NULL) dq->rear = newNode;
}

// Remove from rear
int removeRear(Deque* dq) {
    if (dq->rear == NULL) return -1; // empty
    int val;
    if (dq->front == dq->rear) {
        val = dq->front->data;
        free(dq->front);
        dq->front = NULL;
        dq->rear = NULL;
        return val;
    }
    Node* temp = dq->front;
    while (temp->next != dq->rear) temp = temp->next;
    val = dq->rear->data;
    free(dq->rear);
    dq->rear = temp;
    dq->rear->next = NULL;
    return val;
}
    

This code shows adding an element at the front and removing an element from the rear of a dequeue implemented with a linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop in removeRear that moves through nodes to find the one before the rear.
• How many times: This loop runs once for each node except the last, so up to n-1 times where n is the number of elements.

How Execution Grows With Input

As the number of elements grows, the time to remove from rear grows linearly because we must find the node before the last.

Input Size (n)	Approx. Operations
10	About 9 steps to find the node before rear
100	About 99 steps
1000	About 999 steps

Pattern observation: The steps increase directly with the number of elements, so doubling elements doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means removing from the rear takes longer as the list grows, roughly proportional to the number of elements.

Common Mistake

[X] Wrong: "Removing from the rear is always fast because we have a pointer to the rear node."

[OK] Correct: Even though we have the rear pointer, we must find the node before rear to update its next pointer, which requires walking through the list.

Interview Connect

Understanding how linked list operations scale helps you explain trade-offs in data structure choices clearly and confidently.

Self-Check

"What if we kept a pointer to the node before rear? How would that change the time complexity of removing from the rear?"