Delete Node by Value in DSA Python - Time & Space Complexity

Time Complexity: Delete Node by Value

O(n)

Understanding Time Complexity

When we delete a node by value from a linked list, we want to know how long it takes as the list grows.

We ask: How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def delete_node(head, value):
    if not head:
        return None
    if head.val == value:
        return head.next
    current = head
    while current.next and current.next.val != value:
        current = current.next
    if current.next:
        current.next = current.next.next
    return head

This code removes the first node with the given value from a singly linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the linked list nodes one by one.
• 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 gets longer, the time to find the node grows roughly in a straight line.

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

Pattern observation: The time grows directly with the number of nodes; doubling nodes roughly doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the list size.

Common Mistake

[X] Wrong: "Deleting a node by value always takes constant time because we just remove it."

[OK] Correct: We must first find the node, which can take time proportional to the list length.

Interview Connect

Understanding this helps you explain how linked lists work and how operations scale, a key skill in many coding discussions.

Self-Check

"What if the list was doubly linked? How would the time complexity change when deleting a node by value?"