You are given a pointer to a node of a linked list which is to be deleted. You neither have a head pointer nor the pointer to the previous node.
As we have seen in this post, deleting a node from a linked list requires a pointer to the previous node.
Pseudocode for deleting a node using pointer to the previous node
List-Delete (L, prev) 1. x = next[prev] 2. if x != NULL 3. next[prev] = next[x] 4. Delete(x) (to prevent memory leak) 5. return head[L]
Pseudocode for deleting a node without having a pointer to the previous node
List-Delete (L, x) 1. if x == NULL 2. return 3. if next[x] == NULL 4. cout<<"Last node can't be freed without head node" 5. return 6. temp = next[x] 7. info[x] = info[temp] 8. next[x] = next[temp] 9. Delete(temp) (to prevent memory leak)
Code Implementation
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 | //// main.cpp// Delete from Linked List//// Created by Himanshu on 15/09/21.//#include <iostream>using namespace std;struct node { int info = 0; struct node *next;};typedef struct node Node;node* newNode(int data){ node* Node = new node(); Node->info = data; Node->next = NULL; return(Node);}void printLinkedList (Node* head) { Node *x = head; while (x != NULL) { cout<<(x->info)<<" "; x = x->next; } cout<<endl;}Node* insertNode (Node *head, Node* x) { x->next = head; head = x; return head;}void deleteNode (Node* x) { if (x == NULL) { return; } else if (x->next == NULL) { cout<<"Last node can't be deleted without head pointer"<<endl; return; } Node* temp = x->next; x->info = temp->info; x->next = temp->next; delete (temp);}int main(int argc, const char * argv[]) { Node *head = newNode(7); head = insertNode (head, newNode(6)); head = insertNode (head, newNode(5)); head = insertNode (head, newNode(4)); head = insertNode (head, newNode(3)); head = insertNode (head, newNode(2)); head = insertNode (head, newNode(1)); cout<<"Linked List:"<<endl; printLinkedList(head); cout<<"Deleting Node 1"<<endl; deleteNode(head); cout<<"Linked List:"<<endl; printLinkedList(head); cout<<"Deleting Node 4"<<endl; deleteNode(head->next->next); cout<<"Linked List:"<<endl; printLinkedList(head); cout<<"Deleting Node 7"<<endl; deleteNode(head->next->next->next->next); cout<<"Linked List:"<<endl; printLinkedList(head); return 0;} |
Output
Linked List: 1 2 3 4 5 6 7 Deleting Node 1 Linked List: 2 3 4 5 6 7 Deleting Node 4 Linked List: 2 3 5 6 7 Deleting Node 7 Last node can't be deleted without head pointer Linked List: 2 3 5 6 7
Here’s a working example: Delete a node from a Linked list
Application
- Deleting a node without head pointer is useful in LRU cache implementation (more of this here) if you’re using singly linked-list instead of doubly linked-list. Because you’re required to delete a node from the cache with pointer to the given node.