Home > Enterprise >  Deleting node that doesn't exist in linked list causes segmentation fault
Deleting node that doesn't exist in linked list causes segmentation fault

Time:09-21

So I am new to data structures and I am trying out linked lists. I have made a class Node with an int key, int del and Node* next. When I try to delete nodes by giving delete function (Del) a key, it works perfectly for head node or any node existing in the list but when I give a key that doesn't exist in the list it returns with a segmentation fault.

 void Node::Del(int k) // here k is the key given to search
  {
    Node *curr = head; // ptr that traverses the list
    Node *temp = NULL; // the pointer trails behind curr to store value of node one position behind curr

    while (curr->key != k && curr != NULL)
    {
        temp = curr;
        curr = curr->next;
    }

    if (curr == NULL) // if key not found (not working properly)
    {
        return;
    }

    else if (curr == head) // if head contains the key
    {
        head = curr->next;
        delete curr;
        return;
    }

    else if (curr->key == k) // if key exists in the node
    {
        temp->next = curr->next;
        delete curr;
    }
}

int main()
{
    Node n1;
    n1.Insert(1, 1);
    n1.Insert(2, 2);
    n1.Insert(3, 3);
    n1.Insert(4, 4);
    n1.Insert(5, 5);

    n1.Del(7);
    n1.print();
}

Output:

1 1
2 2
3 3
4 4
5 5

zsh: segmentation fault 

I have a condition after traversing that if( curr == NULL ){ return;} meaning it searched till the end and didn't find the key and exit the loop (as per my understanding) , but instead it It returns segmentation fault.

CodePudding user response:

in this line (curr->key != k && curr != NULL) you should check if curr is null first and before accessing curr to check it's key value, so it should be (curr != NULL && curr->key != k).

explanation : when node isn't exist - i see in your code you assume node key is unique - so you still loop over the linked list till curr become null and the while condition check for the last time, and in this moment curr is null, so it accessing a NULL pointer which rasie your segmantation fault. but in case you check if curr is null firstly the compiler is treating the AND condition as a false before continuing to check the later statments and you go safe.

CodePudding user response:

This line is problematic:

while (curr->key != k && curr != NULL)

The second condition, meaning curr != NULL, is irrelevant. It should be reversed:

while (curr != NULL && curr->key != k)

This way, if curr is NULL, the second condition won't be evaluated (it is called short-circuit evaluation).

  • Related