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

Time Complexity: Dequeue Using Linked List

O(n)

Understanding Time Complexity

We want to understand how fast operations like adding or removing items work in a dequeue built with a linked list.

How does the time taken change as we add more items?

Scenario Under Consideration

Analyze the time complexity of these dequeue operations using a linked list.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Dequeue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue_front(self, data):
        new_node = Node(data)
        if not self.front:
            self.front = self.rear = new_node
        else:
            new_node.next = self.front
            self.front = new_node

    def dequeue_rear(self):
        if not self.rear:
            return None
        if self.front == self.rear:
            temp = self.rear
            self.front = self.rear = None
            return temp.data
        current = self.front
        while current.next != self.rear:
            current = current.next
        temp = self.rear
        self.rear = current
        self.rear.next = None
        return temp.data

This code adds an item at the front and removes an item from the rear of the dequeue using a linked list.

Identify Repeating Operations

Look for loops or repeated steps in the code.

• Primary operation: The while loop in dequeue_rear that moves through nodes to find the one before the rear.
• How many times: It runs once for each node except the last, so up to n-1 times if there are n nodes.

How Execution Grows With Input

As the number of items grows, the time to remove from the rear grows too 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 roughly in a straight line with the number of items.

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 items.

Common Mistake

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

[OK] Correct: Even with a rear pointer, we must find the node before rear to update its next link, which takes time proportional to the list size.

Interview Connect

Understanding how linked list operations scale helps you explain trade-offs clearly and choose the right data structure for the job.

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?