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