Linked List Implementation Memory Allocation

Question

I've implemented a linked list using structs and pointers in C as follows:

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

/* these arrays are just used to give the parameters to 'insert',
 * to create the 'people' array */

#define HOW_MANY 7
char * names[HOW_MANY] = {"Simon", "Suzie", "Alfred", "Chip", "John", "Tim", "Harriet"};
int ages[HOW_MANY] = {22, 24, 106, 6 ,18, 32, 24};

/* declare your struct for a person here */
struct p {
    char *peopleName;
    int age;
    struct p* next;
} person;


struct p* insert_end (struct p *people,char *name, int age) {
    /* put name and age into nthe enxt free place in the array parameter here */
    /* modify nextfreeplace here */
    struct p *nextPerson;

    nextPerson = (struct p*)malloc(sizeof(struct p));

    if (nextPerson == NULL) {
        printf("Error performing malloc.\n");
        return(NULL);
    } else {
        nextPerson -> peopleName = name;
        nextPerson -> age = age;
        if (people == NULL) {
            nextPerson -> next = people;
            return nextPerson;
        } else {
            struct p* temp = people;
            while ((temp -> next) != NULL) {
                temp = temp -> next;
            }
            temp -> next = nextPerson;
            nextPerson -> next = NULL;
            return people;
        }
    }
}



int main (int argc, char **argv) {
    /* declare the people array here */

    struct p *people = NULL;

    for (int i = 0; i < HOW_MANY; i++) {
        people= insert_end(people, names[i], ages[i]);
    }

    while (people != NULL) {
        printf("Freeing\n");
        free(people);
        people = people -> next;
    }


    return 0;
}

This works fine, but what I don't understand is why it doesn't work when insert_end is declared as follows:

struct p* insert_end (struct p *people,char *name, int age) {
    /* put name and age into nthe enxt free place in the array parameter here */
    /* modify nextfreeplace here */
    struct p *nextPerson;

    nextPerson = (struct p*)malloc(sizeof(struct p));

    if (nextPerson == NULL) {
        printf("Error performing malloc.\n");
        return(NULL);
    } else {
        nextPerson -> peopleName = name;
        nextPerson -> age = age;
        if (people == NULL) {
            nextPerson -> next = people;
            return nextPerson;
        } else {
            while ((people -> next) != NULL) {
                people= people-> next;
            }
            people-> next = nextPerson;
            nextPerson -> next = NULL;
            return people;
        }
    }
}

As you can see, the memory is not being freed correctly when this implementation is used. Could anyone help me in understanding why this does not work?

Answer 1

The function is apparently supposed to return a pointer to the first entry in the list. The second implementation does not, instead returning a pointer to the next-to-last entry in the case where there's already at least one thing on the list.

Answer 2

Not the answer to your question, but even when you use the first version of insert_end which works fine, you have undefined behaviour in this piece of code :

while (people != NULL) {
    printf("Freeing\n");
    free(people);
    people = people -> next;  // << you are using people after it has been freed
}

On your platform the code may seem to work correctly, but this is only by chance.

This works in all cases on all platforms :

while (people != NULL) {
    printf("Freeing\n");

    struct p *temp = people ; 
    people = people -> next;
    free(temp);
}