Delete Node at Specific Position in DSA C++ - Execution Trace

Concept Flow - Delete Node at Specific Position

Start at head

↓

Check if position is 0

|Yes↓

Delete head node

No↓

Traverse to node before position

↓

Check if next node exists

|No↓

Position invalid, stop

Yes↓

Delete node at position

Start from the head, if position is zero delete head. Otherwise, move to node before position, check if next node exists, then delete it.

Execution Sample

DSA C++

void deleteNode(Node*& head, int pos) {
  if (pos == 0) {
    Node* temp = head;
    head = head->next;
    delete temp;
    return;
  }
  Node* curr = head;
  for (int i = 0; i < pos - 1 && curr != nullptr; i++) {
    curr = curr->next;
  }
  if (curr == nullptr || curr->next == nullptr) return;
  Node* temp = curr->next;
  curr->next = temp->next;
  delete temp;
}

Deletes the node at the given position in a singly linked list.

Execution Table

Step	pos	curr position	curr node value	Condition	Action	List state
1	3	0	1	pos == 0? No	Move to next node	1 -> 2 -> 3 -> 4 -> 5 -> null
2	3	1	2	i < pos-1 and curr != nullptr? Yes	Move to next node	1 -> 2 -> 3 -> 4 -> 5 -> null
3	3	2	3	i < pos-1 and curr != nullptr? No	Stop loop	1 -> 2 -> 3 -> 4 -> 5 -> null
4	3	2	3	curr == nullptr or curr->next == nullptr? No	Delete node at pos	1 -> 2 -> 3 -> 5 -> null
5	3	-	-	End	Return	1 -> 2 -> 3 -> 5 -> null

💡 Position 3 node deleted, list updated and function returns

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
pos	3	3	3	3	3	3
curr position	0	0	1	2	2	2
curr node value	1	1	2	3	3	3
List	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 5 -> null	1 -> 2 -> 3 -> 5 -> null

Key Moments - 3 Insights

Why do we check if pos == 0 separately?

Because deleting the head node requires updating the head pointer itself, as shown in execution_table step 1 where pos == 0 leads to deleting the head.

What happens if position is greater than list length?

The loop stops when curr becomes nullptr or curr->next is nullptr, and the function returns without deleting, as in execution_table step 4 condition.

Why do we stop the loop at pos - 1?

Because we need to reach the node before the one to delete to update its next pointer, shown in execution_table steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of curr node?

A 3

B 2

C 4

D 1

💡 Hint

Check the 'curr node value' column at step 3 in execution_table

At which step does the node actually get deleted?

A Step 2

B Step 4

C Step 1

D Step 3

💡 Hint

Look at the 'Action' column in execution_table where deletion is mentioned

If pos was 0, what would be the list state after deletion?

A 2 -> 3 -> 4 -> 5 -> null

B 1 -> 3 -> 4 -> 5 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> null

D 2 -> 4 -> 5 -> null

💡 Hint

Refer to key_moments about deleting head node and how head pointer changes

Concept Snapshot

Delete Node at Specific Position in Linked List:
- If position is 0, delete head and update head pointer.
- Else, traverse to node before position.
- If next node exists, update pointers to skip it.
- Handle invalid positions by no action.
- Time complexity: O(n) for traversal.

Full Transcript

This visual execution traces deleting a node at a specific position in a singly linked list. We start by checking if the position is zero to delete the head node directly. If not, we move through the list to the node before the target position. We verify if the next node exists to avoid errors. Then, we update the next pointer to skip the node to delete and free its memory. The execution table shows each step with variable values and list state. Key moments clarify why we treat head deletion separately, how invalid positions are handled, and why we stop traversal at position minus one. The quiz tests understanding of node values at steps, when deletion occurs, and the effect of deleting the head node. The snapshot summarizes the approach and complexity.

Practice

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

easy

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

B. The last node is removed

C. The list remains unchanged

D. All nodes are deleted

Solution

1. Step 1: Understand position 1 in linked list

   Position 1 refers to the head node of the list.

2. Step 2: Delete the head node

   Removing 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 A

4. Quick Check:

   Deleting position 1 removes the head [OK]

Hint: Deleting position 1 means removing the head node [OK]

Common Mistakes:

• Thinking position 1 deletes the last node
• 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 C++?

easy

A. head = head->prev;

B. if (pos == 1) { head = head->next; }

C. delete head->next->prev;

D. head->next = NULL;

Solution

1. Step 1: Check deletion at position 1

   If position is 1, we update head to head->next to remove the first node.

2. Step 2: Verify syntax correctness

   if (pos == 1) { head = head->next; } correctly updates head pointer; others are invalid or incorrect for singly linked list.

3. Final Answer:

   if (pos == 1) { head = head->next; } -> Option B

4. Quick Check:

   Update head for position 1 deletion [OK]

Hint: For position 1, assign head = head->next [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Setting next pointer to NULL incorrectly
• Deleting wrong node pointer

3. What is the output linked list after deleting the node at position 3 from the list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL?

medium

A. 2 -> 3 -> 4 -> 5 -> NULL

B. 1 -> 2 -> 3 -> 5 -> NULL

C. 1 -> 3 -> 4 -> 5 -> NULL

D. 1 -> 2 -> 4 -> 5 -> NULL

Solution

1. Step 1: Identify node at position 3

   Node at position 3 is the node with value 3.

2. Step 2: Remove node 3 and link previous to next

   Link node 2's next to node 4, skipping node 3.

3. Final Answer:

   1 -> 2 -> 4 -> 5 -> NULL -> Option D

4. Quick Check:

   Node 3 removed, list links 2 to 4 [OK]

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

Common Mistakes:

• Removing wrong node
• Not updating previous node's next pointer
• Deleting head instead of position 3

4. Given the code snippet below, what is the error when deleting a node at position 4?

void deleteNode(Node*& head, int pos) {
  Node* temp = head;
  for (int i = 1; i < pos - 1; i++) {
    temp = temp->next;
  }
  Node* toDelete = temp->next;
  temp->next = toDelete->next;
  delete toDelete;
}

medium

A. No check if position is valid or if temp is NULL

B. Incorrect loop range causing off-by-one error

C. Deleting head node incorrectly

D. Using delete on a pointer not allocated with new

Solution

1. Step 1: Analyze loop and pointer usage

   The loop moves temp to node before position to delete, but no checks if temp or temp->next is NULL.

2. Step 2: Identify missing validation

   Without checking if position is valid or temp is NULL, code may crash on invalid positions.

3. Final Answer:

   No check if position is valid or if temp is NULL -> Option A

4. Quick Check:

   Missing boundary checks cause runtime errors [OK]

Hint: Always check pointers before accessing next [OK]

Common Mistakes:

• Ignoring invalid position inputs
• Assuming list length is sufficient
• Not checking for NULL pointers

5. You have a singly linked list: 10 -> 20 -> 30 -> 40 -> 50 -> NULL. Write the resulting list after deleting the node at position 5 and then deleting the node at position 1.

hard

A. 20 -> 30 -> 40 -> 50 -> NULL

B. 10 -> 20 -> 30 -> 40 -> NULL

C. 20 -> 30 -> 40 -> NULL

D. 10 -> 20 -> 30 -> NULL

Solution

1. Step 1: Delete node at position 5

   Node at position 5 is 50, removing it results in list: 10 -> 20 -> 30 -> 40 -> NULL.

2. Step 2: Delete node at position 1

   Deleting head node 10 updates head to 20, final list: 20 -> 30 -> 40 -> NULL.

3. Final Answer:

   20 -> 30 -> 40 -> NULL -> Option C

4. Quick Check:

   Delete last then head node sequentially [OK]

Hint: Delete last node first, then head node for correct order [OK]

Common Mistakes:

• Deleting head first then last causing wrong list
• Not updating head after deleting position 1
• Forgetting to remove last node