how to free memory for doubly linked list program in c

Question

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


}

Answer 1

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.

Answer 2

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