Double Ended Queue Deque in DSA Python - Time & Space Complexity

Time Complexity: Double Ended Queue Deque

O(n) for front insert/remove, O(1) for rear insert/remove

Understanding Time Complexity

We want to understand how fast operations on a double ended queue (deque) run as the number of items grows.

Specifically, how does adding or removing items from either end affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following deque operations.

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

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        return self.items.pop(0)

    def remove_rear(self):
        return self.items.pop()

This code shows basic add and remove operations at both ends of a deque using a Python list.

Identify Repeating Operations

Look at the operations that repeat when we add or remove items.

• Primary operation: Inserting or removing at the front uses list insert(0, item) or pop(0).
• How many times: Each add or remove at front shifts all other elements, so it repeats work proportional to the number of items.
• Adding or removing at the rear uses append() or pop() which work directly at the end without shifting.

How Execution Grows With Input

Adding or removing at the rear stays fast no matter how many items there are.

But adding or removing at the front takes longer as the list grows because all items must move.

Input Size (n)	Approx. Operations for front insert/pop	Approx. Operations for rear append/pop
10	10 shifts	1 operation
100	100 shifts	1 operation
1000	1000 shifts	1 operation

Pattern observation: Front operations grow linearly with n, rear operations stay constant.

Final Time Complexity

Time Complexity: O(n) for front insert/remove, O(1) for rear insert/remove

This means adding or removing at the front takes longer as the deque grows, but rear operations stay fast.

Common Mistake

[X] Wrong: "All deque operations are always fast and take the same time."

[OK] Correct: Using a list, front operations shift all items, so they take longer as size grows, unlike rear operations.

Interview Connect

Understanding how different deque operations scale helps you choose the right data structure and explain your choices clearly in interviews.

Self-Check

"What if we used a linked list instead of a Python list? How would the time complexity of front insert and remove change?"