Delete an item from a linked list

Question

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.

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?

• Snowbody: Problem: Your code does not compile. You're missing the definition of linked (which I suspect ought to be called node istead)

Answer 1

Apart from the less-than-ideal variable and type names already mentioned you are doubling up on code just to check 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 tmp points to the node which needs to be removed
  • If we have a valid prev then rewire by skipping tmp
  • If we don't have a valid prev then apparently head needs to be moved
  • Now the current node is unlinked and we can delete it
  • We can also return val instead 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).

Answer 2

My concerns are with the type name linked and the variable name listToDel. linked is really a node, not a handle to a linked list. Similarly, listToDel is the node that's going to be deleted, not a list that's going to be deleted.

Also, tmp is a very poor variable name; it gives no indication about what it's used for.

You also might be able to save some indirection by changing from using tmp to using curNode and nextNode.

• Anton.P: Thank you, I agree and will keep that in mind next time.