Delete Node at Specific Position in DSA Python - Time & Space Complexity

Time Complexity: Delete Node at Specific Position

O(n)

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?"

Practice

1. What happens when you delete a node at position 0 in a singly linked list?

easy

A. The last node is removed

B. The list remains unchanged

C. The head node is removed and the next node becomes the new head

D. All nodes are deleted

Solution

1. Step 1: Understand position 0 in linked list

   Position 0 refers to the head node of the list.

2. Step 2: Effect of deleting head node

   Deleting the head means the next node becomes the new head.

3. Final Answer:

   The head node is removed and the next node becomes the new head -> Option C

4. Quick Check:

   Deleting position 0 removes head [OK]

Hint: Deleting position 0 always removes the head node [OK]

Common Mistakes:

• Thinking last node is deleted at position 0
• Assuming list stays same after deletion
• Deleting all nodes instead of one

2. Which of the following is the correct syntax to delete a node at position pos in a singly linked list in Python?

easy

A. head = head.next if pos == 1 else head

B. if pos == 0: head = head.next

C. head.next = head if pos == 0 else head.next

D. head = head.prev if pos == 0 else head.next

Solution

1. Step 1: Check deletion at position 0

   Deleting at position 0 means moving head to next node.

2. Step 2: Verify syntax correctness

   if pos == 0: head = head.next correctly assigns head to head.next when pos is 0.

3. Final Answer:

   if pos == 0: head = head.next -> Option B

4. Quick Check:

   Correct syntax for deleting head node [OK]

Hint: Deleting head means head = head.next [OK]

Common Mistakes:

• Using head.prev which doesn't exist in singly linked list
• Wrong condition for position check
• Assigning head incorrectly

3. What will be the linked list after deleting the node at position 2 from the list: 10 -> 20 -> 30 -> 40 -> null?

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

def delete_node(head, pos):
    if pos == 0:
        return head.next
    current = head
    for _ in range(pos - 1):
        current = current.next
    current.next = current.next.next
    return head

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head = delete_node(head, 2)

# Print list
current = head
result = []
while current:
    result.append(current.data)
    current = current.next
print(result)

medium

A. [10, 20, 40]

B. [10, 30, 40]

C. [20, 30, 40]

D. [10, 20, 30, 40]

Solution

1. Step 1: Identify node at position 2

   Position 2 node has value 30 in the list 10 -> 20 -> 30 -> 40.

2. Step 2: Delete node at position 2

   Node 20's next pointer is updated to node 40, skipping node 30.

3. Final Answer:

   [10, 20, 40] -> Option A

4. Quick Check:

   Deleted node 30 at position 2 [OK]

Hint: Skip node at position by linking previous to next [OK]

Common Mistakes:

• Deleting wrong node due to off-by-one error
• Not updating next pointer correctly
• Returning wrong head

4. Find the error in the following code snippet that deletes a node at position pos in a singly linked list:

def delete_node(head, pos):
    if pos == 0:
        head = head.next
    current = head
    for _ in range(pos - 1):
        current = current.next
    current.next = current.next.next
    return head

medium

A. No error, code is correct

B. Loop runs one time too many

C. current.next.next may cause AttributeError if current.next is None

D. Missing return after deleting head node

Solution

1. Step 1: Check deletion at position 0

   When pos is 0, head is updated but not returned immediately.

2. Step 2: Effect of missing return

   Code continues and tries to access current.next causing errors or wrong behavior.

3. Final Answer:

   Missing return after deleting head node -> Option D

4. Quick Check:

   Return immediately after deleting head [OK]

Hint: Return immediately after deleting head node [OK]

Common Mistakes:

• Not returning head after deleting first node
• Ignoring edge cases when list is empty
• Assuming current.next always exists

5. Given a singly linked list 5 -> 10 -> 15 -> 20 -> 25 -> null, write the resulting list after deleting nodes at positions 0, 2, and then 1 in that order. What is the final list?

hard

A. [10, 25]

B. [10, 15, 25]

C. [10, 20]

D. [5, 15, 25]

Solution

1. Step 1: Delete node at position 0

   Deleting head (5), list becomes 10 -> 15 -> 20 -> 25.

2. Step 2: Delete node at position 2

   Node at position 2 is 20, deleting it results in 10 -> 15 -> 25.

3. Step 3: Delete node at position 1

   Node at position 1 is 15, deleting it results in 10 -> 25.

4. Final Answer:

   [10, 25] -> Option A

5. Quick Check:

   Sequential deletions update list correctly [OK]

Hint: Delete nodes stepwise, update positions after each deletion [OK]

Common Mistakes:

• Not updating list after each deletion
• Confusing positions after deletions
• Deleting wrong nodes due to static indexing