-2

So, I have a struct:

tyepdef struct node {
    struct node *next;
    double value;
} NodeT, *NodeTP;

and I have three functions:

int deleteNode(NodeTP p)
{
    free(p);
    p = NULL;

    return 1;
}

int deleteOne(NodeTP list)
{
    if (list->next != NULL)
        deleteOne(list->next);
    else 
        deleteNode(list);

    return 1;
}

int print(NodeT list)                                                           
{                                                                               
    printf("%lf\n", list.value);                                                

    if (list.next != NULL)                                                      
        print(*list.next);                                                      

    return 1;                                                                   
}

deleteOne will hand the final node in the list to deleteNode so that the memory can be freed. When a node is initialized, no memory is allocated for next, until it is needed. instead, it is initially set to be NULL. This is why I don't free(p->next).

So, if I have a list of nodes (let's say their values are 3.5, 2.5, 1.2, 3.6) the print function will print the following:

3.5
2.5
1.2
3.6

Then, if the final node is deleted, and I print again, the following is printed:

3.5
2.5
1.2
3.6

If I delete another node, I get an error because I'm trying to free memory that has already been freed.

It seems as though print is accessing a memory location still, that has already been freed. However, it seems like it shouldn't be trying to read this if the 'next' node is equal to NULL. I realize this is undefined behaviour, but how can I fix this?

user3280527
  • 11
  • 4
  • I cant see your calling code, but should deleteNode() be accepting a pointer to p? – EyeOfTheHawks May 28 '14 at 19:16
  • 1
    Undefined behavior is undefined behavior. It's not a "guaranteed crash" or "guaranteed garbage values". The solution: if you need to access some memory, then don't free it. – The Paramagnetic Croissant May 28 '14 at 19:17
  • The `p = NULL;` inside your `deleteNode` function has no effect. All you're doing is modifying a *local* copy of the pointer. So when you call `deleteNode(list);` (adding the missing semicolon here), you're not actually changing the value of `list`. The call to `deleteNode` will `free` what is *pointed to* by `list`, but `list` is passed by value to `deleteNode` and therefore remains unchanged. – Mike Holt May 28 '14 at 19:23

2 Answers2

1

When the tail node of a linked list is deleted, it is the programmer's responsibility to set the previous' node's next element to NULL.

When the tail node is free()ed, the memory that the node occupied will continue to hold the values it was assigned (when it was a node) until that memory is used for another purpose. Hence, it is not a good idea to continue to reference that memory after freeing it.

Sometimes, I write my own free() function to ensure that the pointer passed to free is no longer capable of accessing the memory. Something like this:

void myFree(void **ptr)
   {
   free(*ptr);
   *ptr=NULL;
   }

Then, when the tail node is freed, the parent node's next pointer is automatically set to NULL:

void myFreeTailNode(NodeT **head)
   {
   NodeT *parentNode   = NULL;

   if(NULL == head)
      return;

   if(NULL == *head)
      return;

   if(NULL == (*head)->next)
      myFree((void **)head);
   else
      {
      for(parentNode = *head; parentNode->next->next; parentNode=parentNode->next)
          /*Do Nothing */ ;

      MyFree((void **)&parentNode->next);
      }
   }
Mahonri Moriancumer
  • 5,993
  • 2
  • 18
  • 28
0

You should do this if you want NULL assigned outside the function:

int deleteNode(NodeTP * p)
{
    free(*p);
    *p = NULL;

    return 1;
}

And change your calls to deleteNode.

Mabus
  • 1,418
  • 12
  • 20
  • Sadly this doesn't seem to affect how the code performs at all – user3280527 May 28 '14 at 19:27
  • You need to apply the same change to deleteOne if you want list to be modified outside that function. – Mabus May 28 '14 at 19:32
  • Maybe I'm not understanding, but... NodeTP is the same as NodeT *, so shouldn't this change make no difference? Also, if I make this change to deleteOne, won't this break my if statement? Since, I will no longer be able to access list->next? – user3280527 May 28 '14 at 19:36
  • As a rule of thumb, if you want to modify a parameter's value (not the memory that it points to) you must pass a pointer to this parameter instead. You want to modify the parameter 'list' so it doesn't matter that list is already a pointer: you must pass a pointer to it. – Mabus May 28 '14 at 19:44