2

Past few days I'm working on my c\c++ skills. I was going through my Data structure book and then I thought why not implement doubly linked list program. I wrote the program; surprisingly it work fine too, but , I'm not sure whether I've written it correctly. I'm not able to figure it out how to free the memory I've allocated. Please help me with this guys.

Also if any of you can explain me this "while(linkNode!=0)", i'll be really thankfull.

#include<stdio.h> #include<malloc.h> struct node { int x; struct node * next; struct node * prev; }; struct head { unsigned int count; struct node * hd; struct node * tl; }; void main() { int i =0; struct node * linkNode; struct head *hdd; hdd = (head *)malloc(sizeof(head)); linkNode = (node *) malloc(sizeof(node)); hdd->count = 1; hdd->hd = linkNode; linkNode->prev = 0; linkNode->next = 0; linkNode->x = 0; for(;i<10;i++) { linkNode->next = (node *) malloc(sizeof(node)); linkNode->next->prev = linkNode; linkNode = linkNode->next; linkNode->next = 0; linkNode->x = i; hdd->count+=1; hdd->tl = linkNode; } linkNode = hdd->hd; printf("priniting in next direction\n"); while(linkNode!=0) { printf("%d\n",linkNode->x); linkNode = linkNode->next; } linkNode = hdd->tl; printf("priniting in prev direction\n"); while(linkNode!=0) { printf("%d\n",linkNode->x); linkNode = linkNode->prev; } linkNode = hdd->hd; while(linkNode!=0) { free(linkNode->prev); linkNode = linkNode->next; } free(hdd); }
Improve this question

2 Answers 2

Reset to default
3

Your linked list looks something like this:

+------+----+----+ | Head | hd | tl | ---------->-------- +------+----+----+ \ | ---->------ | NULL | / \ | | +------+-----+------+------+ +------+-----+------+------+ | Node | x=0 | next | prev | | Node | x=1 | next | prev | +------+-----+------+------+ +------+-----+------+------+ | | | \ NULL / -----------------------<----------------------

(I've simplified it to two nodes).

Now, we can just write out what this code does:

linkNode = hdd->hd; while(linkNode!=0) { free(linkNode->prev); linkNode = linkNode->next; }
  1. linkNode = hdd->hd leaves linkNode pointed at the first node
  2. (linkNode!=0) is true (the first node is not NULL), so we enter the while loop
  3. free(linkNode->prev) calls free(NULL) since hdd->hd->prev == NULL (you set the first node up like this explicitly). This is fine, but does nothing.
  4. linkNode = linkNode->next leaves linkNode pointed at the last node
  5. linkNode!=0 is still true (the last node is also not NULL), so we go round the loop again
  6. free(linkNode->prev) frees the previous node (which is the first one)
  7. linkNode = linkNode->next leaves linkNode == NULL
  8. linkNode!=0 is false now, so the loop terminates.

So, we free'd all but the last node. No node's prev member points to that node, so calling free(linkNode->prev) can never free it. You could, however, free it via hdd->tl.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

tediously, but sometimes pictures are just clearer (even ASCII art)
in a notepad or some tool?
1

You are already freeing the memory allocated to your nodes of your linked list in the reverse order from the tail of the list. This line is doing this.

free(linkNode->prev);

There is a memory leak in your program . Your last node in the list is not freed.

Just include 

free(linkNode);

before freeing hdd .

Explanation for: 

while(linkNode!=0)

This is to make sure that you are dereferencing a NULL pointer. Since dereferncing a NULL pointer could cause undefined behaviours.

These are the dereference operations

linkNode->x linkNode->prev
Improve this answer

4 Comments

thanks Sibrajas for your quick response. Can you tell me how actually compiler will convert this statement? I asked this because i'm using same statement for reverse traversal and normal traversal. Also I just wanted to clarify is my program is releasing all the memory it allocated or is there any memory leak?
You use l = l->next for forward traversal, and l = l->prev for reverse traversal. So, you're not using the same for both. And there is, in fact, a leak - you leak the last node.
@user1289810 This allocation and freeing has nothing to do with the compilation. All these are during runtime. Ofcourse malloc allocates memory in the heap or is useful for dynamic memory allocation. . You are freeing the memory here in the forward order. Yes . I see a memory leak here. for the last node of the list. I ll edit my answer on that.
thank you guys for clarifying it. so if after while loop i say free(linkNode) or free(hd->tl) it does free all the memory i've created, right. Once again thank you @Useless and Sibrajas

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.