Computer Science Canada

Freeing memory of a linked list
Author:  Raknarg [ Wed Oct 22, 2014 2:57 pm ]
Post subject:  Freeing memory of a linked list
I made a doubly linked list in c, and I'm trying to be good and free all my pointers. However, when I run Dr Memory I run into a lot of errors, memory leaks, etc. so I'm assuming I'm doing something wrong here.

I guess the important things here to look at are the remove and killNode functions. Any ideas? I'm pretty new to C, so any help would be great
Author:  Insectoid [ Wed Oct 22, 2014 3:40 pm ]
Post subject:  RE:Freeing memory of a linked list
code:
void killNode(DNode *nodeToKill) {
    (nodeToKill)->prev->next = (nodeToKill)->next;
    (nodeToKill)->next->prev = (nodeToKill)->prev;
    free(nodeToKill);
    free((nodeToKill)->prev);
    free((nodeToKill)->next);
}


You're trying to access nodeToKill->prev after you've already freed nodeToKill. This might not cause an issue, since the memory most likely hasn't been overwritten so it's not reading bogus data, but it is undefined behaviour.

This is nicely illustrated by trying to kill a list with 1 node. It will try to free itself three times in a row.
Author:  Tony [ Wed Oct 22, 2014 3:47 pm ]
Post subject:  RE:Freeing memory of a linked list
something that's jumping out with questions...
code:

void removeDNode
   ...
   DNode *newNode = newDNode();
   ...

why are you creating a new node, while removing another node?

code:

void killNode
   ...
   free(nodeToKill);
   free((nodeToKill)->prev);
   free((nodeToKill)->next);

are you trying to free both neighbors or a node being killed? What if one of them is NULL? (actually the same question applies to relinking with (nodeToKill)->next->prev -- what if "next" is NULL?).

Either way, after you've freed nodeToKill, you are trying to access it again on those last two lines.
Author:  Raknarg [ Wed Oct 22, 2014 3:52 pm ]
Post subject:  RE:Freeing memory of a linked list
@Insectoid Thanks, I didn't see that.

@Tony the first part is because I copied code from my addNode code, and I must have missed that part when editing.

My thought process for killing the nodes was first freeing the pointers to the neighbors(because I think you need to free all pointers of a struct), and then I would free the pointer to the struct itself. Am I correct witht that logic?

By definition of my code, no neighbor should ever be null because it's circularly linked
Author:  Insectoid [ Wed Oct 22, 2014 4:03 pm ]
Post subject:  RE:Freeing memory of a linked list
You don't need to free the pointersof the struct, you need to free all pointers to the struct. The only time you free the pointers of the struct is if you're doing a recursive delete. With your logic, you just deleted the neighbours without fixing up any of the neighbour's neighbour's pointers, and you'd better hope the node you just deleted wasn't the dummy, or your entire list becomes one giant orphan.
Author:  Raknarg [ Wed Oct 22, 2014 5:04 pm ]
Post subject:  RE:Freeing memory of a linked list
So I just need to delete the nodes?
Author:  Tony [ Wed Oct 22, 2014 5:53 pm ]
Post subject:  Re: RE:Freeing memory of a linked list
Raknarg @ Wed Oct 22, 2014 3:52 pm wrote:
because I think you need to free all pointers of a struct

Just to clarify, you don't need to free pointers, which are just integers storing memory address. You need to free space that was allocated with malloc, and a pointer is used to identify that memory location.

e.g.
code:

void example(){
   int foo = 42;
   int* bar = &foo;
   int* buzz = malloc(sizeof(int));
}

There is no need to free bar -- it will disappear when example function is popped off the stack (exits).

buzz on the other hand, has its memory allocated on the Heap (outside of the function stack), so when the stack exits, the memory allocation survives. If there is nothing else that knows about this memory address (to use and/or free it later), then it's a wasted space (also known as memory leak).
Author:  Raknarg [ Wed Oct 22, 2014 5:55 pm ]
Post subject:  RE:Freeing memory of a linked list
Right, I meant all because I dynamically allocate all of my nodes. Thanks.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy