Delete a Node from Circular Linked List in DSA Python - Time & Space Complexity

Time Complexity: Delete a Node from Circular Linked List

O(n)

Understanding Time Complexity

We want to understand how long it takes to remove a node from a circular linked list.

Specifically, how the time grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def delete_node(head, key):
    if head is None:
        return None
    curr = head
    prev = None
    while True:
        if curr.data == key:
            if prev:
                prev.next = curr.next
            else:
                # Deleting head node
                if head.next == head:
                    return None
                temp = head
                while temp.next != head:
                    temp = temp.next
                temp.next = head.next
                head = head.next
            break
        prev = curr
        curr = curr.next
        if curr == head:
            break
    return head
    

This code deletes a node with a given value from a circular linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the circular linked list to find the node to delete.
• 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 a straight line.

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

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

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 in a circular linked list always takes constant time because it's linked."

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

Interview Connect

Understanding this helps you explain how linked lists work and how to handle circular references efficiently.

Self-Check

"What if the list was doubly linked? How would the time complexity change?"