Linked List doesn't take in the next element (C language)

Question

I am new to C language and I am working on a Linked List example.

The initialize() function seems to work fine, but after the first call of insert() the program crashes.

I think the problem comes from when a new element is added to the linked list, as if it overflows or it doesn't accept the new first element of the list.

I worked on a similar example with a linked list that has only an int element and it worked fine.

The code is as following :

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

typedef struct Element Element;

struct Element
{
    char f_name[10];
    char l_name[10];
    float score;
    Element* next;
};

typedef struct Liste Liste;

struct Liste
{
    Element* first;
};

Element* read()
{
    Element* element = (Element*) malloc(sizeof(element));
    if(element==NULL)
        exit(EXIT_FAILURE);
    printf("Please provide first name : \n");
    scanf(" %s", element->f_name);
    printf("Please provide last name : \n");
    scanf(" %s", element->l_name);
    printf("Please provide score : \n");
    scanf("%f", &(element->score));
    return element;
}

Liste* initialize()
{
    Liste* liste = (Liste*) malloc(sizeof(liste));
    Element* element = (Element*) malloc(sizeof(element));
    if(liste==NULL || element==NULL)
        exit(EXIT_FAILURE);
    element = read();
    element->next = NULL;
    liste->first = element;
    return liste;
}

void insert(Liste* liste)
{
    Element* nouveau = (Element*) malloc(sizeof(nouveau));
    if(liste==NULL || nouveau==NULL)
        exit(EXIT_FAILURE);
    nouveau = read();
    nouveau->next = liste->first;
    liste->first = nouveau;
}

int main()
{
    Liste* maListe = (Liste*) malloc(sizeof(maListe));
    maListe = initialize();
    insert(maListe);
    insert(maListe);
    insert(maListe);
    return 0;
}

What did I do wrong in this one ? and how should I fix it ?

Thanks.

Answer 1

While you already have an answer for your SegFault, there are additional areas where you can clean and refactor your code to work much more efficiently together. Since you are using a list structure liste to hold the pointer to the beginning the list in first, you may as well add another pointer last to point to the final node in the list and eliminate having to iterate to the last node on each insertion. With a last (or tail) pointer, your new node is always inserted at last->next. For instance you Liste struct could be:

typedef struct Liste Liste;

struct Liste {
    Element *first, *last;
};

Your list functions should do one thing each, meaning initialize() should just allocate for and initialize the Liste node and its pointers. read() should allocate and read and return a valid pointer to a filled node, or NULL on failure. insert() should do just that, take the Liste list addressm and the node from read() and insert it into the list. Putting those functions together you could do:

Element *read()
{
    Element *element = malloc (sizeof(*element));   /* allocate */
    if (element == NULL)                            /* validate */
        return NULL;
    element->next = NULL;                           /* initialize */

    printf ("\nPlease provide first name : ");
    if (scanf ("%9s", element->f_name) != 1)   /* validate EVERY input */
        goto badread;

    printf ("Please provide last name  : ");
    if (scanf ("%9s", element->l_name) != 1)
        goto badread;

    printf ("Please provide score      : ");
    if (scanf ("%f", &element->score) != 1)
        goto badread;

    return element;     /* return allocated and initialized element */

badread:;     /* just a simple goto label for handling read error */

    free (element);     /* free memory of node if error */

    return NULL;
}

(note: the use of goto to send you to a label beyond the normal return where you can free the memory for the node that failed during filling.)

/* initialize the list, don't worry about the elements */
Liste *initialize (void)
{
    Liste *liste = malloc(sizeof *liste);
    if (liste == NULL) {
        perror ("malloc-liste");    /* give some meaningful error */
        exit (EXIT_FAILURE);
    }
    liste->first = liste->last = NULL;

    return liste;
}

void insert (Liste *liste, Element *nouveau)
{
    if (liste == NULL || nouveau == NULL)
        exit (EXIT_FAILURE);

    if (!liste->first)                          /* inserting 1st node */
        liste->first = liste->last = nouveau;
    else {                                      /* inserting all others */
        liste->last->next = nouveau;
        liste->last = nouveau;
    }
}

(note: initialize and insert are straight-forward, the only two classes yo handle is whether you are inserting the 1st node, or all other nodes. Makes it very simple)

Putting it altogether, you can write your full test code as follows adding a function to iterate over the list printing values, and then a similar function to iterate over the list freeing nodes and then finally the list::

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

#define MAXN 10     /* if you need a constant, #define one (or more) */

typedef struct Element Element;

struct Element {
    char f_name[MAXN];
    char l_name[MAXN];
    float score;
    Element* next;
};

typedef struct Liste Liste;

struct Liste {
    Element *first, *last;
};

Element *read()
{
    Element *element = malloc (sizeof(*element));   /* allocate */
    if (element == NULL)                            /* validate */
        return NULL;
    element->next = NULL;                           /* initialize */

    printf ("\nPlease provide first name : ");
    if (scanf ("%9s", element->f_name) != 1)   /* validate EVERY input */
        goto badread;

    printf ("Please provide last name  : ");
    if (scanf ("%9s", element->l_name) != 1)
        goto badread;

    printf ("Please provide score      : ");
    if (scanf ("%f", &element->score) != 1)
        goto badread;

    return element;     /* return allocated and initialized element */

badread:;     /* just a simple goto label for handling read error */

    free (element);     /* free memory of node if error */

    return NULL;
}

/* initialize the list, don't worry about the elements */
Liste *initialize (void)
{
    Liste *liste = malloc(sizeof *liste);
    if (liste == NULL) {
        perror ("malloc-liste");    /* give some meaningful error */
        exit (EXIT_FAILURE);
    }
    liste->first = liste->last = NULL;

    return liste;
}

void insert (Liste *liste, Element *nouveau)
{
    if (liste == NULL || nouveau == NULL)
        exit (EXIT_FAILURE);

    if (!liste->first)                          /* inserting 1st node */
        liste->first = liste->last = nouveau;
    else {                                      /* inserting all others */
        liste->last->next = nouveau;
        liste->last = nouveau;
    }
}

void prnlist (Liste *liste)
{
    Element *iter = liste->first;

    while (iter) {  /* just iterate list outputting values */
        printf ("%-10s %-10s  ->  %.2f\n", 
                iter->f_name, iter->l_name, iter->score);
        iter = iter->next;
    }
}

void freelist (Liste *liste)
{
    Element *iter = liste->first;

    while (iter) {
        Element *victim = iter;
        iter = iter->next;          /* iterate to next node BEFORE */
        free (victim);              /* you free victim */
    }
    free (liste);
}

int main (void) {

    Liste *maListe = initialize();  /* create/initialize list */
    Element *node;

    while ((node = read()))         /* allocate/read */
        insert (maListe, node);     /* insert */

    puts ("\n\nElements in list:\n");   /* output list values */
    prnlist (maListe);

    freelist (maListe);     /* don't forget to free what you allocate */

    return 0;
}

Example Use/Output

$ ./bin/ll_liste

Please provide first name : Donald
Please provide last name  : Duck
Please provide score      : 99.2

Please provide first name : Minnie
Please provide last name  : Mouse
Please provide score      : 99.7

Please provide first name : Pluto
Please provide last name  : Dog
Please provide score      : 83.5

Please provide first name :

Elements in list:

Donald     Duck        ->  99.20
Minnie     Mouse       ->  99.70
Pluto      Dog         ->  83.50

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/ll_liste
==10838== Memcheck, a memory error detector
==10838== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==10838== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==10838== Command: ./bin/ll_liste
==10838==

Please provide first name : Donald
Please provide last name  : Duck
Please provide score      : 99.2

Please provide first name : Minnie
Please provide last name  : Mouse
Please provide score      : 99.6

Please provide first name : Pluto
Please provide last name  : Dog
Please provide score      : 87.2

Please provide first name :

Elements in list:

Donald     Duck        ->  99.20
Minnie     Mouse       ->  99.60
Pluto      Dog         ->  87.20
==10838==
==10838== HEAP SUMMARY:
==10838==     in use at exit: 0 bytes in 0 blocks
==10838==   total heap usage: 5 allocs, 5 frees, 144 bytes allocated
==10838==
==10838== All heap blocks were freed -- no leaks are possible
==10838==
==10838== For counts of detected and suppressed errors, rerun with: -v
==10838== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Look things over and let me know if you have questions.

Answer 2

I think the problem in your case is that you have written sizeof(element) where you need to have sizeof(Element). You have that in two different places.

Note that "element" is a variable of pointer type, so it has the size of a pointer (8 bytes probably) while "Element" is your struct type that has a much larger size. So, when you allocate only sizeof(element) bytes that is too small.

This kind of errors are easily found by running your program through valgrind.