CODEWITHSUNDEEP
c
e t
e t

Reputation: 253

When to use free in linked list delete node code?

#include <stdio.h>
#include <stdlib.h>

struct item {
    int key;
    int data;
    struct item *next;
};

struct item *head = NULL;


void delete(int key)
{
    if(head == NULL) {
        ;
    } else if(head->key == key) {
        head = head->next;
    } else {
        struct item *curr = head;
        struct item *prev = NULL;
        int found = 0;
        while(curr != NULL) {
            if(curr->key == key) {
                found = 1;
                break;
            } else if(curr->key > key) {
                break;
            }
            prev = curr;
            curr = curr->next;
        }
        if(found) {
            prev->next = curr->next;
        }
    }

}

the keys are sorted. delete takes in a key then deletes it. It works but I don't understand when to use free.

We have to free() the struct item we're unlinking from the list

Upvotes: 2

Views: 121

Answers (3)

Stephen Docy
Stephen Docy

Reputation: 4788

You should free() memory assigned to a pointer whenever you are no longer going to be accessing that memory. But you have to make sure you actually do not need it. For example, in your code:

    if(found) {
        free(curr); // Here
        prev->next = curr->next;
    }

Might seem like it would work, because you have found the node to delete, but in fact, you still need access to data pointered to by curr, in order to update the value of prev->next. So instead you should free it here :

    if(found) {
        prev->next = curr->next;
        free(curr); // Here
    }

because at that point, you truly no longer need to access the contents of curr for anything.

Upvotes: 1

Adriano Martins
Adriano Martins

Reputation: 1808

You must think "malloc" and "free" the same as borrowing something from someone. Whenever you borrow a pen from someone (malloc) you need to give it back later on (free).

In your case, you must free your node after you are sure nothing will access it anymore:

#include <stdio.h>
#include <stdlib.h>

struct item {
    int key;
    int data;
    struct item *next;
};

struct item *head = NULL;


void delete(int key)
{
    if(head == NULL) {
        ;
    } else if(head->key == key) {
        head = head->next;
    } else {
        struct item *curr = head;
        struct item *prev = NULL;
        int found = 0;
        while(curr != NULL) {
            if(curr->key == key) {
                found = 1;
                break;
            } else if(curr->key > key) {
                break;
            }
            prev = curr;
            curr = curr->next;
        }
        if(found) {
            prev->next = curr->next;
            free(curr); // Here
        }
    }
}

It acts exact the same as the borrowing mechanics: you can't use anything after returning it (using free) - otherwise it will crash.

Upvotes: 3

I. Ahmed
I. Ahmed

Reputation: 2534

After updating the pointer to next item, you have to delete current. As the current item will not be used anymore. To avoid the memory leak you need to delete it. 

   if(found) 
   {
            prev->next = curr->next;
            free(curr)
   }

Upvotes: 1

Related Questions