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.

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;

}

[std10093]

You do not want to use delete and free together. Delete is enough.

[coolguy67]

Thank you for the reply! So simply removing free(temp); is my only issue? My logic and syntax is correct otherwise?

[std10093]

Trust me, it's far better you try to find out yourself. Take a piece of paper and a pencil and draw what your function would do at a list. Use a 3 noded list for example. Do not forget to draw your pointers and, if needed, keep track of the values of your variables in a table. Here you do not need to keep track of your values.

Welcome to the forum.

[tabstop]

You should only delete things you got from new; free should only be used with malloc. Since this is C++, I would suspect you are using new and delete.

Before you delete your object though, you need to fix your pointers; otherwise you have a "hole" in your list and no way to bridge the gap. You need to make the element before the to-be-deleted object point at the element after it, and vice versa.