The node of the linked list looks like this:
As compared with the array, the linked list is not a sequential data structure because it is a dynamically stored data structure. It stores all the data in different memory locations and we can access this data through the pointer of the node which stores the address of the data.
This way of storing data has this benefits:
1. We do not have a pre-defined memory size like an array, which leads to lots of memory waste.
2. In an array, if we define one time memory, we can’t decrease or increase it according to our requirements. But in a linked list, we can increase or decrease the nodes according to our requirements.
The linked list is looks like this:
Every linked list has one header node which is the first node of the linked list; and one tail node which is present at the end of the linked list. From the tail node, the linked list pointing to the next node is over because it stores the null address, which means nothing. If any linked list has only one node, then it means the header node and tail node are the same.
Deletion of a linked list:
As given below, we can delete a node from a linked list in three ways:
1. Delete the first node of linked list
2. Delete the last node of linked list
3. Delete a specific position node
explanation of all these concepts:
1. Delete the first node of linked list(the header node):-
To delete the first node from the linked list means deleting the header node (first node) of the linked list. To do this, we have to follow the following procedure:
a. We have to create a pointer (temporary).
b. The address of the header node is copied to the pointer (temporary).
c. Now, we have stored the address of the header node. So, we can declare the next node of the header as a linked list first node.
Deleting the first node means the header node is simple:
C++ code to delete the first node from the linked list:
{
node *temporaryNode=new node;
temporaryNode=headNode;
headNode=headNode->next;
delete temporaryNode;
}
2. Deleting the last node (tail node):
Deleting the linked list’s header node was simple. But when we wanted to delete the linked list’s last node or tail node, we have to transfer the null pointer from the tail node to the previous node of the tail, which has the address of the tail node.
To implement this, we must use two temporary nodes and run through the linked list. When the traversing linked list is over, the one temporary node will point to the current node and another temporary node will point to the previous node. Now both required nodes address the details we have and we can delete the tail node while shifting the null pointer to the previous node.
C++ code to delete the last node from the linked list:
{
node *currentNode=new node;
node *previousNode=new node;
currentNode=headNode;
while(currentNode->next!=NULL)
{
previousNode=currentNode;
current=currentNode->next;
}
tail=previousNode;
previousNode->next=NULL;
delete currentNode;
}
3. Deleting the node at specific position:
To delete a node from anywhere in the linked list, we must enter the particular position of the node that we want to delete. To define the specific position node, we use two temporary nodes, like we did while deleting the tail node. We traverse the whole linked list till we do not get the specific position node that we want to delete, and after we get that node, the other temporary node will hold the previous node address of the current node. Now, as we have both node details, we can easily shift the address from the deleting node to the previous address node, which will now point to the next node, just like in the previous deleted method of the last node.
C++ code to delete the nth node from the linked list:
node *currentNode=new node;
node *previousNode=new node;
currentNode=headNode;
for(int count=1;i<positionNumber;count++) {
previousNode=currentNode;
currentNode=currentNode->next;
}
previousNode->next=currentNode->next;
}
C++ program to delete a nth node from the linked list
using namespace std;
class linkedListNode {
public:
int info;
linkedListNode *pointer;
};
int lengthCalculate(linkedListNode* node){
int count = 0;
while(node!=NULL){
node = node->pointer;
count++;
}
return count;
}
void insert(linkedListNode** headNode, int info){
linkedListNode* newNode = new linkedListNode();
newNode->info = info;
newNode->pointer = *headNode;
*headNode = newNode;
}
void deleteNodeMethod(int count, linkedListNode** headNode){
linkedListNode* temporaryNode = *headNode;
linkedListNode* previousNode;
int length = lengthCalculate(*headNode);
if(count < 1 || count > length){
cout << "Deletion of linked list node is not valid" << endl;
return;
}
// this fucntion will delete the first node of the linked list
if(count == 1){
*headNode = (*headNode)->pointer;
cout << temporaryNode->info << " deleted the linked first node" << endl;
delete(temporaryNode);
return;
}
// this while loop will stop when it is reached at the
// end of the linked list
while (--count) {
previousNode = temporaryNode;
temporaryNode = temporaryNode->pointer;
}
// this line will update the previousNode pointer
// with the nth linked list node pointer
previousNode->pointer = temporaryNode->pointer;
// this code will delete the nth node from the linked list
cout << temporaryNode->info << " deleted" << endl;;
delete(temporaryNode);
}
void displayLinkedList(linkedListNode* item){
cout << "\nDisplaying LinkedList => : ";
// This condition will stop when linkedlist reached at the end
while(item!=NULL){
cout << item->info << " ";
item = item->pointer;
}
cout << endl;
}
int main(){
linkedListNode* headNode = NULL;
insert(&headNode, 29);
insert(&headNode, 34);
insert(&headNode, 23);
insert(&headNode, 27);
insert(&headNode, 31);
insert(&headNode, 50);
displayLinkedList(headNode);
cout << "\n Deleting node number 3 = ";
deleteNodeMethod(3, &headNode);
cout << "\n After delete node number 3, linked list will be =";
displayLinkedList(headNode);
cout << "\n Deleting node number 5 = ";
deleteNodeMethod(5, &headNode);
cout << "\n After delete node number 5, linked list will be =";
displayLinkedList(headNode);
return 0;
}
Output:
Deleting node number 3 = 27 deleted
After delete node number 3, linked list will be =
Displaying LinkedList => : 50 31 23 34 29
Deleting node number 5 = 29 deleted
After delete node number 5, linked list will be =
Displaying LinkedList => : 50 31 23 34
Conclusion:
In this blog, we have studied different ways to delete the linked list concepts and how we can code in a C++ program too. Finally, we studied the main concepts of deleting the node from a particular position. Linked list concepts are always important because this is the way to play with the memory of the operating system and has lots of benefits as compared to the array.
