HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Delete an item from a linked list

Submitted by: @import:stackexchange-codereview··
0
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.

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

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.