patterncMinor
Delete an item from a linked list
Viewed 0 times
itemdeletelistfromlinked
Problem
I wrote this code to delete an item from a linked list. I checked it and it works, but I want to know if the logic could be written simpler or clearer.
When checking if a pointer is
typedef struct linked_list{
int value;
struct linked_list * next;
}linked;
int deleteSpecificItem(linked ** head, int val)
{
if(!head || !(*head)) return -1;
linked * tmp = *head;
int ret;
linked * listToDel;
if(tmp->value == val)
{
*head = (*head)->next;
ret = tmp->value;
free(tmp);
return ret;
}
while(tmp->next != NULL)
{
if(tmp->next->value == val)
{
listToDel = tmp->next;
tmp->next = tmp->next->next;
ret = listToDel->value;
free(listToDel);
return ret;
}
tmp = tmp->next;
}
return -1;
}When checking if a pointer is
NULL, I can use either !head or head != NULL. What is preferred in companies?Solution
Apart from the less-than-ideal variable and type names already mentioned you are doubling up on code just to check
The way this works is: First we try to find the node which should be removed and we also keep a pointer to the previous node. Once the loop finishes there are several cases to check:
Regarding
head first and then separately doing the same again for every other node. The only difference is that you need to modify head if the element to be removed is the first one. This can be condensed into a single loop:int deleteSpecificItem(linked** head, int val)
{
if (!head || !(*head)) return -1;
linked* tmp = *head;
linked* prev = NULL;
while (tmp->value != val && tmp->next != NULL)
{
prev = tmp;
temp = temp->next;
}
if (tmp->value == val)
{
if (prev)
{
prev->next = tmp->next;
}
else
{
*head = tmp->next;
}
free(tmp);
return val;
}
return -1;
}The way this works is: First we try to find the node which should be removed and we also keep a pointer to the previous node. Once the loop finishes there are several cases to check:
- If the current value is not equal to the one we are looking then it's not in the list and we can return
- If the current value is equal to the one we are looking for then
tmppoints to the node which needs to be removed
- If we have a valid
prevthen rewire by skippingtmp
- If we don't have a valid
prevthen apparentlyheadneeds to be moved
- Now the current node is unlinked and we can delete it
- We can also return
valinstead of remembering the value of the current node because we know that they are equal.
Regarding
!head vs head == NULL: I tend to prefer !head if it's for simple pointer checks and prev->next == NULL when the expression is more complex. However some companies enforce the style NULL == head because a typo like typing = instead of == will yield in a compile error this way (you can't assign something to a constant) instead of an accidental assignment. I never managed to consistently do it that way (old habits die hard) and to be honest I've never run into a bug due to this (compilers these days spit out warnings for these kind of constructs).Code Snippets
int deleteSpecificItem(linked** head, int val)
{
if (!head || !(*head)) return -1;
linked* tmp = *head;
linked* prev = NULL;
while (tmp->value != val && tmp->next != NULL)
{
prev = tmp;
temp = temp->next;
}
if (tmp->value == val)
{
if (prev)
{
prev->next = tmp->next;
}
else
{
*head = tmp->next;
}
free(tmp);
return val;
}
return -1;
}Context
StackExchange Code Review Q#83659, answer score: 8
Revisions (0)
No revisions yet.