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!

One thing: if you delete a pointer after setting it to 0 it isn't actually deleted. You have called delete on 0 which does nothing. This will leak memory. — Baldrick, Sep 10 '15 at 20:31
I'll ask the basic question: Did you draw on paper with boxes and lines how the deletion step would conceptually look like? Deleting from a linked list should mimic exactly what you drew on paper (if you did so). Also you're *deleting* nodes -- why are you allocating a new node to do this? — PaulMcKenzie, Sep 10 '15 at 21:04
yes i did so. New node is for holding the node whose value is equal to key. If i don't use new node then how will i proceed my temp to next node! — R32, Sep 10 '15 at 21:12
You don't need a new node. If you're creating nodes just to delete nodes is an indication you're logic is incorrect. Take a chain link -- if you want to break a link in the chain, you don't go and buy a temporary link, do you? Same reasoning here...You take the previous link, hook it to the link that came after the link that is to be deleted. Then you've 1) Linked the previous link to the next link, and 2) You've unhooked the link that you want to delete so that you can call `delete` on it safely. — PaulMcKenzie, Sep 10 '15 at 21:21
And also, your `prev` shouldn't even move if you're deleting a link. It should remain seated until you come across a link that doesn't match the key. Consider `1 -> 2 -> 2 -> 2 -> 3`. You want the `prev` to be stuck on the `1` in the list, while your loop is deleting the `2` entries. What you *should* be doing with `prev` is adjusting its `next` pointer only. — PaulMcKenzie, Sep 10 '15 at 21:30

score 1 · Answer 1 · answered Sep 10 '15 at 20:33

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;

answered Sep 10 '15 at 20:33

Guanxi

3,103
21
38

yes this thing was not getting clear to me as i was confusing with prev and temp. But now it is deleting nothing. And should'nt we update the prev pointer too in the IF block i.e prev->next=temp after updating temp? – R32 Sep 10 '15 at 20:51
yes that will remain as it is, I just concentrated on delete part. – Guanxi Sep 10 '15 at 20:51
i have edited my code according to your ans. Plz have a look on it. It is deleting nothing. – R32 Sep 10 '15 at 20:54
3

@R32 Don't do that, it makes the whole thing a nonsense if you change the question after everybody has answered. – john Sep 10 '15 at 21:30

score 1 · Answer 2 · edited May 23 '17 at 11:51

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;
        }
    }
}

Dolk13 · Answer 3 · 2015-09-21T21:27:12.817

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;
        }
    }
}

this does not seem to link the previous node with the next – sp2danny Sep 21 '15 at 15:55 — sp2danny, Sep 21 '15 at 15:55

bku_drytt · Accepted Answer · 2015-09-10T21:22:25.423

0

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;
}

edited Sep 10 '15 at 21:22

answered Sep 10 '15 at 21:10

bku_drytt

3,169
17
19

but i used the while loop with condtion temp!=0 i.e until you will not left with more nodes keep on looping! – R32 Sep 10 '15 at 21:14
I see no while loop anywhere in your original post. – bku_drytt Sep 10 '15 at 21:20
This is the right idea, but will only work if @R32 has implemented a doubly linked list. I see no signs of this in the question. Erase will need at least one more parameter: A reference to the previous node's `next` pointer. – user4581301 Sep 10 '15 at 21:54
@user458130 You are correct. However, the question was about how to delete all nodes that matched a certain key, which is why I had the comment above the erase line. Assuming that he doesn't have a doubly linked list is the same as assuming he does, I suppose. – bku_drytt Sep 10 '15 at 22:05

score -2 · Answer 5 · edited Sep 21 '15 at 15:32

-2

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

edited Sep 21 '15 at 15:32

Shotgun Ninja

2,540
3
26
32

answered Sep 21 '15 at 14:28

Muhammad Ahmad

1
3

**this does not delete anything**, and please don't advocate two decade old compiler. You can get C++14 compiler [online](http://coliru.stacked-crooked.com/) – sp2danny Sep 21 '15 at 15:48

Delete nodes in a linked list

5 Answers5