How to delete a node from a Linked list without head pointer in C++

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 require 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;
}

Here’s a working example:

https://ideone.com/MtzfHN

Application

  • Deleting a node without head pointer is useful in LRU cache implementation (more of this later) if you’re using singly linked-list instead of doubly linked-list. Because you’re require to delete a node from the cache with pointer to the given node.

Leave a Reply

Your email address will not be published.