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

Question

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

You really should be using `new` and `delete` in C++ if you have to do manual memory allocation. `malloc` and `free` do not work with non-standard layout class types in C++. — NathanOliver, Nov 18 '16 at 13:31
Please learn how to use a debugger, and how to step through your code line by line. — Some programmer dude, Nov 18 '16 at 13:31
Oh MAN !! Thank You !!! I use new for memory allocation. Should use delete insted of free. — pZCZ, Nov 18 '16 at 13:34
Draw what you're trying to do and check if your logic works. If it really does, debug the program line by line. — Dart Feld, Nov 18 '16 at 13:34
It could be the problem since the behavior of using free() with new can be unexpected. Please see: [Post](http://stackoverflow.com/questions/4061514/c-object-created-with-new-destroyed-with-free-how-bad-is-this) — Dart Feld, Nov 18 '16 at 13:37
@NathanOliver nope, when using delete nodeToDelete its deleting nodeToDelete->nextNode [link to screenshot](https://s22.postimg.org/dff43kn9d/slide.jpg) — pZCZ, Nov 18 '16 at 14:01

Dart Feld · Answer 1 · 2016-11-18T14:37:23.820

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 :

Point head to the next node.
Make head->previous point to nodeToDelete->previous
Make nodeToDelete->next point to head
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...

score 1 · Answer 2 · answered Nov 18 '16 at 14:19

1

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.

answered Nov 18 '16 at 14:19

Kenny Ostrom

5,639
2
21
30

Thank you for your comment. i fix my code. I schould pass head by refference just add & to function and its working. – pZCZ Nov 18 '16 at 15:06

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

2 Answers2