Deleting links in a doubly linked list

I am writing a doubly linked list based code in C. I had wrongly assumed that deleting the head node by doing free(head_node). And I could see the computer slowing down as the run progressed (which apparently is due to memory leak). I searched stackoverflow and other sites and the code I usually came across for deleting a linked list was this :

Node* current = head;
while( current != NULL ) {
Node* next = current->Next;
free( current );
current = next;
}

When I tried this in my code, the program just hangs right there after the free statement without returning to the function that calls this one. Is the above code relevant for a doubly linked list? My lis开发者_StackOverflow社区t member data contains a lot of pointers too. When I do free on one of the links, does it free all data the members point to? Please suggest and clarify with code snippets or references to books. Thank you.

---

When I do free on one of the links, does it free all data the members point to?

No. This is what would happen if you deleted the last reference to an object in a garbage-collected language, but C doesn't work like that. You need to manually free each bit of memory that you've allocated.

That code looks like what you'd usually use for a singly- or doubly-linked list, assuming none of its values were pointers.

My list member data contains a lot of pointers too.

Since they are you need to free each current->value as well (and if they're pointers to pointers...).

---

The code you posted should work for singly or doubly linked lists, but makes some assumptions:

• That there's no cleanup of the node to do before freeing it; this is often an incorrect assumption.
• That the end of the list is marked with a NULL pointer (i.e. the last node's Next member is NULL)

Regarding the first assumption: Since you have dynamically allocated data in your nodes, and presuming you don't have another pointer to it somewhere else that you'll use to clean it up later, you'll need to free that data before you free each node. In C, this is not done for you; the general rule is that if you had to allocate it yourself, you have to free it yourself too. A sensible way to deal with this is to write a function to clean up and free a node, and call that instead of just calling free(); your cleanup function would still free the node, but it would free the node's data first.

Regarding the second assumption: It's a pretty common practice to set the last node's Next pointer to NULL to mark the end since it makes it easy to tell when you've walked all the way through the list. For a doubly linked list, the same goes for the first node's Prev pointer. However, if it's a circular list, the last node just points back to the first node instead -- and that would break the code you posted. In that situation, you'd start with the node head->Next instead of head, and check whether current is not head rather than not NULL. Then deal with head at the end, since you skipped it initially.

And one more thing: Make sure after you're done freeing your list, that you don't leave head pointing to an invalid (already freed) node and then try to access the list again...