how to delete a node in a linked list c++

How to delete a node in linked list :

Deleting a node in a linked list can be achieved by connecting the predecessor node with the successor node of the linked list.

For example, if we have one linked list with three nodes as like below :

How to delete a node in linked list

And, if we want to delete Node 2, we can do that by connecting Node 1 with Node 3. But, that will not delete Node 2 from memory. This is called garbage node and we should clean it. For that, we will use one extra pointer variable called temp. Before joining Node 1 with Node 3, we will keep the address of Node 2 in this temp variable. Then, after Node 1 is joined with Node 3, we can delete it using delete.

C++ program to delete a linked list node :

The below code snippet works as like I have explained above :

                          void              deleteNode              (Node              *nodeBefore)              {              Node              *temp;              temp              =              nodeBefore->next;              nodeBefore->next              =              temp->next;              delete              temp;              }

Here, nodeBefore is the node pointer before the node we are deleting.

To delete the head node, we need a bit of modification to the above program :

                          void              deleteHeadNode              (              )              {              Node              *temp;              temp              =              head;              head              =              head->next;              delete              temp;              }

Here, we are simply pointing the head to the next node and deleting the node that was pointed by head before.

Complete C++ program :

The below program illustrates how insertion and deletion works in a linked list in C++. This program can also display all nodes of a linked list.

We are deleting a node using its value.

                                          #                include                <iostream>                            using              namespace              std;              struct              Node              {              int              value;              Node              *next;              }              ;              class              LinkedList              {              Node              *head              =              NULL              ;              public              :              void              insertAtHead              (              int              value)              {              Node              *node              =              new              Node;              node->value              =              value;              if              (head              ==              NULL              )              {              node->next              =              NULL              ;              }              else              {              node->next              =              head;              }              head              =              node;              }              void              displayList              (              )              {              Node              *flag              =              head;              while              (flag              !=              NULL              )              {              cout              <<              "->"              <<              flag->value;              flag              =              flag->next;              }              cout              <<              endl;              }              void              deleteNode              (Node              *nodeBefore)              {              Node              *temp;              temp              =              nodeBefore->next;              nodeBefore->next              =              temp->next;              delete              temp;              }              void              deleteHeadNode              (              )              {              Node              *temp;              temp              =              head;              head              =              head->next;              delete              temp;              }              void              deleteNodeWithValue              (              int              value)              {              Node              *nodeBefore              =              head;              if              (nodeBefore->value              ==              value)              {              deleteHeadNode              (              )              ;              }              else              {              while              (nodeBefore->next->value              !=              value)              {              nodeBefore              =              nodeBefore->next;              if              (nodeBefore->next              ==              NULL              )              {              break              ;              }              }              if              (nodeBefore->next              ==              NULL              )              {              cout              <<              "Node not found"              <<              endl;              }              else              {              deleteNode              (nodeBefore)              ;              }              }              }              }              ;              int              main              (              )              {              int              choice,              value;              LinkedList linkedList;              while              (              1              )              {              int              exit              =              0              ;              cout              <<              "Enter 1 to insert, 2 to display, 3 to delete and -1 to exit :"              <<              endl;              cin              >>              choice;              switch              (choice)              {              case              -              1              :              exit              =              1              ;              break              ;              case              1              :              cout              <<              "Enter a value :"              <<              endl;              cin              >>              value;              linkedList.              insertAtHead              (value)              ;              break              ;              case              2              :              linkedList.              displayList              (              )              ;              break              ;              case              3              :              cout              <<              "Enter a value to delete :"              <<              endl;              cin              >>              value;              linkedList.              deleteNodeWithValue              (value)              ;              break              ;              }              if              (exit              ==              1              )              {              break              ;              }              }              return              0              ;              }

Here, deleteNodeWithValue method is used to delete a node using its value. If the node to delete is head node, it calls deleteHeadNode and for other nodes, it calls deleteNode.

Sample Output :

            Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              1              Enter a value              :              10              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              1              Enter a value              :              11              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              1              Enter a value              :              12              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              2              ->              12              ->              11              ->              10              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              3              Enter a value to              delete              :              11              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              2              ->              12              ->              10              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              3              Enter a value to              delete              :              12              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              2              ->              10              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              3              Enter a value to              delete              :              10              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :              2              Enter              1              to insert,              2              to display,              3              to              delete              and              -              1              to exit              :