CODEWITHSUNDEEP
c++memory-managementfreedoubly-linked-list
pZCZ
pZCZ

Reputation: 183

can't free node in double linked list in C++

i try to write function for deleting node in double linked list. But i stack on first condition where nodeToDelete is also head. when i use that code free(nodeToDelete) dont free nodeToDeleteBut nodeToDelete->nextNode;

any help?

edited: with delete also dont work see screenshot -> https://s22.postimg.org/dff43kn9d/slide.jpg

edit 

void deleteNode(node *&head, int value)

fix my code THANK YOU.

void deleteNode(node *head, int value)
{
    node* nodeToDelete = head;

    while(nodeToDelete != NULL)
    {
        if(nodeToDelete->value == value)
        {
            if(nodeToDelete == head)
            {
                head = nodeToDelete->nextNode;
                head->previousNode = NULL;
                delete nodeToDelete;
                return;
            }

        }

        nodeToDelete = nodeToDelete->nextNode;
     }
}

Upvotes: 0

Views: 500

Answers (2)

Dart Feld
Dart Feld

Reputation: 213

You have a wrong order of steps. I drew a quick sketch with nodes and pointers and here's what I found:

First you start with two pointers: head and nodeToDelete which both point on the node you want to delete. Then you point head to the next node and nullify its pointer to preceeding node and proceed to delete the nodeToDelete. So far no problem.

but then this line: nodeToDelete = nodeToDelete->nextNode; is problematic.

Because that nodeToDelete has been freed you cannot use it anymore and the logic itself doesn't work.

I think the logic to follow is :

  1. Point head to the next node.

  2. Make head->previous point to nodeToDelete->previous

  3. Make nodeToDelete->next point to head

  4. Delete nodeToDelete

This way you will have you previous point to next, your next pointing to previous and the one in between deleted.

Something like: 

head = nodeToDelete->next;
head->previous = nodeToDelete->previous;
nodeToDelete->next = head;
delete(nodeToDelete);

while(nodeToDelete != NULL) is not necessary, you can check with an if if you want, but looping this ain't a good idea.

Here's a glorious drawing I did, maybee it will help a bit. Sorry I'm really bad...

enter image description here

Upvotes: 2

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

If head->value matches, you change head inside this function, but that will not change head elsewhere. The caller now has an invalid pointer to a deleted node, and no way to find the actual nodes. It is probably this invalid pointer which is leading to a later call failing.

Also, if head->value does not match, then you search the list, but refuse to do anything with it later because it isn't head. There is no else clause.

Upvotes: 1

Related Questions