Delete a node at a given position in a Linked list C++
Contents
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.
- Find the previous node of the node to be deleted
- Remove the node to be deleted
- Reconnect the link list to change the next of the previous node
- 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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include<iostream> 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<<head->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
