How to delete in a Linked List and its implementation in C++

In this post, I am going to discuss, How to delete in a Linked List and its implementation in C++. Deletion in a linked list can also be performed in 3 ways:

  1. Deleting a start node
  2. Deleting an internal node
  3. Deletion from the end

In the previous tutorial, I have discussed how to insert a node in the linked list in C++.

Deleting a start node in a linked list in C++

struct node* del_start(struct node* first,int value)
{
struct node *temp,*temp1;
 temp1=first;
 temp=first->next;
 if(temp1->data==value)
 {
   first=temp;
   del_start(temp1);
 }
 else
 {
    while(temp->data!=value)
    {
    temp=temp->next;
    temp1=temp1->next;
    }
 }

}

}

No need to worry about this, let me explain this in easy language.

  1. In the given function del_start, I have passed reference to the first node of the linked list and the value that we have to delete.
  2. Two temporary pointers are taken. One points to the first node and other points to next of the first node.
  3. If the value to be deleted is in a temporary variable, delete it and first now points to where another variable was pointing else goto 4.
  4.  Traverse the list until the value that we have to delete is found and delete it.

Deleting from the middle in a linked list

void del_mid(struct node *p)
{
if(p==NULL)
{
 printf("no element to delete in linked list");
}
else if(p->next)
{ struct node *f=temp,*h=NULL;
while(p && p->next && p->next->next)
{ h=f;
  f=f->next;
  p=p->next->next;
}
if(h)
{
  h->next=h->next->next;
  f->next=NULL;
  free(f);
  f=NULL;
}
else
{ printf("cannot delete.");
}

}
else 
printf("only one element present in linked list");
}

}

Explanation of the code:

  1. First of all, the address of the linked list is pass in the function as a parameter.
  2. Now, we are going to check whether or not the linked list is empty.If former(list is  not empty), goto 3.
  3.  If a node is there, we are going to check if there are nodes next to this node in the linked list.
  4. Now, simply delete the node from the linked list and we move the first to next node else goto 5.
  5. Print “only one element present in linked list” if condition given in 4 if false.

Deletion at the end of a linked list in C++

void del_end()
 { 
   struct node *temp,*temp1;
   if(first==NULL)
    { 
     printf("list is empty\n"); 
    }
  else if(first->next==NULL)
   { 
     first=NULL; 
     free(first);
   }
  else
   {
     temp=first;
      while(temp->next!=NULL)
       { 
         temp1=temp; 
         temp=temp->next; 
       } 
          temp1->next=NULL;
          free(temp); 
          printf("node deleted");
    }
 }

Explanation of the code:

  1. As we know, we have to delete the last node from list, we are not going pass any value as an argument.
  2. Check if list is empty or not. If former(i.e. list is not empty), check for whether there is only one node in the list.
  3. If there is only one node in the list, simply delete it, else goto 4.
  4. If there is more than one node in the list, we will traverse the list until we reach the last node.
  5. When the last node is found, we will free the memory allocated to last node and make the next of the second last node as null.

This was How to delete in a linked list and its implementation in C++. Also, give a read to, Program to Rotate Doubly linked list by N nodes in C++

Delete the middle element of a stack in C++

Leave a Reply