Steps to delete a node in a Linked List

In order to delete a node at a given position in Singly linked list, we need follow the below steps.

1. Find the previous node of the node to be deleted
2. Remove the node to be deleted
3. Reconnect the link list to change the next of the previous node
4. Free the allocated memory of the removed node.

Different ways to delete the node in a Linked list.

1.Delete a node from the beginning
2.Delete a node from a certain position
3.Delete a node from the end

Example

Input: position = 3, Linked List = 72->13->59->17->33->80
Output: Linked List = 72->13->17->33->80

Program to delete a node from a Linked list in C++

#include

using namespace std;

//Declare Node
struct node
{
   int data;
   node * next;
};

//Insert node at start
void insertNode(node **head,int data)
{
   node *temp = new node; // temporary node created to add the new element
   temp->data = data;  // add data to temporary node
   temp->next = *head; // add the address of old head element to temporary node
   *head = temp;       // change temporary node to head node
}

//Delete the node at the given position
void deleteNode(node **head,int position)
{
  /*"prev" will point to the node
     whose position is before the node to be deleted.
     "temp" is a copy of head pointer*/

   node *temp = *head;
   node *prev;
   /*if head is NULL i.e. linked list
     is empty */
   if(temp == NULL)
      return;
   /*If the head is the node that is
   to be deleted*/
   if(position == 1)
   {
      *head = temp->next; //change head
      free(temp);      //free old head
      return;
   }

   /*Traversing till we find the
   node to be deleted*/
   for(int i=1 ; i!=position ; i++)
   {
      prev = temp;
      temp = temp->next;
   }

   /*This condition is true, if the
   data is not present in LL*/
   if(temp == NULL)
   {
      cout<<"\nData not present\n";
      return;
   }
   else
   {
      /*Deletion of the node*/
      prev->next = temp->next;
      free(temp);
   }
}
/*Function that is used to
print the Linked List*/
void display(node *head)
{
  while (head != NULL)
  {
     cout<data<<"-> ";
     head = head->next;
  }
   cout<<"NULL";
}
int main()
{
  node* head = NULL;
  insertNode(&head, 72);
  insertNode(&head, 13);
  insertNode(&head, 59);
  insertNode(&head, 17);
  insertNode(&head, 33);
  insertNode(&head, 80);

  cout<<"Created Linked list is:\n";
  display(head);

  /*Deleting node at position 3*/
  deleteNode(&head,3);
  cout<<"\n\nResultant Linked list is:\n";
  display(head);

   return 0;
}

Output

Recommended Articles

• Implementation of Linked List in C++ with examples