Deletion of target node in doubly linked list in C++
How to delete any target node in doubly linked list in C++?
Doubly Linked List is the successor of the singly linked list linear data structure. Although Doubly Linked List is more useful than singly linked list in various manner, but it has its own drawbacks, one of which is that it requires a lot of data in comparison with singly linked list. In this article let’s see one of the operation that you can perform on Doubly Linked List, i.e; a C++ Program for Deletion of nth node in Doubly Linked List
Steps to delete a target node in doubly linked list in C++
Following steps are involved in deletion any target node from a doubly linked list :-
- Traverse till the target node.
- Assign previous node’s next pointer to the next node of the target node.
- For the next node of the target node, its previous pointer is assigned to the targets node’s previous node’s address.
- Exit
Defining doubly linked list in C++
struct Node { int Data; Struct Node* next; Struct Node* prev; };
Algorithm to delete any target node in doubly linked list in C++
- IF HEAD = NULL
- EXIT
- ELSE SET TEMP = HEAD
- Repeat Next Step while TEMP ->NODE!= POS
- SET TEMP = TEMP -> NEXT
- END Of LOOP
- SET PTR = TEMP -> NEXT
- SET TEMP -> NEXT = PTR -> NEXT
- SET PTR -> NEXT -> PREV = TEMP
- FREE PTR
- EXIT
Program to delete any target node in doubly linked list in C++
#include<iostream> using namespace std; struct node { int num; struct node * preptr; struct node * nextptr; }*start_node, *end_node; void Listcreation(int n); void DeleteFirstnode(); void DeleteLastnode(); void DeleteAnyNode(int pos); void display(int a); int main() { int n,num1,a,insPlc; start_node = NULL; end_node= NULL; cout<<" Enter the number of nodes : "; cin>>n; Listcreation(n); a=1; display(a); cout<<" Enter the position to delete a node : "; cin>>insPlc; if(insPlc<1 || insPlc>n) { cout<<"\n Invalid position. Try again.\n "; } if(insPlc>=1 && insPlc<=n) { DeleteAnyNode(insPlc); a=2; display(a); } return 0; } void Listcreation(int n) { int i, num; struct node *fnNode; if(n >= 1) { start_node = (struct node *)malloc(sizeof(struct node)); if(start_node != NULL) { cout<<" Enter data for node 1: "; // storing data in the first node cin>>num; start_node->num = num; start_node->preptr = NULL; start_node->nextptr = NULL; end_node= start_node; for(i=2; i<=n; i++) { fnNode = (struct node *)malloc(sizeof(struct node)); if(fnNode != NULL) { cout<<" Enter data for node "<>num; fnNode->num = num; fnNode->preptr = end_node; // linking new nodes fnNode->nextptr = NULL; // setting the address of last node to NULL end_node->nextptr = fnNode; // previous node is linking with the new node end_node= fnNode; // assign new node as last node } else { cout<<" Memory can not be allocated."; break; } } } else { cout<<" Memory can not be allocated."; } } } void DeleteAnyNode(int pos) { struct node* curNode; int i; curNode = start_node; for (i = 1; curNode != NULL && i < pos; i++) { curNode = curNode->nextptr; } if (pos == 1) { DeleteFirstnode(); } else if (curNode == end_node) { DeleteLastnode(); } else if (curNode != NULL) { curNode->preptr->nextptr = curNode->nextptr; curNode->nextptr->preptr = curNode->preptr; free(curNode); // Deleting the nth node } else { cout << "The given position is invalid!\n"; } } void DeleteFirstnode()//deleting the first node { struct node * NodeToDel; if(start_node == NULL)//checking if the first node is the last node or not { cout<<" Delete is not possible. No data in the list.\n"; } else { NodeToDel = start_node; start_node = start_node->nextptr; start_node->preptr = NULL; free(NodeToDel); } } void DeleteLastnode()//deleting the last node { struct node * NodeToDel; if(end_node== NULL)//checking whether the list has any nodes or not { cout<<" Delete is not possible. No data in the list.\n"; } else { NodeToDel = end_node; end_node= end_node->preptr; end_node->nextptr = NULL; free(NodeToDel); } } void display(int m) { struct node * tmp; int n = 1; if(start_node == NULL) { cout<<" No data found in the List yet."; } else { tmp = start_node; if (m==1) { cout<<"\n Data entered in the list are :\n"; } else { cout<<"\n After deletion the new list are :\n"; } while(tmp != NULL) { cout<<" node "<< n<<": "<< tmp->num<nextptr; // current pointer moves to the next node } } }
Output: Enter the number of nodes : 5 Enter data for node 1: 11 Enter data for node 2: 22 Enter data for node 3: 33 Enter data for node 4: 44 Enter data for node 5: 55 Data entered in the list are : node 1: 11 node 2: 22 node 3: 33 node 4: 44 node 5: 55 Enter the position to delete a node : 3 After deletion the new list are : node 1: 11 node 2: 22 node 3: 44 node 4: 55
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
Click Here - Doubly Linked List in –
- Insertion in doubly linked list –
- Insertion at beginning in doubly linked list –
- Insertion at end in doubly linked list –
- Insertion at nth node in doubly linked list –
- Deletion in doubly linked list –
- Deletion from beginning in doubly linked list :
- Deletion from nth in doubly linked list :
- Deletion from end in doubly linked list :
- Insertion and Deletion in a doubly linked list :
- Insertion in the middle in a doubly linked list :
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
- Doubly Linked List in – C | C++ | Java
- Insertion in doubly linked list – C | C++ | Java
- Deletion in doubly linked list – C | C++ | Java
- Insertion and Deletion in doubly linked list – C | C++ | Java
- Insertion in the middle in a doubly linked list – C | C++ | Java
Login/Signup to comment