Writing a Delete algorithm in an ordered linked list

[coolguy67]

I am trying to write a delete algorithm for an ordered linked list. Search and traverse I think I have down but delete is giving me fits. It crashes every time. Any help is greatly appreciated!

I have a private pointer to a ListNode strcuture called head in my TestLL class. The ListNode structure contains int Key, double dataValue, and ListNode *next. The function returns true if the node to delete was found and deleted or false if it was not found.

My code:

bool TestLL::Delete(int Key)
{
ListNode *back = NULL, *temp = head;
//Search for the node to delete
while((temp != NULL) && (key != temp -> key))
//advance the pointers
back = temp;
temp = temp->next;
}
//Check for node to delete not being found
if( temp == NULL)
{
return false;
}
//Check for deleting the head of the list
else if( back == NULL) //I'm very unsure of my else if and else
{
delete temp;
}
else// Remove node other than at the head
{
delete temp;
}

//deallocate memory used by the removed node

free(temp);
return true;

}

[LB]

You cannot mix new/malloc with free/delete. new goes with delete only. Remove line 27.

Also, while you're destructing the element, you're not removing it from the list, so the previous node still points to it.

[Stewbond]

You were missing a { in line 6. Proper indenting would show this.

bool TestLL::Delete(int Key)
{
    ListNode *back = NULL, *temp = head;
    //Search for the node to delete
    while((temp != NULL) && (key != temp -> key))
    {
        //advance the pointers
        back = temp;
        temp = temp->next;
    }
    //Check for node to delete not being found
    if( temp == NULL)
    {
        return false;
    }
    //Check for deleting the head of the list
    else if( back == NULL) //I'm very unsure of my else if and else
    {
        delete temp;
    }
    else// Remove node other than at the head
    {
        delete temp;
    }

    //deallocate memory used by the removed node

    free(temp);
    return true;

}

Is this your problem? I can't imagine that it would have compiled as-is so if it's not a syntax mistake, I'll need to look closer.

[coolguy67]

Thanks for the replies. I'm not sure what command to use to remove/ delete nodes besides delete. Also the deallocating memory syntax bit at the end is confusing me.

[LB]

delete just destructs the node and releases the memory for it, but you still need to change your linked list so it no longer is pointing at the memory of the node you just destructed.

[Stewbond]

Actually, a second look made me think about your else if. There is only one way that back would be NULL. That case is when temp is NULL from the start. If that does happen then deleting temp would result in a problem because there is nothing to delete.

I think you want to do this:

bool TestLL::Delete(int Key)
{
    ListNode *back = NULL, *temp = head;
    //Search for the node to delete
    while((temp != NULL) && (key != temp -> key))
    {
        //advance the pointers
        back = temp;
        temp = temp->next;
    }
    //Check for node to delete not being found
    if( temp == NULL)
    {
        return false;
    }
    //Check for deleting the head of the list
    else if( back == NULL) //I'm very unsure of my else if and else
    {
        return false;
    }
    else// Remove node other than at the head
    {
        delete temp;
    }

    //deallocate memory used by the removed node

    free(temp);
    return true;

}

[LB]

Still need to remove that free(temp);!

[Stewbond]

Right, I hadn't refreshed the page to see your comments in a while. Also, we don't really need put else if after a return statement, so here's something to make the code a little shorter too:

bool TestLL::Delete(int Key)
{
    ListNode *back = NULL, *temp = head;
    //Search for the node to delete
    while((temp != NULL) && (key != temp -> key))
    {
        //advance the pointers
        back = temp;
        temp = temp->next;
    }
    //Check for node to delete not being found
    if( temp == NULL)
        return false;

    //Check for deleting the head of the list
    if( back == NULL) //I'm very unsure of my else if and else
        return false;

    //deallocate memory used by the removed node
    delete temp;
    return true;
}