CODEWITHSUNDEEP
c++linked-listdynamic-memory-allocation
Sarah Sepanski
Sarah Sepanski

Reputation: 189

removing a value from a linked list/deleting values that were not dynamically allocated

My textbook has the following code for removing an element from a linked list.

void remove(double num)
{
    Node *cur, *prev;
    if(!head){
        return;
    }
    if(head->data == num)
    {
        cur = head;
        head = head->next;
        delete cur;
    }
    else{
        cur = head;
        while(cur!=NULL && cur->data != num)
        {
            prev = cur;
            cur= cur->next;
        }
        if(cur)
        {
            prev->next = cur->next;
            delete cur;
        }
    }
}

I have a few questions about this code. First of all, how is it possible to delete a value that was not dynamically allocated? Why is that necessary? I don't see a new statement anywhere. Second of all, why is this block of code necessary? Why does it need to be inside an if statement?

if(cur)
        {
            prev->next = cur->next;
            delete cur;
        }

Upvotes: 1

Views: 52

Answers (2)

Dev Null
Dev Null

Reputation: 4997

It's not correct to delete a value that wasn't previously allocated with a new. I assume new-allocation is implied by your textbook.

Regarding your second question, after 

while(cur!=NULL && cur->data != num){...}

has finished, either cur == NULL or cur != NULL && cur->data == num. if (cur) is effectively if (cur != NULL) and it implies that cur contains the value you were looking for.

The block itself is needed to remove the found element by changing the next pointer of the previous element to the element, that goes after the one being removed.

Upvotes: 0

Beta
Beta

Reputation: 99144

First, this code assumes that the nodes were dynamically allocated. That's the way linked lists are usually constructed. If your code uses nodes on the stack, then just remove the delete statements. (And give a little thought to how you'll keep track of which nodes are in use.)

Second, that block of code is necessary because it removes the node that is to be removed-- if that node exists. It is in an if block in case the node does not exist. Draw up a simple example on paper, and step through the code to see what happens if you try to remove an element that isn't in the list.

Upvotes: 5

Related Questions