Delete nodes in a linked list

Question

I know that plenty of questions have been asked regarding deleting a node from linked list. But my mind got stuck at a point and I am unable to clear my confusion.

I have a linked list with nodes 1,2,2 in it. And I want to delete nodes of 2 from it. My code is deleting only first node of 2 not the second one. In short I want to delete all the nodes that match to the key give by the user. Here is my code:

void LinkedList::Delete(int key)
{
    if(head == 0)
        return;
    if(head->data == key)
    {
        Node *p = head;
        head = head->next;
        delete p;
    }
    else
    {
        Node *prev = 0;
        Node *temp = head;
        while(temp!=0)
        {
            if(temp->data == key)
            {
                Node *q = temp;
                temp = temp->next;
                prev = temp;
                delete q;
            }
            else
            {
                prev = temp;
                temp = temp->next;
            }
        }

    }
}

If I comment out the else portion then it gives me the access violation error at the last line i.e temp=temp->next and I know the issue is that to which node it should point if it is at the last node!

Answer 1

In below piece of code, after deleting, your temp is not pointing to next node. So, once you delete first entry of "2" your loop stops.

 if(temp->data == key)
        {
            prev->next = temp->next;
            temp = 0;
            delete temp;
        }

Try doing below in IF block.

 itemToDelete = temp;
 temp = temp->next;
 delete itemToDelete;

Answer 2

This is pretty typical C++ beginner's mistake, I bet by the time I'm done typing this answer there will be tones of answers showing you how to delete a pointer (tip: first delete, then nullify -- if you need to).

For the sake of completeness, you can avoid having to check prev pointer and simplify the code by using pointer to pointer. See here for details.

void LinkedList::Delete(int key)
{
    for (Node** pp = &head; *pp; pp = &(*pp)->next)
    {
        Node* p = *pp;
        if (p->data == key)
        {
            *pp = p->next;
            delete p;
        }
    }
}

Answer 3

You have a few problems in your code. If first node equal '2' - you delete only first node. And why do you allocate memory for Node *prev? And you have memory leak (see comments).

You can try this code:

void LinkedList::Delete(int key)
{
    if (head == 0)
        return;

    Node* prev = 0;
    Node* cur = head;
    while (cur != 0)
    {
        if (cur->data == key)
        {
            Node* temp = cur;
            if (prev == 0)
                head = cur->next;
            else
                prev->next = cur->next;
            cur = cur->next;
            delete temp;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
}

Answer 4

Your code is not deleting anything because you are not going through the list. You are simply checking that the first element is equal to the key (2), but the list's first element is 1.

You need to loop through the whole list if you wish to delete every node whose key == the function argument key.

node* current_node{ head };
while (current_node)
{
    node* next{ current_node->next };
    if (current_node->key == key)
    {
        // This operation should take care of properly managing pointers
        // in the linked list when a node is erased.
        erase(current_node);
    }
    current_node = next;
}

Answer 5

I have written in Turbo C++ Compiler. It is working very correctly.

//start deleteEnd code
void deleteEnd()
{
    if (first == NULL)
    {
        cout<<"No list Available";
        return;
    }
    next = first;
    while (next->add != NULL)
    {
        cur = next;
        next = next->add;
    }
    cur->add=NULL;
}
//deleteEnd