Time Complexity: Delete Node at Specific Position
O(n)
0
0
Delete Node at Specific Position in DSA Python - Time & Space Complexity
Understanding Time Complexity
We want to know how long it takes to remove a node from a linked list at a certain position.
How does the time needed change 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, position):
if position == 0:
return head.next
current = head
for _ in range(position - 1):
current = current.next
current.next = current.next.next
return head
This code removes the node at the given position from a singly linked list.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Loop moving through the list to reach the node before the one to delete.
- How many times: Up to position - 1 times, depending on where the node is.
How Execution Grows With Input
As the list grows, the time to reach the node grows too, because we move step by step.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 9 steps |
| 100 | Up to 99 steps |
| 1000 | Up to 999 steps |
Pattern observation: The number of steps grows roughly in direct proportion to the position of the node.
Final Time Complexity
Time Complexity: O(n)
This means the time to delete a node grows linearly with the position of the node in the list.
Common Mistake
[X] Wrong: "Deleting a node always takes the same short time no matter where it is."
[OK] Correct: Because we must first walk through the list to find the node before the one to delete, so deleting near the end takes longer.
Interview Connect
Understanding how linked list operations scale helps you explain your code clearly and shows you know how data structures work under the hood.
Self-Check
"What if we had a doubly linked list? How would the time complexity of deleting a node at a specific position change?"