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
//
// 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.