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 :
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 :