Delete by Value in Doubly Linked List in DSA Python - Time & Space Complexity

Time Complexity: Delete by Value in Doubly Linked List

O(n)

Understanding Time Complexity

When deleting a node by value in a doubly linked list, we want to know how the time taken changes as the list grows.

We ask: How long does it take to find and remove a node with a given value?

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

def delete_by_value(head, value):
    current = head
    while current:
        if current.data == value:
            # Remove current node
            if current.prev:
                current.prev.next = current.next
            if current.next:
                current.next.prev = current.prev
            if current == head:
                head = current.next
            break
        current = current.next
    return head
    

This code searches for the first node with the given value and removes it from the doubly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the list node by node to find the value.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the time to find the node grows roughly in direct proportion to the list size.

Input Size (n)	Approx. Operations
10	Up to 10 node checks
100	Up to 100 node checks
1000	Up to 1000 node checks

Pattern observation: The number of steps grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete by value grows linearly as the list gets longer.

Common Mistake

[X] Wrong: "Deleting by value in a doubly linked list is always fast and constant time because we can jump directly to the node."

[OK] Correct: We must first find the node by checking each one, which takes time proportional to the list size.

Interview Connect

Understanding this helps you explain how linked lists work and why searching affects performance, a key skill in many coding interviews.

Self-Check

"What if the list was sorted? How would that change the time complexity of deleting by value?"