Delete Node at End in DSA C

Mental Model

To remove the last item in a chain, find the second last and cut off its link to the last.

Analogy: Imagine a chain of paper clips linked together. To remove the last clip, you hold the second last clip and unhook the last one.

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

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, delete node at end

Goal: Remove the last node so the list ends at node 2

Step 1: start at head node 1

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

Why: We begin from the start to find the second last node

Step 2: move to node 2, check next node

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

Why: We need to find the node before the last one

Step 3: node 2's next is node 3 which is last, set node 2's next to null

head -> 1 -> 2 -> null

Why: Cutting off the last node removes it from the list

Result:

head -> 1 -> 2 -> null

Annotated Code

DSA C

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

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

// Function to delete node at end
void deleteAtEnd(struct Node** head_ref) {
    if (*head_ref == NULL) return; // empty list

    if ((*head_ref)->next == NULL) { // only one node
        free(*head_ref);
        *head_ref = NULL;
        return;
    }

    struct Node* temp = *head_ref;
    // move to second last node
    while (temp->next->next != NULL) {
        temp = temp->next;
    }

    free(temp->next); // free last node
    temp->next = NULL; // cut link to last node
}

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

// Driver code
int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    deleteAtEnd(&head);
    printList(head);

    // Free remaining nodes
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
    return 0;
}

if (*head_ref == NULL) return; // empty list

handle empty list by returning immediately

if ((*head_ref)->next == NULL) { free(*head_ref); *head_ref = NULL; return; }

handle single node list by freeing and setting head to null

while (temp->next->next != NULL) { temp = temp->next; }

advance temp to second last node

free(temp->next); temp->next = NULL;

free last node and cut link from second last

Output

1 -> 2 -> null

Complexity Analysis

Time: O(n) because we traverse the list once to find the second last node

Space: O(1) because we only use a few pointers regardless of list size

vs Alternative: Compared to removing from the front which is O(1), deleting at end requires traversal making it slower

Edge Cases

empty list

function returns immediately without error

DSA C

if (*head_ref == NULL) return; // empty list

single node list

node is freed and head set to null

DSA C

if ((*head_ref)->next == NULL) { free(*head_ref); *head_ref = NULL; return; }

When to Use This Pattern

When you need to remove the last item in a linked list, look for the pattern of finding the second last node and cutting its link.

Common Mistakes

Mistake: Trying to free the last node without updating the second last node's next pointer
Fix: Always set the second last node's next pointer to null after freeing the last node

Summary

Deletes the last node from a singly linked list.

Use when you want to remove the tail element from a linked list.

The key is to find the second last node and set its next pointer to null.

Practice

1. What is the main purpose of the Delete Node at End operation in a singly linked list?

easy

A. To reverse the linked list

B. To add a new node at the end of the linked list

C. To delete the first node of the linked list

D. To remove the last node from the linked list

Solution

1. Step 1: Understand the operation's goal

   The operation aims to remove the last node in the linked list, which is the node that points to null.

2. Step 2: Identify the correct description

   Removing the last node means deleting the node at the end, not adding or reversing nodes.

3. Final Answer:

   To remove the last node from the linked list -> Option D

4. Quick Check:

   Delete Node at End = Remove last node [OK]

Hint: Deleting at end means removing the last node [OK]

Common Mistakes:

• Confusing delete at end with delete at beginning
• Thinking it adds a node instead of deleting
• Mixing up with reversing the list

2. Which of the following C code snippets correctly deletes the last node of a singly linked list named head?

easy

A. if (head == NULL || head->next == NULL) return; Node* temp = head; while (temp->next->next != NULL) temp = temp->next; free(temp->next); temp->next = NULL;

B. Node* temp = head; while (temp->next != NULL) temp = temp->next; free(temp);

C. free(head); head = NULL;

D. Node* temp = head; while (temp->next != NULL) temp = temp->next; temp->next = NULL;

Solution

1. Step 1: Check for empty or single-node list and traverse to second last node

   if (head == NULL || head->next == NULL) return; Node* temp = head; while (temp->next->next != NULL) temp = temp->next; free(temp->next); temp->next = NULL; checks if list is empty or single node, then moves to the node before last using temp->next->next != NULL.

2. Step 2: Free last node and update pointer

   It frees the last node and sets temp->next to NULL, correctly deleting the last node.

3. Final Answer:

   if (head == NULL || head->next == NULL) return; Node* temp = head; while (temp->next->next != NULL) temp = temp->next; free(temp->next); temp->next = NULL; -> Option A

4. Quick Check:

   Traverse to second last, free last, set next NULL = if (head == NULL || head->next == NULL) return; Node* temp = head; while (temp->next->next != NULL) temp = temp->next; free(temp->next); temp->next = NULL; [OK]

Hint: Stop at second last node before deleting last [OK]

Common Mistakes:

• Freeing node without updating previous node's next pointer
• Not checking for empty list
• Freeing head without traversal

3. What will be the output linked list after deleting the last node from the list: 10 -> 20 -> 30 -> 40 -> NULL using the standard delete at end operation?

medium

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

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

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

D. 10 -> 20 -> NULL

Solution

1. Step 1: Identify the last node

   The last node is 40, which points to NULL.

2. Step 2: Remove the last node and update the second last node's next pointer

   After deletion, 30 becomes the last node and its next pointer is set to NULL.

3. Final Answer:

   10 -> 20 -> 30 -> NULL -> Option B

4. Quick Check:

   Last node 40 removed = 10 -> 20 -> 30 -> NULL [OK]

Hint: Last node removed, second last points to NULL [OK]

Common Mistakes:

• Not updating second last node's next pointer
• Deleting wrong node (like first node)
• Output list unchanged

4. Consider the following code snippet to delete the last node of a singly linked list. What is the error?

void deleteEnd(Node** head) {
  if (*head == NULL) return;
  Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  free(temp);
  temp = NULL;
}

medium

A. It does not update the second last node's next pointer to NULL

B. It frees the head node instead of the last node

C. It causes a segmentation fault by accessing NULL pointer

D. It deletes the first node instead of the last

Solution

1. Step 1: Analyze traversal logic

   The loop moves temp to the last node (where temp->next is NULL).

2. Step 2: Check pointer update after freeing

   It frees the last node but does not update the second last node's next pointer to NULL, leaving a dangling pointer.

3. Final Answer:

   It does not update the second last node's next pointer to NULL -> Option A

4. Quick Check:

   Missing next pointer update causes dangling pointer [OK]

Hint: Always update second last node's next to NULL after free [OK]

Common Mistakes:

• Freeing node without updating previous node's next
• Not handling empty list
• Incorrect loop condition causing crash

5. You have a singly linked list with nodes: 5 -> 15 -> 25 -> 35 -> 45 -> NULL. Write the steps to delete the last node and then insert a new node with value 50 at the end. What will be the final list?

hard

A. 5 -> 15 -> 25 -> 35 -> NULL

B. 5 -> 15 -> 25 -> 35 -> 45 -> 50 -> NULL

C. 5 -> 15 -> 25 -> 35 -> 50 -> NULL

D. 50 -> 5 -> 15 -> 25 -> 35 -> NULL

Solution

1. Step 1: Delete the last node (45)

   Traverse to second last node (35), free last node (45), set 35's next to NULL.

2. Step 2: Insert new node with value 50 at end

   Traverse to last node (35), create new node with 50, set 35's next to new node, new node's next to NULL.

3. Final Answer:

   5 -> 15 -> 25 -> 35 -> 50 -> NULL -> Option C

4. Quick Check:

   Delete last, then add 50 at end = 5 -> 15 -> 25 -> 35 -> 50 -> NULL [OK]

Hint: Delete last node, then add new node at end [OK]

Common Mistakes:

• Not updating pointers correctly after deletion
• Appending new node without deleting last
• Inserting new node at wrong position