linked list behavior - help me understand

Question

i am in the process of learning linked lists, and i dont understand the behavior change when freeing a string. Here is the code:

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

struct node {
    char*          data;
    struct node*   next;
    };

void Push(struct node** headRef, char *data)
{
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = data;
    newNode->next = *headRef;  // The '*' to dereferences back to the real head
    *headRef = newNode;        // ditto
}

int main(int argc, const char * argv[])
{

    char* auxStr;
    struct node* list;
    struct node* auxPtr;
    int i=5;


    while (i<9)
    {
        auxStr=malloc(sizeof("String:%d"));
        sprintf(auxStr, "String:%d",i);
        Push(&list, auxStr);
        i++;
    }

    auxPtr=list;

    i=0;
    while (auxPtr)
    {
        printf("Node:%d - Data:%s\n",i++,auxPtr->data);
        auxPtr=auxPtr->next;
    }

    return 0;
}

That results in:

Node:0 - Data:String:8
Node:1 - Data:String:7
Node:2 - Data:String:6
Node:3 - Data:String:5

now, when i add free(auxStr) in the first while:

while (i<9)
{
    auxStr=malloc(sizeof("String:%d"));
    sprintf(auxStr, "String:%d",i);
    Push(&list, auxStr);
    free(auxStr);
    i++;
}

i now get:

Node:0 - Data:String:8
Node:1 - Data:String:8
Node:2 - Data:String:8
Node:3 - Data:String:8

Can someone explain why ? i know it may not be the most efficient code freeing in there multiple times, but i saw this behavio and it is puzzling me. Would appreciate your help to help me understand the concept better.

Thanks

Note that the buffer `malloc(sizeof("String:%d"))` will be too small for `sprintf()` when your integer becomes `>= 100`. — Niklas R, Feb 03 '13 at 09:25

score 2 · Answer 1 · answered Feb 03 '13 at 09:10

2

You are getting undefined behavior.

You are freeing a memory (auxPtr) but you still happen to have a pointer to it - as the data in the relevant node. That is called a dangling reference.

What happens with this data is undefined, and it happens to be reusing the same address for each new allocation (but again, anything can happen).

Thus, when later printing the data - the output is undefined.

answered Feb 03 '13 at 09:10

amit

175,853
27
231
333

if i use an array instead: char auxStr[20]; and get rid of the malloc and free, i still get the same wrong result. Why is it the same situation ? – jelipito Feb 03 '13 at 09:20
@jelipito Not sure I am following, do you mean you will use an array in `main()` and send it to the linked list? The result will then be perfectly defined - but again wrong, the `data` in all nodes will have the value assigned to the last node in this case. You should consider dynamically allocate a string per node, or replace the `char*` in each `node` to a `char[SIZE]` (in the later beware of buffer overflow) – amit Feb 03 '13 at 09:22
yes, ok, got the array one. The other that i don't understand is that going back to the original code posted, why does it work fine ? when i call malloc several times for auxStr does it actually creates different pointers everytime ? – jelipito Feb 03 '13 at 09:27
@jelipito It may reuse already freed memory (which seems to be the case), and since you copied the **address** of the string to `data` - after freeing that address you cannot access the same address again (you can, but that will result in undefined behavior). When you later read the data, you access addresses that were already released, and the result is undefined. In practice, you keep getting the same address, which is a valid behavior for the memory allocator - because you already freed that memory.\ – amit Feb 03 '13 at 10:12
thanks, any links that you recommend for learning dynamic allocation ?. – jelipito Feb 03 '13 at 10:33

score 0 · Answer 2 · answered Feb 03 '13 at 09:10

0

You aren't copying the data string by strncpy - instead you are simply assigning pointer to the same string that you free later

answered Feb 03 '13 at 09:10

kchoi

473
1
4
11

score 0 · Answer 3 · edited May 23 '17 at 10:24

0

As indicated here acessing a poitner after you free it is undefined behavior.

edited May 23 '17 at 10:24

Community

1
1

answered Feb 03 '13 at 09:11

Ivaylo Strandjev

69,226
18
123
176

md5 · Answer 4 · 2013-02-03T09:17:05.203

Each of your data in struct node points on the same address. When freeing auxPtr, you are accessing to a memory location which is not allocated anymore. In C, it leads to an undefined behavior. It could be a better idea to dynamically allocate your data, as follow.

#include <assert.h>
#include <stdlib.h>
#include <string.h>

void Push(struct node **head, const char *data, size_t size)
{
  struct node *elt;

  elt = malloc(sizeof *elt);
  assert(elt != NULL);

  elt->data = malloc(size);
  assert(elt->data != NULL);
  memcpy(elt->data, data, size);

  elt->next = *head;
  *head = elt;
}

Moreover, there is no null pointer in your list. You should allocate list first.

Hm.. It would be interesting as why they point to the same location, which is not covered in your answer. I think because `malloc()` returns the same address which was just freed bofere, again, but that's just a guess. — Niklas R, Feb 03 '13 at 09:30

linked list behavior - help me understand

4 Answers4