How to make a function in C++ to delete a node from the linked list (node can be any except the first node) which matches the searched key

Question

I have this function named DeleteData which I use to delete any node from my linked list.

void DeleteData(Node *node, int key)
{
   Node temp;
   //If key is in the first node itself
   if (node != NULL && node->read_data() == key)
   {
      temp = *node->next;
      node->next = NULL;
      delete node;
      cout << "New List";
      // It's just a function that reads all data from the linked list given the head reference.
      ListTraverse(&temp);
      return;
   }
   //If key is not in first node
else if (node->read_data() != key)
{
    while (node != NULL && node->read_data() != key)
    {
        // Function to loop thorugh all the nodes
    }
    if (node->read_data() == key)
    {
        //Steps to do, If node is found
    }
}
else
{
    cout<<"Invalid Search key";
}

}

This DeleteData is designed to take two arguments, 1. the reference of 1st node, 2. A key. I need to delete the node which has the matching key as its value. I have successfully made the 1st part i.e., when the key is in the 1st node only, but I am unable to design it so that if the key is not found in the 1st node it should on to search the remaining nodes.

Node is a C++ class having this definition

class Node
{
private:
  int data;

public:
  Node *next;
  void push_data(int x)
  {
      data = x;
  }
  int read_data()
  {
     return data;
  }
};

[Check out the Community addition to this answer](https://stackoverflow.com/a/22122095/4581301). If it doesn't outright solve your problem, ask questions about it. — user4581301, Jan 13 '21 at 18:06
I see one possible problem: `void DeleteData(Node *node, int key)` makes it impossible to remove the first node. You need something like `void DeleteData(Node *&node, int key)` so you can update the caller with the new first node. — user4581301, Jan 13 '21 at 18:19
@JahirulIslamMonir All code not recommended. Ask for a [mre] instead. In addition, all information necessary to understand the question must be in the question. Links rot, get blocked by firewalls and are generally a nuisance. If more code is required to correctly answer the question, and you're probably right that it is in this case, people in the future will not be able to understand the answers if the code is no longer available. — user4581301, Jan 13 '21 at 18:22
tl;dr: Please include a [mcve] of your code in the question ;) — 463035818_is_not_an_ai, Jan 13 '21 at 18:39

score 2 · Answer 1 · answered Jan 13 '21 at 18:58

First, apply the single responsibility principle:

Separate searching for the node to delete, from deleting it.

Separate doing the work, from deciding what to do with the result.

This way, any error has a far harder time hiding in the confusion, and is easily fixed.

Node*& findNode(Node*& root, int key) {
    auto p = &root;
    while (*p && (*p)->data != key)
        p = &(*p)->next;
    return *p;
}
void deleteNode(Node*& node) {
    if (node)
        delete std::exchange(node, node->next);
}
bool deleteNode(Node*& root, int key) {
    auto& node = findNode(root, key);
    if (!node) return false;
    deleteNode(node);
    return true;
}

score 0 · Accepted Answer · answered Jan 13 '21 at 18:43

For starters the parameter that specifies the head node shall have a referenced type.

The function can be declared and defined the following way

bool DeleteData( Node * &head, int key )
{
    Node **current = &head;

    while ( *current && ( *current )->read_data() != key )
    {
        current = &( *current )->next; 
    }

    bool success = *current != nullptr;

    if ( success )
    {
        Node *tmp = *current;
        *current = ( *current )->next;
        delete tmp;
    }

    return success;
}

How to make a function in C++ to delete a node from the linked list (node can be any except the first node) which matches the searched key

2 Answers2