Linked list in C, is the list being constructed correctly?

Question

I'm trying to implement a linked list abstraction, however I am running into problems. Once I create the linked list and add elements to it. When I print the list it only prints the first element in it in an infinite loop fashion, meaning that either the first element is linked to itself or the print function is incorrect. However, I can't find the problem, could someone help?

The following is the list abstraction:

typedef struct _friend {
    char *firstname;
    char *lastname;
    char birthdate[9];
} friend;


typedef struct _node {
    friend *value;
    struct _node *next;
} node;

typedef struct _linkedlist {
    node *head;
} linkedlist;

The program must follow this abstraction, as it is part of something bigger. The following are the functions that should print the list and add a node to the beginning of the list:

 /* addHead
  *
  * This function takes two parameters - a linked list and a friend.
  * This creates a node for the linked list and connects the friend to the 
  * node.  Then it adds the node to the head of the linked list.
  */

void addHead(linkedlist *llist, friend *f)
{

    // create a node and put the friend in it
    node *n = (node *)malloc(sizeof(node));
    n->value = f;
    n->next = NULL;

    // if the list is empty
    if (llist == NULL)
    {
        // this link is the entire list
        llist->head = n;
        printf("adding friend to null list\n");

    }
    // if the list is not empty
    else
    {
        // make the new link's next pointer point to
        // the first link in the list
        n->next = llist->head;
        printf("adding %s to head\n", n->value->firstname);

        //  make the head pointer point to the new link
        llist->head = n;


}

}

/*
 * printList
 *
 * This steps down through each of the nodes in a linked list and 
 * prints out the information stored in the friend to which the node points.
 * Instead of automatically printing to the screen, it prints to the 
 * file pointer passed in.  If the programmer wants to print to the screen,
 * he/she will pass in stdout.
 */

void printList(linkedlist *llist,FILE *fp)
{

    node *n;
    friend *f;
    // for each node, print out the friend attached to it

    for(n = llist->head; n != NULL ; n = llist->head->next)
    {
        // assign f to the friend of the right node
        f = n->value; 
        // print the friend out
        fprintf(fp,"%s %s: %s\n",
        f->firstname, f->lastname, f->birthdate);
    }

}

Thank You

Answer 1

The for loop in printList isn't quite right:

for(n = llist->head; n != NULL ; n = llist->head->next)

This should read:

for(n = llist->head; n != NULL ; n = n->next)

Otherwise from the second iteration onwards, n gets set to the same value every single time.

The following isn't related to the problem you're having, but I thought I'd mention it anyway. In the following code:

if (llist == NULL)
{
    // this link is the entire list
    llist->head = n;
    printf("adding friend to null list\n");

}

if llist == NULL, the llist->head = n will segfault.

With the current signature of addHead(), there's not a lot you can do if llist is NULL (other than printing an error message and bailing out).

If instead you meant to check whether llist->head is NULL, you don't need to do that since the else block already handles that correctly.

Answer 2

Try:

void printList(linkedlist *llist,FILE *fp)
{

    node *n;
    friend *f;
    // for each node, print out the friend attached to it

    for(n = llist->head; n != NULL ; n = n->next)
    {
        // assign f to the friend of the right node
        f = n->value; 
        // print the friend out
        fprintf(fp,"%s %s: %s\n",
        f->firstname, f->lastname, f->birthdate);
    }

}

Answer 3

I have done the following to your program:

• slightly modified the friend structure. Declared firstname and lastname as arrays for convenience.
• Wrote a main() which calls other functions
• error checking in addHead()
• added create_friend() function which creates friend struct
• added freeList() to release the memory which was malloc()'ed
• corrected looping error in your print function

So here it goes..

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

typedef struct _friend {
    char firstname[10];
    char lastname[10];
    char birthdate[9];
} friend;


typedef struct _node {
    friend *value;
    struct _node *next;
} node;

typedef struct _linkedlist {
    node *head;
} linkedlist;


void addHead(linkedlist *llist, friend *f)
{
    node *n = NULL;

    if (( n = (node *)malloc(sizeof(node))) == NULL) {
        printf("unable to allocate memory \n");
        exit(1);
    }

    n->value = f;
    n->next = NULL;

    if (llist == NULL) {
        llist->head = n;
        printf("adding friend to null list\n");
    } else {
        n->next = llist->head;
        printf("adding %s to head\n", n->value->firstname);
        llist->head = n;
    }

    return;
}

void printList(linkedlist *llist)
{
    node *n;
    friend *f;

    if (llist->head == NULL) {
        printf("Empty list \n");
        return;
    }

    for(n = llist->head; n != NULL ; n = n->next) {
        f = n->value; 
        printf("%s %s %d \n", f->firstname, f->lastname, f->birthdate);
    }

    return;
}

friend * create_friend(char *fn, char *ln, char *dob)
{
    friend *fp = NULL;

    if ((fp = malloc(sizeof(friend))) == NULL) {
        printf("unable to allocate memory \n");
        exit(1);
    }

    strcpy(fp->firstname, fn);
    strcpy(fp->lastname, ln);
    strcpy(fp->birthdate, dob);

    return fp;
}

void freeList(linkedlist *llist)
{
    node *cur = llist->head;
    node *prev = cur; 
    friend *f;

    while (cur != NULL) {
        prev = cur; 
        cur = cur->next;
        f = prev->value;
        printf("freeing .. %s %s %d \n", f->firstname, f->lastname, f->birthdate);
        free(prev->value);
        free(prev);
    }    

    return;
}

int main(void)
{
    linkedlist ll;
    friend *f;

    ll.head = NULL;

    f = create_friend("firstname1", "lastname1", "12345678");
    addHead(&ll, f);

    f = create_friend("firstname2", "lastname2", "12345678");
    addHead(&ll, f);

    f = create_friend("firstname3", "lastname3", "12345678");
    addHead(&ll, f);

    printList(&ll);

    freeList(&ll);
    ll.head = NULL;

    printList(&ll);

    return 0;
}

Hope this helps!

Answer 4

Should be n = n ->next otherwise you're just getting the next of the head every time.