Delete from End of Doubly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Delete from End of Doubly Linked List

O(1)

Understanding Time Complexity

When we delete a node from the end of a doubly linked list, we want to know how the time it takes changes as the list grows.

We ask: How many steps does it take to remove the last node when the list size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def delete_from_end(self):
        if not self.tail:
            return  # List is empty
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None
    

This code removes the last node from a doubly linked list by updating pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the tail node and updating pointers.
• How many times: This happens once per deletion, no loops or recursion involved.

How Execution Grows With Input

Deleting from the end always takes the same number of steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	5 steps
100	5 steps
1000	5 steps

Pattern observation: The number of steps stays the same as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means deleting from the end takes a constant amount of time regardless of list size.

Common Mistake

[X] Wrong: "Deleting from the end takes longer as the list grows because we have to find the last node."

[OK] Correct: The doubly linked list keeps a direct reference to the last node (tail), so no searching is needed.

Interview Connect

Knowing that deleting from the end of a doubly linked list is quick shows you understand how pointers help save time in data structures.

Self-Check

"What if we did not keep a tail pointer? How would the time complexity of deleting from the end change?"