Deletion of the linked list can occur in different parts of the list. Some cases are:

1. Beginning of the linked list.
2. End of the linked list.
3. Given position in the linked list.

Let’s take a look at the schedule for each of these cases.

1. Deletion at beginning of the linked list:

• To remove the first node (primary node), copy the primary node to a temporary node.
• Make the second node the primary node.
• Now delete the temporary node.

head = head->next;

For example:

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_beginning();
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          if(n == 0)
          {
                   printf("Empty List\n");
                   exit(0);
          }
          else
          {
                   createList(n);
          }
          printf("\nThe List is \n");
          displayList();
          deletion_beginning();
          printf("\n\nAfter Deleting the first node, the List is\n");
          displayList();
          return 0;
          }
          void createList(int n)
          {
                   struct node *newNode, *temp;
                   int data, i;
                   head = (struct node *)malloc(sizeof(struct node));
                   if(head == NULL)
                   {
                             printf("Unable to allocate memory.");
                   }
                   else
                   {
                             printf("\nEnter the data of node 1: ");
                             scanf("%d", &data);
                             head->data = data;
                             head->next = NULL;
                             temp = head;
                   for(i=2; i<=n; i++)
                   {
                             newNode = (struct node *)malloc(sizeof(struct node));
                             if(newNode == NULL)
                             {
                                      printf("Unable to allocate memory.");
                                      break;
                             }
                             else
                             {
                             printf("\nEnter the data of node %d: ", i);
                             scanf("%d", &data);
                             newNode->data = data;
                             newNode->next = NULL;
                             temp->next = newNode;
                             temp = temp->next;
                             }
                   }
          }
}
void deletion_beginning()
{
          if(head == NULL)
          printf("\n The list is Empty\n");
          struct node *temp;
          temp = head;
          head = head -> next;
          free(temp);
}
void displayList()
{
          struct node *temp;
          if(head == NULL)
 {
          printf("List is empty.");
 }
else
{
          temp = head;
          while(temp != NULL)
          {
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

2. Deletion at end of the linked list:

• To remove the last node, start looping through the list from the parent node and continue scrolling until the address part of the node is null.
• Track the penultimate node with a temporary variable such as prev_node.
• If address part of node NULL, set address part of previous node to NULL and remove last node.

struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;

For example:

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_end();
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          createList(n);
          printf("\nThe List is \n");
          displayList();
          deletion_end();
          printf("\n\nAfter Deleting the last node, the List is\n");
          displayList();
          return 0;
}
void createList(int n)
{
          struct node *newNode, *temp;
          int data, i;
          head = (struct node *)malloc(sizeof(struct node));
          if(head == NULL)
          {
                   printf("Unable to allocate memory.");
          }
          else
          {
                   printf("\nEnter the data of node 1: ");
                   scanf("%d", &data);
                   head->data = data;
                   head->next = NULL;
                   temp = head;
          for(i=2; i<=n; i++)
          {
                   newNode = (struct node *)malloc(sizeof(struct node));
          if(newNode == NULL)
          {
                   printf("Unable to allocate memory.");
                   break;
          }
          else
          {
          printf("\nEnter the data of node %d: ", i);
          scanf("%d", &data);
          newNode->data = data;
          newNode->next = NULL;
          temp->next = newNode;
          temp = temp->next;
          }
          }
}
}
void deletion_end()
{
          if(head -> next == NULL)
          {
          free(head);
          head = NULL;
          }
          struct node *temp = head,*prev_node;
          while(temp -> next != NULL)
          {
                   prev_node = temp;
                   temp = temp -> next;
          }
          free(temp);
          prev_node -> next = NULL;
          }
          void displayList()       
          {
                   struct node *temp;
                   if(head == NULL)
                   {
          printf("List is empty.");
          }
          else
          {
                   temp = head;
          while(temp != NULL)
          {
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

3. Deletion at given position in the linked list:

• Now suppose you need to remove the node at position 2.
• Start scrolling through the list from the main node and move to that position.
• During your walkthrough, track past nodes to the node you want to remove.
• In this case, you must traverse node 2 to remove the second node and store node 1 in a temporary variable.
• Now the address part of node 2 is mapped to the address part of node 1 and node 2 is removed.

for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;

For example:

Here Code:

#include <stdio.h>
#include <stdlib.h>
struct node {
          int data;
          struct node *next;
}*head;
void createList(int n);
void deletion_given_pos(int pos);
void displayList();
int main()
{
          int n, data, pos;
          printf("\nEnter the total number of nodes: ");
          scanf("%d", &n);
          createList(n);
          printf("\nThe List is \n");
          displayList();
          printf("\nEnter the position : ");
          scanf("%d",&pos);
          deletion_given_pos(pos);
          printf("\n\nAfter Deleting the node at given position, the List is\n");
          displayList();
          return 0;
}
void createList(int n)
{
          struct node *newNode, *temp;
          int data, i;
          head = (struct node *)malloc(sizeof(struct node));
if(head == NULL)
{
          printf("Unable to allocate memory.");
}
else
{
          printf("\nEnter the data of node 1: ");
          scanf("%d", &data);
          head->data = data;
          head->next = NULL;
          temp = head;
for(i=2; i<=n; i++)
{
          newNode = (struct node *)malloc(sizeof(struct node));
          if(newNode == NULL)
          {
                   printf("Unable to allocate memory.");
                   break;
          }
          else
          {
                   printf("\nEnter the data of node %d: ", i);
                   scanf("%d", &data);
                   newNode->data = data;
                   newNode->next = NULL;
                   temp->next = newNode;
                   temp = temp->next;
          }
          }
}
}
void deletion_given_pos(int pos)
{
          if(head == NULL)
          {
                   free(head);
                   head = NULL;
          }
          struct node *temp = head,*prev_node;
          int count = 0;
          while(temp -> next != NULL && pos != count){
                   prev_node = temp; 
                   temp = temp -> next;
                   count = count + 1;
          }
          if(pos == count){
                   prev_node -> next = temp -> next; 
                   free(temp);
          }
}
void displayList(){
          struct node *temp;
          if(head == NULL){
                   printf("List is empty.");
          }
          else{
                   temp = head;
          while(temp != NULL){
                   printf("%d\t", temp->data);
                   temp = temp->next;
          }
          printf("\n");
          }
}

Conclusion:

In this article, you should learn that removing a node from a linked list also includes several locations where you can remove the node. You can remove the first node, the last node, or the k-th random node from the linked list. After deletion, the next and other pointers in the linked list must be adjusted properly to keep the linked list intact.

References:

• https://www.programiz.com/dsa/linked-list-operations
• https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
• https://www.faceprep.in/data-structures/linked-list-deleting-a-node/
• https://www.softwaretestinghelp.com/linked-list/

Fahad Ali

Intern & Technical Content Writer for Programmer’s Academy.

programmersacademy.in/register/