Delete Node at Specific Position in DSA C

Mental Model

We remove a node from a linked list by changing the pointer of the previous node to skip the node to delete.

Analogy: Imagine a chain of paper clips linked together. To remove one clip in the middle, you unhook the clip before it and link it directly to the clip after it.

head -> 1 -> 2 -> 3 -> 4 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> null, delete node at position 2 (0-based)

Goal: Remove the node at position 2 so the list becomes 1 -> 2 -> 4 -> null

Step 1: Check if position is 0, if yes, remove head

head -> 1 -> 2 -> 3 -> 4 -> null

Why: We must handle deleting the first node differently

Step 2: Traverse to node before position 2 (node at position 1)

head -> 1 -> [curr->2] -> 3 -> 4 -> null

Why: We need the previous node to change its next pointer

Step 3: Change curr's next pointer to skip node at position 2

head -> 1 -> 2 -> 4 -> null

Why: Skipping the node removes it from the list

Result:

head -> 1 -> 2 -> 4 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to delete node at given position (0-based)
void deleteNodeAtPosition(Node** head_ref, int position) {
    if (*head_ref == NULL) return; // empty list

    Node* temp = *head_ref;

    // If head needs to be removed
    if (position == 0) {
        *head_ref = temp->next; // move head
        free(temp); // free old head
        return;
    }

    // Find previous node of the node to be deleted
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    // If position is more than number of nodes
    if (temp == NULL || temp->next == NULL) return;

    // Node temp->next is the node to delete
    Node* next = temp->next->next;

    free(temp->next); // free memory

    temp->next = next; // unlink deleted node
}

// Function to print the linked list
void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("null\n");
}

int main() {
    // Create list 1->2->3->4->null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);

    printf("Original list:\n");
    printList(head);

    // Delete node at position 2
    deleteNodeAtPosition(&head, 2);

    printf("List after deleting node at position 2:\n");
    printList(head);

    return 0;
}

if (position == 0) {

Check if head node needs to be deleted

*head_ref = temp->next;

Move head pointer to next node to remove first node

for (int i = 0; temp != NULL && i < position - 1; i++) { temp = temp->next; }

Traverse to node before the one to delete

if (temp == NULL || temp->next == NULL) return;

Check if position is valid

Node* next = temp->next->next;

Store pointer to node after the one to delete

free(temp->next);

Free memory of node to delete

temp->next = next;

Link previous node to node after deleted node

Output

Original list:

1 -> 2 -> 3 -> 4 -> null

List after deleting node at position 2:

1 -> 2 -> 4 -> null

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the position

Space: O(1) because we only use a few pointers and no extra data structures

vs Alternative: Compared to rebuilding the list or copying nodes, this method deletes in place with no extra space and linear time

Edge Cases

Empty list

Function returns immediately without changes

DSA C

if (*head_ref == NULL) return;

Delete head node (position 0)

Head pointer moves to next node, old head freed

DSA C

if (position == 0) { *head_ref = temp->next; free(temp); return; }

Position greater than list length

Function returns without changes

DSA C

if (temp == NULL || temp->next == NULL) return;

When to Use This Pattern

When asked to remove a node at a specific position in a linked list, use pointer traversal to find the previous node and adjust links to exclude the target node.

Common Mistakes

Mistake: Not handling deletion of the head node separately
Fix: Add a condition to check if position is 0 and update head pointer accordingly

Mistake: Not checking if position is out of bounds causing null pointer errors
Fix: Add checks to ensure the node before the target and the target node exist before deletion

Summary

Deletes a node at a given position in a singly linked list by adjusting pointers.

Use when you need to remove an element from anywhere in a linked list by position.

The key is to find the node before the target and link it to the node after the target to remove it.

Practice

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

easy

A. The list remains unchanged

B. The last node is removed

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 1 in linked list

   Position 1 refers to the head node of the list.

2. Step 2: Deleting 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 C

4. Quick Check:

   Deleting position 1 removes head [OK]

Hint: Deleting position 1 always removes 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. void deleteNode(struct Node* head, int pos);

B. void deleteNode(struct Node** head_ref, int pos);

C. void deleteNode(int pos, struct Node* head);

D. void deleteNode(int pos);

Solution

1. Step 1: Understand pointer usage for head modification

   To delete a node, the function must modify the head pointer if position 1 is deleted, so it needs a pointer to pointer.

2. Step 2: Check function parameters

   Only void deleteNode(struct Node** head_ref, int pos); uses struct Node** head_ref allowing head modification.

3. Final Answer:

   void deleteNode(struct Node** head_ref, int pos); -> Option B

4. Quick Check:

   Use pointer to pointer for head changes [OK]

Hint: Use double pointer to head to delete at any position [OK]

Common Mistakes:

• Using single pointer and expecting head to change
• Wrong parameter order
• Missing head pointer in parameters

3. Given the linked list: 10 -> 20 -> 30 -> 40 -> 50 -> NULL, what is the list after deleting the node at position 3?

medium

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

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

C. 10 -> 30 -> 40 -> 50 -> NULL

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

Solution

1. Step 1: Identify node at position 3

   Position 3 node is 30 in the list.

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

   Link node 20 to node 40, skipping 30.

3. Final Answer:

   10 -> 20 -> 40 -> 50 -> NULL -> Option A

4. Quick Check:

   Deleted 3rd node (30) correctly [OK]

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

Common Mistakes:

• Deleting wrong node position
• Not updating links correctly
• Removing head instead of position 3

4. Consider this code snippet to delete a node at position pos in a linked list:

void deleteNode(struct Node** head_ref, int pos) {
  struct Node* temp = *head_ref;
  if (pos == 1) {
    *head_ref = temp->next;
    free(temp);
    return;
  }
  for (int i = 1; temp != NULL && i < pos - 1; i++) {
    temp = temp->next;
  }
  if (temp == NULL || temp->next == NULL) return;
  struct Node* next = temp->next->next;
  free(temp->next);
  temp->next = next;
}

What is the bug in this code?

medium

A. It does not handle empty list when pos is 1

B. It frees the wrong node

C. It does not update head pointer correctly

D. It does not check if pos is valid

Solution

1. Step 1: Check deletion at position 1

   If list is empty (*head_ref is NULL), temp is NULL, so temp->next causes error.

2. Step 2: Identify missing empty list check

   Code should check if temp is NULL before accessing temp->next when pos == 1.

3. Final Answer:

   It does not handle empty list when pos is 1 -> Option A

4. Quick Check:

   Empty list check missing at head deletion [OK]

Hint: Always check if list is empty before deleting [OK]

Common Mistakes:

• Ignoring empty list case
• Assuming pos is always valid
• Not freeing the deleted node

5. You have a singly linked list: 5 -> 10 -> 15 -> 20 -> 25 -> NULL. You want to delete the node at position 6. What should happen after calling the delete function?

hard

A. The last node (25) is deleted

B. The function crashes due to invalid position

C. The head node (5) is deleted

D. The list remains unchanged because position 6 is invalid

Solution

1. Step 1: Check if position 6 exists in list

   List has 5 nodes, so position 6 is invalid.

2. Step 2: Behavior on invalid position

   Proper delete function should do nothing if position is invalid, leaving list unchanged.

3. Final Answer:

   The list remains unchanged because position 6 is invalid -> Option D

4. Quick Check:

   Invalid position means no deletion [OK]

Hint: Invalid position means no change to list [OK]

Common Mistakes:

• Deleting last node incorrectly
• Crashing due to no position check
• Deleting head by mistake