Dequeue Operation in DSA Python - Time & Space Complexity

Time Complexity: Dequeue Operation

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove an item from a dequeue as the number of items grows.

How does the time to remove an element change when the dequeue gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Dequeue:
    def __init__(self):
        self.items = []

    def dequeue_front(self):
        if not self.items:
            return None
        return self.items.pop(0)  # Remove from front
    

This code removes an item from the front of a dequeue implemented with a list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Removing the first item using pop(0) which shifts all other items left.
• How many times: The shifting happens for every dequeue_front call, proportional to the number of items after the removed one.

How Execution Grows With Input

When we remove from the front, all other items move one step left, so more items means more work.

Input Size (n)	Approx. Operations
10	About 9 moves
100	About 99 moves
1000	About 999 moves

Pattern observation: The work grows roughly in direct proportion to the number of items.

Final Time Complexity

Time Complexity: O(n)

This means removing from the front takes longer as the dequeue gets bigger, growing linearly with size.

Common Mistake

[X] Wrong: "Removing from the front is always fast, like popping from the end."

[OK] Correct: Removing from the front shifts all other items, so it takes more time as the list grows.

Interview Connect

Understanding this helps you explain why some dequeue implementations use linked lists or double-ended queues for fast front removals.

Self-Check

"What if we used a linked list instead of a list for the dequeue? How would the time complexity change?"