Delete Node at Specific Position in DSA C++ - Deep Dive

Overview - Delete Node at Specific Position

What is it?

Deleting a node at a specific position means removing an element from a linked list at the exact place you choose. A linked list is a chain of connected nodes, each holding data and a link to the next node. This operation changes the list by cutting out one node and linking its neighbors directly. It helps keep the list updated by removing unwanted or outdated data.

Why it matters

Without the ability to delete nodes at specific positions, linked lists would become cluttered with old or irrelevant data, making them inefficient and harder to use. This operation allows programs to manage memory better and keep data organized, which is crucial in many applications like managing playlists, undo features, or dynamic data sets. Without it, lists would grow uncontrollably or require rebuilding from scratch.

Where it fits

Before learning this, you should understand what linked lists are and how to traverse them. After mastering deletion at specific positions, you can learn about more complex linked list operations like reversing, sorting, or handling doubly linked lists.

Mental Model

Core Idea

Deleting a node at a specific position means carefully skipping over that node by changing the link of the previous node to point to the next node, effectively removing it from the chain.

Think of it like...

Imagine a paper chain where each paper ring is linked to the next. To remove one ring in the middle, you open the previous ring and link it directly to the ring after the one you want to remove, so the chain stays connected without that ring.

Head -> [Node1] -> [Node2] -> [Node3] -> [Node4] -> null

To delete Node3 at position 3:

Step 1: Find Node2 (previous node)
Step 2: Change Node2's next pointer from Node3 to Node4
Result: Head -> [Node1] -> [Node2] -> [Node4] -> null

Build-Up - 6 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect.

A linked list is a sequence of nodes where each node contains data and a pointer to the next node. The first node is called the head. The last node points to null, marking the end. Traversing means moving from one node to the next using these pointers.

Result

You can visualize a chain of nodes connected by pointers, starting from the head and ending at null.

Understanding the basic structure of linked lists is essential because deletion depends on changing these connections without breaking the chain.

2

Foundation

Traversing to a Specific Position

Concept: Learn how to move through the list to reach a node at a given position.

To delete a node at position 'pos', you first need to reach the node just before it (position pos-1). Start at the head and move forward one node at a time, counting positions until you reach pos-1. This node's pointer will be changed to skip the node at pos.

Result

You can identify the node before the one you want to delete, which is necessary to update links.

Knowing how to traverse to the correct position prevents errors like deleting the wrong node or breaking the list.

3

Intermediate

Deleting the Head Node

🤔Before reading on: do you think deleting the first node requires changing the head pointer or just the next pointer of the first node? Commit to your answer.

Concept: Deleting the first node is a special case because the head pointer itself must change.

If the position to delete is 1, simply move the head pointer to the second node. The original first node is then disconnected and can be deleted. This updates the start of the list correctly.

Result

The head now points to the second node, and the first node is removed from the list.

Handling the head node separately is crucial because it changes the entry point to the list, unlike other nodes where only links between nodes change.

4

Intermediate

Deleting a Node in the Middle or End

🤔Before reading on: do you think deleting a node in the middle requires updating the previous node's next pointer or the next node's pointer? Commit to your answer.

Concept: For nodes other than the head, deletion involves changing the previous node's next pointer to skip the node to delete.

After reaching the node before the target, update its next pointer to point to the node after the target. Then delete the target node. This removes the target from the chain without breaking links.

Result

The list remains connected, but the target node is removed.

Understanding pointer updates ensures the list stays intact and prevents memory leaks or broken chains.

5

Advanced

Handling Invalid Positions Gracefully

🤔Before reading on: do you think deleting a node at a position beyond the list length should cause an error or be ignored? Commit to your answer.

Concept: Robust deletion checks if the position is valid before attempting removal.

Before deletion, count nodes or check if traversal reaches null before the target position. If the position is invalid (less than 1 or beyond list length), do nothing or return an error. This prevents crashes or undefined behavior.

Result

The program safely handles invalid positions without corrupting the list.

Validating input positions protects the program from runtime errors and ensures stability.

6

Expert

Memory Management and Avoiding Leaks

🤔Before reading on: do you think simply unlinking a node frees its memory automatically? Commit to your answer.

Concept: Deleting a node requires both unlinking it and freeing its memory to avoid leaks.

In languages like C++, after unlinking the node, you must explicitly delete it to free memory. Failing to do so causes memory leaks, which waste resources and can crash programs over time.

Result

Memory used by the deleted node is returned to the system, keeping the program efficient.

Knowing the difference between unlinking and freeing memory is key to writing safe, efficient code in manual memory management environments.

Under the Hood

Internally, a linked list node contains a data field and a pointer to the next node. Deleting a node at a specific position involves changing the pointer of the previous node to point to the node after the one being deleted. This skips the target node, removing it from the chain. In manual memory management languages, the deleted node's memory must be explicitly freed to avoid leaks. The head pointer is updated if the first node is deleted.

Why designed this way?

Linked lists were designed to allow dynamic memory use and easy insertion or deletion without shifting elements, unlike arrays. The pointer-based structure makes deletion efficient by only changing links, not moving data. Explicit memory management gives programmers control but requires careful handling to avoid leaks. Alternatives like arrays trade off flexibility for direct indexing.

Head -> [Node1|*] -> [Node2|*] -> [Node3|*] -> [Node4|null]

Delete Node3 at position 3:

Step 1: Previous node (Node2) pointer (*) changes from Node3 to Node4
Step 2: Node3 is unlinked and deleted

Result:
Head -> [Node1|*] -> [Node2|*] -> [Node4|null]

Myth Busters - 4 Common Misconceptions

Quick: Do you think deleting a node automatically frees its memory in C++? Commit to yes or no.

Common Belief: Deleting a node means it is removed and its memory is freed automatically.

Reality: Unlinking a node only removes it from the list; you must explicitly delete it to free memory in C++.

Why it matters: Failing to free memory causes leaks, which waste resources and can crash long-running programs.

Quick: Do you think you can delete a node at position 0 in a 1-based linked list? Commit to yes or no.

Common Belief: Position 0 is a valid position to delete a node.

Reality: Positions in linked lists start at 1; position 0 is invalid and should be handled as an error.

Why it matters: Ignoring this causes undefined behavior or crashes when trying to delete at invalid positions.

Quick: Do you think deleting the last node requires special handling different from other nodes? Commit to yes or no.

Common Belief: Deleting the last node is the same as deleting any other node and needs no special care.

Reality: Deleting the last node requires updating the previous node's next pointer to null to mark the new end of the list.

Why it matters: Failing to update the last node's pointer causes dangling pointers and potential runtime errors.

Quick: Do you think deleting a node in a singly linked list requires access to the node itself? Commit to yes or no.

Common Belief: You can delete a node if you have a pointer to it, without needing the previous node.

Reality: In singly linked lists, you must have access to the previous node to update its next pointer; otherwise, deletion is not possible.

Why it matters: Trying to delete without the previous node leads to broken links and corrupted lists.

Expert Zone

1

When deleting nodes frequently, maintaining a tail pointer can optimize deletion at the end by avoiding full traversal.

2

In multi-threaded environments, deletion must be synchronized to prevent race conditions and corrupted lists.

3

Using sentinel (dummy) head nodes simplifies deletion logic by removing special cases for head deletion.

When NOT to use

Deleting nodes at specific positions is inefficient for very large lists if done repeatedly at random positions because traversal is O(n). In such cases, data structures like balanced trees or indexed skip lists offer faster random access and deletion.

Production Patterns

In real systems, deletion at specific positions is often combined with validation and error handling. For example, text editors use linked lists for undo stacks, deleting nodes as actions are undone. Memory pools or custom allocators are used to manage node memory efficiently and avoid fragmentation.

Connections

Array Deletion

Both involve removing elements, but arrays require shifting elements while linked lists only change pointers.

Understanding linked list deletion highlights the tradeoff between pointer manipulation and data movement, which is key in choosing data structures.

Garbage Collection

Manual deletion in linked lists contrasts with automatic memory management in garbage-collected languages.

Knowing manual deletion deepens appreciation for garbage collection's role in preventing memory leaks and simplifies programming.

Supply Chain Management

Deleting a node is like removing a step in a supply chain process and reconnecting the previous step to the next.

This cross-domain link shows how managing connections and dependencies is a universal problem beyond programming.

Common Pitfalls

#1 Trying to delete a node without updating the previous node's next pointer.

Wrong approach:

Node* temp = head;
for (int i = 1; i < pos; i++) {
temp = temp->next;
}
// delete temp without changing previous node's next
delete temp;

Correct approach:

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

Root cause:

Not realizing that the previous node's pointer must be updated to maintain list integrity.

#2 Not handling deletion of the head node separately.

Wrong approach:

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

Correct approach:

if (pos == 1) {
Node* toDelete = head;
head = head->next;
delete toDelete;
} else {
Node* temp = head;
for (int i = 1; i < pos - 1; i++) {
temp = temp->next;
}
Node* toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;
}

Root cause:

Treating head deletion like other nodes ignores that head pointer must be updated.

#3 Deleting a node at a position beyond the list length without checks.

Wrong approach:

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

Correct approach:

if (pos < 1) {
return;
}
if (pos == 1) {
if (head == nullptr) {
return;
}
Node* toDelete = head;
head = head->next;
delete toDelete;
return;
}
Node* temp = head;
int count = 1;
while (temp != nullptr && count < pos - 1) {
temp = temp->next;
count++;
}
if (temp == nullptr || temp->next == nullptr) {
// position invalid, do nothing or error
return;
}
Node* toDelete = temp->next;
temp->next = toDelete->next;
delete toDelete;

Root cause:

Not validating position leads to null pointer dereference and crashes.

Key Takeaways

Deleting a node at a specific position in a linked list requires careful pointer updates to maintain the chain.

Special handling is needed when deleting the head node because it changes the starting point of the list.

Always validate the position to avoid errors or crashes when deleting nodes.

In manual memory management languages, unlinking a node is not enough; you must also free its memory to prevent leaks.

Understanding these details ensures safe, efficient, and correct manipulation of linked lists in real-world programs.

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