Deletion in Linked List

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.

Deletion in Linked List

head = head->next;

For example:

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

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.

Deletion in Linked List

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

For example:

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

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.

Deletion in Linked List

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

For example:

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

Deletion in Linked List

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:

(Visited 124 times, 1 visits today)

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
Ask ChatGPT
Set ChatGPT API key
Find your Secret API key in your ChatGPT User settings and paste it here to connect ChatGPT with your Tutor LMS website.
0
Would love your thoughts, please comment.x
()
x