Delete a Node In Linked List

Deleting a node in linked list is a fundamental operation. The process involves removing a node from the list while adjusting the pointers of the adjacent nodes to maintain the integrity of the list. There are a few different scenarios when deleting a node, the major are given below

• Deletion at the Beginning of Linked List
• Deletion at Specific Position of Linked List
• Deletion at the End of Linked List

Consider a following 5-nodes singly linked list, where head is pointing to 350 address to get the first node data (10).

1. Deletion at Beginning in a Linked List

When we delete a node from the beginning in a linked list, we are removing the head node, which is the first element in the list. This is a relatively simple operation compared to deleting nodes from other positions (like the middle or end) because we only need to update the head pointer to point to the second node in the list.

Step 01: temp_ptr = head;

• head: This is a pointer that points to the first node of the linked list. It is typically the entry point to the linked list.
• temp_ptr: This is a new pointer variable (often used temporarily) that will now hold the address of the first node (the same as head).

so, both temp_ptr and head are pointing to the same memory location (the first node of the list).

Step 02:head = temp_ptr->next;

• Here, temp_ptr->next refers to the node that comes after the current head node (i.e., the second node in the list).
• The head pointer is then updated to point to this second node (data =20).
• head now points to the second node

Step 03: free(temp_ptr);

• In your linked list, temp_ptr points to node1, which is the first node in the list.
• After updating head to point to the second node (head = temp_ptr->next;), node1 is no longer part of the list, but the memory it used is still allocated in the system.
• To avoid a memory leak (where memory is not properly freed), we call free(temp_ptr) to delete node1 from memory.

Output:

Finally we get the following output, after deletion of first node in the beginning of the singly linked list

The descriptive diagram, step 01 to 03 is given below

C Programming Code

C Programming Code for Deletion at the beginning in the singly linked list is given below

#include <stdio.h> #include <stdlib.h>// Define the node structure struct Node { int data; struct Node *next; };// Function to delete the first node struct Node* deleteFirstNode(struct Node* head) { if (head == NULL) { printf("The list is empty. Nothing to delete.\n"); return head; // Return unchanged head }struct Node* temp_ptr = head; // Temporary pointer to the current head head = head->next; // Move head to the next nodefree(temp_ptr); // Free the memory of the old head node printf("First node deleted.\n"); return head; // Return the new head } // Function to print the linked list void printList(struct Node* head) { if (head == NULL) { printf("The list is empty.\n"); return; } struct Node* temp_ptr = head; while (temp_ptr != NULL) { printf("%d -> ", temp_ptr->data); temp_ptr = temp_ptr->next; } printf("NULL\n"); } // Function to add a new node at the beginning struct Node* insertAtBeginning(struct Node* head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = head; head = newNode; // Move head to the new node return head; // Return the new head } // Main function int main() { struct Node* head = NULL; // Insert nodes at the beginning head = insertAtBeginning(head, 70); head = insertAtBeginning(head, 52); head = insertAtBeginning(head, 30); head = insertAtBeginning(head, 20); head = insertAtBeginning(head, 10); // Print original list printf("Original list:\n"); printList(head); // Delete the first node head = deleteFirstNode(head); // Print the list after deletion printf("List after deleting first node:\n"); printList(head); return 0; }

Output

Original list:
10 -> 20 -> 30 -> 52 -> 70 -> NULL
First node deleted.
List after deleting first node:
20 -> 30 -> 52 -> 70 -> NULL

2. Delete node at given position in a linked list

When dealing with linked lists, one of the common operations is deleting a node at a specific position. This operation allows us to remove a node from the list, re-linking the remaining nodes so that the list’s integrity is maintained. The position of the node to be deleted can vary, and we need to handle different cases based on the position.

Step 01: temp_ptr = head;

temp_ptr and head are pointing to first node of the list.

Step 02: Condition

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

This loop is used to find the node just before the one you want to delete in a singly linked list. To delete a node at a given position, we need to access the node before it.

Step 03 (part -1): nodeToDel_ptr = temp_ptr->next;

temp_ptr->next: This gives you the node that we want to delete. By storing this address in"nodeToDel_ptr", we can later safely free the memory of the node we want to delete without losing access to it.

Step 03 (part -2): temp_ptr->next = temp_ptr->next->next;

This statement changes the next pointer of temp_ptr to skip the node temp_ptr->next and point to the node after it. This effectively removes the node 30 from the linked list.

• Before (temp_ptr->next = temp_ptr->next->next;) statement, the temp_ptr->next was pointing to 700 address.
• After, (temp_ptr->next = temp_ptr->next->next;) statement, the temp_ptr->next is pointing to 900 address.

Step 04: free(nodeToDel_ptr);

free() is a C/C++ statement that deallocates or frees memory.  nodeToDel_ptr points to the node that is being deleted. The free(nodeToDel_ptr) function is then called to release the memory for this node.

Output:

Finally the output is given below

The descriptive diagram is given below for delete node at given position in a linked list

Code Example in C: delete a node at given position in a linked list

#include <stdio.h> #include <stdlib.h>// Define the structure for a node in the singly linked list struct Node { int data; struct Node* next; };// Function to insert a new node at the beginning of the list struct Node* insertAtBeginning(struct Node* head, int newData) {// Allocate memory for the new node struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));// Assign the data to the new node newNode->data = newData; // Make the next of new node as head newNode->next = head; // Return the new head of the list return newNode; } // Function to delete a node at a given position struct Node* deleteNodeAtPosition(struct Node* head, int position) { // If the list is empty, return NULL if (head == NULL) { printf("List is empty.\n"); return NULL; } struct Node* temp_ptr = head; // If the position is 0 (delete the head node) if (position == 0) { head = temp_ptr->next; // Move head to the next node free(temp_ptr); // Free memory of the old head node return head; } // Find the previous node of the node to be deleted for (int i = 0; temp_ptr != NULL && i < position - 1; i++) { temp_ptr = temp_ptr->next; } // If position is greater than the number of nodes if (temp_ptr == NULL || temp_ptr->next == NULL) { printf("Position out of bounds.\n"); return head; } // Node temp_ptr->next is the node to be deleted struct Node* nodeToDel_ptr = temp_ptr->next; // Renamed variable temp_ptr->next = temp_ptr->next->next; // Unlink the node from the list // Free memory free(nodeToDel_ptr); return head; } // Function to print the list void printList(struct Node* head) { struct Node* temp_ptr = head; // Rename ptr to temp_ptr while (temp_ptr != NULL) { printf("%d -> ", temp_ptr->data); temp_ptr = temp_ptr->next; } printf("NULL\n"); } int main() { // Initialize the list as empty (head is NULL) struct Node* head = NULL; // Inserting some nodes at the beginning head = insertAtBeginning(head, 70); head = insertAtBeginning(head, 52); head = insertAtBeginning(head, 30); head = insertAtBeginning(head, 20); head = insertAtBeginning(head, 10); // Print the list before deletion printf("Linked List before deletion: "); printList(head); // Delete node at position 2 (0-based indexing) to delete node 30 head = deleteNodeAtPosition(head, 2); // Print the list after deletion printf("Linked List after deletion: "); printList(head); return 0; }

Output: after deletion of 30.

Linked List before deletion: 10 -> 20 -> 30 -> 52-> 70 -> NULL
Linked List after deletion: 10 -> 20 -> 52-> 70 -> NULL

3. Delete a node at the end of linked list​

To delete the last node, you need to traverse the list until you reach the second-to-last node, and then update its next pointer to Null.

Step 01: temp_ptr = head;

temp_ptr and head pointers both are pointing to first node of the list.

Step 02: Condition

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

First itertion: Condition true

• temp_ptr->next pointing to the next node (380 address) after the current node (350 address) in second iteration.
• temp_ptr->next->next pointing to the node (700 address) after the next node (380 address) in first iteration.

Second itertion: Condition true

• temp_ptr->next pointing to the next node (700 address) after the current node (380 address) in second iteration.
• temp_ptr->next->next pointing to the node (900 address) after the next node (700 address) in first iteration.

Third itertion: Condition true

• temp_ptr->next pointing to the next node (900 address) after the current node (700 address) in second iteration.
• temp_ptr->next->next pointing to the node (1700 address) after the next node (900 address) in first iteration.

Fourth itertion: Condition False due to temp_ptr->next->next points to NULL

• temp_ptr->next pointing to the next node (1700 address) after the current node (900 address) in second iteration.
• temp_ptr->next->next pointing to the node (Null address) after the next node (1700 address) in first iteration.

So, temp_ptr reaches the second last node through this condition. 

Step 03: nodeToDel_Ptr = temp_ptr->next;

The statement assigns nodeToDel_Ptr to point to the last node. We need it because we will unlink this last node from the list by setting temp_ptr->next = NULL; later. So, we need a pointer to it in order to free its memory later. 

Step 04: temp_ptr->next = NULL;

As we use the nodeToDel_Ptr to point the last node already in step 03, now we can unlinke the last node from the list by setting temp_ptr->next = NULL;

Step 05: free(NodeToDel_ptr);

This statement deallocate the memroy used by last node through free() function. It is a final output, Following is the descriptive diagram for Delete a node at the end of linked list​

Example Code in C: Delete a node at the end of linked list​

#include <stdio.h> #include <stdlib.h>// Define the structure for a node in the singly linked list struct Node { int data; struct Node* next; };// Function to insert a new node at the beginning of the list struct Node* insertAtBeginning(struct Node* head, int newData) { // Allocate memory for the new node struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));// Assign the data to the new node newNode->data = newData;// Make the next of new node as head newNode->next = head; // Return the new head of the list return newNode; } // Function to delete the node at the end of the list struct Node* deleteNodeAtEnd(struct Node* head) { // If the list is empty, return NULL if (head == NULL) { printf("List is empty.\n"); return NULL; } // If there's only one node in the list if (head->next == NULL) { free(head); return NULL; // List is now empty } // Traverse the list to find the second-to-last node struct Node* temp_ptr = head; while (temp_ptr->next != NULL && temp_ptr->next->next != NULL) { temp_ptr = temp_ptr->next; } // Now temp_ptr is the second-to-last node struct Node* nodeToDel_Ptr = temp_ptr->next; // The node to be deleted (last node) temp_ptr->next = NULL; // Unlink the last node // Free memory of the node to be deleted free(nodeToDel_Ptr); return head; } // Function to print the list void printList(struct Node* head) { struct Node* temp_ptr = head; while (temp_ptr != NULL) { printf("%d -> ", temp_ptr->data); temp_ptr = temp_ptr->next; } printf("NULL\n"); } int main() { // Initialize the list as empty (head is NULL) struct Node* head = NULL; // Inserting some nodes at the beginning head = insertAtBeginning(head, 70); head = insertAtBeginning(head, 52); head = insertAtBeginning(head, 30); head = insertAtBeginning(head, 20); head = insertAtBeginning(head, 10); // Print the list before deletion printf("Linked List before deletion: "); printList(head); // Delete node at the end head = deleteNodeAtEnd(head); // Print the list after deletion printf("Linked List after deletion at the end: "); printList(head); return 0; }

Output: after deletion last node 72.

Linked List before deletion: 10 -> 20 -> 30 -> 52 -> 72 -> NULL
Linked List after deletion at the end: 10 -> 20 -> 30 -> 52 -> NULL

Time and Space Complexity of Linked List Deletion Operations

In linked lists, the time and space complexity of deletion operations can vary depending on the position where the deletion occurs. Let’s break it down into the three main cases: deletion at the beginning, deletion at a specific position, and deletion at the end.

1. Deletion at the Beginning of Linked List:

• Time Complexity: The time complexity for this operation is O(1) because we don’t need to traverse the list. We simply adjust the head pointer to point to the next node and free the old head node.
• Space Complexity: The space complexity is O(1) since no additional space is required beyond the pointers and memory for the node to be deleted.

2. Deletion at Specific Position of Linked List:

• Time Complexity: The time complexity for this operation is O(n), where n is the number of nodes in the list. In the worst case, we need to traverse the list to find the node just before the target node, which takes linear time.
• Space Complexity: The space complexity is O(1) since we only need a fixed amount of space (a few pointers) to perform the operation.

3. Deletion at the End of Linked List:

• Time Complexity: The time complexity for this operation is O(n), where n is the number of nodes in the list. We need to traverse the list to find the second-to-last node, which requires linear time.
• Space Complexity: The space complexity is O(1), since we are only using a fixed number of pointers regardless of the size of the list.

Summary of Time and Space Complexity for Deletion Operations:

Operation	Time Complexity	Space Complexity
Deletion at the Beginning	O(1)	O(1)
Deletion at a Specific Position	O(n)	O(1)
Deletion at the End	O(n)	O(1)