How to solve error in code and interpret error message

Question

So I'm working on a project using linked lists. The program basically takes in numbers until -999 is inputted and then does operations on it. The two operations I am having problems with are deleteAll, where all the same values are deleted from the list, and deleteSmallest, where the smallest value in the list is deleted. The code that calls both functions is as follows:

    int num;
    cout << "Enter a number you would like deleted from the whole list: ";
    cin >> num;

    uList.deleteAll(num);
    cout << "New list: " << uList << endl;

    uList.deleteSmallest();
    cout << "After deleting the smallest number, the list now is: " << uList << endl;

The code for deleteAll is as follows:

    template <class Type>
    void UnorderedLinkedList<Type>::deleteAll(const Type& deleteItem)
    {
        NodeType<Type>* curr;
        NodeType<Type>* p = NULL;
        NodeType<Type>* q = NULL;

        curr = first;

        if(first == NULL)
            throw std::runtime_error("Cannot delete from an empty list");
        else
        {
            for(int i = 0; i < count; i++)
            {
                if(curr->info == deleteItem)
                {
                    p = curr;
                    q = p->link;
                    p->link = q->link;
                    delete q;
                }
                curr = curr->link;
            }
        }
        delete p;
        delete curr;
    }

The code for deleteSmallest is as follows:

    template <class Type>
    void UnorderedLinkedList<Type>::deleteSmallest()
    {
        NodeType<Type>* curr;
        NodeType<Type>* p;
        NodeType<Type>* q;
        NodeType<Type>* r;

        curr = first;

        if (first == NULL)
            throw std::runtime_error("Cannot delete from an empty list");
        else
        {
            for(int i = 0; i < count; i++)
            {
                if(curr->link->info < curr->info)
                {
                    int smallest = curr->link->info;
                    p = curr;
                    q = curr->link;
                }
                curr = curr->link;
            }
        }
        r = q->link;
        p->link = q->link;
        delete q;
    }

The error that I get is:

    1 [main] Project 5 4044 cygwin_exception::open_stackdumpfile: Dumping stack trace to Project 5.exe.stackdump

Sorry to post a large question, but can someone explain what the error means in this situation and what I'm doing that is causing this to come up? Thank you!

Answer 1

For deleteAll() you should be doing something like this:

else
{
    for (Node* prev = curr; curr != NULL; prev = curr, curr = curr->link)
    {
        if (curr->info == deleteItem)
        {
            NodeType<Type>* temp = curr;
            curr = curr->link;

            if (prev)
                prev->next = curr;
            delete temp;
        }
    }
}

The way you had it before was not deleting curr at all. You should also remove the delete p and delete curr at the bottom as they are redundant.

And for deleteSmallest(), you need to keep a pointer pointing to the smallest node (and a previous node pointing to the one before it) so when the loop finishes you know what delete:

else
{
    Node* prev = NULL, **smallest;

    for (Node** curr = smallest = head, *back(*head); *curr != NULL; back = *curr, curr = &(*curr)->link)
    {
        if ((*curr)->info < (*smallest)->info)
        {
            prev = back;
            smallest = curr;
        }
    }

    Node* temp = *smallest;
    *smallest = (*smallest)->link;

    if (prev)
        prev->link = *smallest;
    delete temp;
}