C linked list creation from input file with output

Question

Hello I am creating a linked list in C to print the unique tokens given from a text file called dict.txt I am new to C and unsure how to properly read each word from the file, store it into a Node and then print the resulting linked list. Below are my following methods, I have omitted my contains method or its implementation into my add method. I am not concerned with that part yet, only trying to print every word from the given text file.

struct Node{

        char *data;
        struct Node *next;
}

typedef struct Node *node;

Node createNode(){
        Node new;
        new = (Node)malloc(sizeof(struct Node));
        *new.next = NULL;
        return new;
}

void add(Node head, char data){     
        Node temp,p;
        temp = createNode();
        *temp.data = data;
        if(head == NULL) head == temp;
        else{
        p = head;
        while(*p.next != NULL) {
        //TODO contains method to catch duplicates
        p = *p.next;
        }
        *p.next = temp;
        }
        return head;
        }
int main(){
        File *filep;
        filep = fopen("dict.txt", "r");
        Node head = NULL;

        while(fscanf(filep, "%s", word) != EOF){
        int i = 0;
        if (i == 0) Node parent = add(head, word); //add the first word
        else{
        //how should I add the other nodes?
        }
        i++
}

I am struggling to add a Node given the previous node in the while loop. Any suggestions? is my implementation incorrect? I am willing to change my methods around if it better suits the linked list data structure. thanks

Answer 1

First, let's start with basics, you have to read your word into a valid buffer, so declare a buffer large enough to hold your words (the longest word in the Unabridged Dictionary (non-medical) is 29-characters). Don't use magic-numbers, so declare a constant of sufficient size to create the buffer with automatic storage (don't skimp! on buffer size), e.g.

#define MAXC 1024u  /* if you need a constant, define one (or more) */
...
int main (int argc, char **argv) {

    char word[MAXC];        /* buffer to hold each word */

Notice use of the form of main() providing arguments to your program. Use them! Do not hardcode filenames -- that is what the arguments are for. Just pass the filename as the first argument to your program and validate that you have at least 2 arguments (the 1st argument is always the program name), e.g.

    if (argc < 2) { /* check that at least 2 arguments available */
        fprintf (stderr, "error: insufficient arguments.\n"
                "usage: %s filename\n", argv[0]);
        return 1;
    }

    filep = fopen (argv[1], "r");   /* open file given as 1st argument */

Now validate that the file is open for reading:

    if (!filep) {                   /* validate file is open for reading */
        perror ("fopen-filep");
        return 1;
    }

Now you can look at how to handle your list additions. First, you are free to write a create_node() function which can be helpful with complex struct initializations, but for a single character string data, there really is no need. Just allocate a new node every time you call addnode() and then it is simply a matter of checking whether it is the first-node added (simply assign the node address as your list address), otherwise, iterate to the end of your list and add the node there for an in-order insertion.

(note: you can simply use forward-chaining and eliminate the need to find the list end -- but you will end up with your list in reverse order -- unless you also keep a pointer to the end of your list -- that is a topic left to you for research)

Before looking at your addnode() note, if you are allocating for the first node within addnode() you must pass the address of your list pointer to addnode() since the address of the list will be set to the first node. You can alternatively return a pointer to the node inserted (which you also use as an indication of insertion success/failure) and assign the return as your list address for the first node -- up to you. However, when you begin inserting in sort-order or removing nodes from your list you will likewise need to pass the address of your list as a parameter as changing the first node or removing the first-node will cause your list address to change.

With that in mind, your addnode() could be similar to:

node_t *addnode (node_t **head, char *word)
{
    size_t len = strlen (word);             /* length of word */
    node_t  *node = malloc (sizeof *node),  /* allocate new node */
            *iter = *head;      /* temp iterator for in-order insert */

    if (!node) {                    /* validate EVERY allocation */
        perror ("malloc-node");     /* handle error */
        return NULL;
    }

    node->next = NULL;
    node->data = malloc (len + 1);  /* allocate storage for word */

    if (!node->data) {              /* ditto! */
        free (node);                /* free node - word allocation failed */
        perror ("malloc-node->data");
        return NULL;
    }

    memcpy (node->data, word, len + 1); /* copy with nul-character */

    if (!*head)                     /* are we the first node? */
        return (*head = node);      /* just set *head = node */

    while (iter->next)              /* while next is not NULL */
        iter = iter->next;          /* advance iter to next node */

    return (iter->next = node);     /* new node at end */
}

You will create and assign nodes to your list simply by passing the address of the list and the word to add, e.g. in main(),

    while (fscanf (filep, "%s", word) != EOF)   /* read each word */
        addnode (&head, word);                  /* add to list */
    fclose (filep);                 /* close file, done reading */

That is your addnode() to add nodes/words to your list in a nutshell. But every program that creates a list should also have the ability to delete the list and free() all memory allocated to the list. A simple iteration over the node saving a pointer to the node to delete and advancing to the next node before deleting the victim node is key, e.g.

  void free_list (node_t *node)
{
    while (node) {              /* iterate over each node */
        node_t *victim = node;  /* save node to free as victim */
        node = node->next;      /* advance to next before freeing current */
        free (victim->data);    /* free node word */
        free (victim);          /* free node */
    }
}

Putting it altogether, your read of each word in the file and adding each word to a node in your list could be:

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

#define MAXC 1024u  /* if you need a constant, define one (or more) */

typedef struct Node {
    char *data;
    struct Node *next;
} node_t;

node_t *addnode (node_t **head, char *word)
{
    size_t len = strlen (word);             /* length of word */
    node_t  *node = malloc (sizeof *node),  /* allocate new node */
            *iter = *head;      /* temp iterator for in-order insert */

    if (!node) {                    /* validate EVERY allocation */
        perror ("malloc-node");     /* handle error */
        return NULL;
    }

    node->next = NULL;
    node->data = malloc (len + 1);  /* allocate storage for word */

    if (!node->data) {              /* ditto! */
        free (node);                /* free node - word allocation failed */
        perror ("malloc-node->data");
        return NULL;
    }

    memcpy (node->data, word, len + 1); /* copy with nul-character */

    if (!*head)                     /* are we the first node? */
        return (*head = node);      /* just set *head = node */

    while (iter->next)              /* while next is not NULL */
        iter = iter->next;          /* advance iter to next node */

    return (iter->next = node);     /* new node at end */
}

void prn_list (node_t *node)
{
    puts ("\nlinked list:\n");

    while (node) {              /* iterate over each node */
        puts (node->data);      /* outputting node->data */
        node = node->next;      /* advance to next node */
    }
}

void free_list (node_t *node)
{
    while (node) {              /* iterate over each node */
        node_t *victim = node;  /* save node to free as victim */
        node = node->next;      /* advance to next before freeing current */
        free (victim->data);    /* free node word */
        free (victim);          /* free node */
    }
}

int main (int argc, char **argv) {

    char word[MAXC];        /* buffer to hold each word */
    FILE *filep;            /* FILE not File */
    node_t *head = NULL;    /* node to beginning of list */

    if (argc < 2) { /* check that at least 2 arguments available */
        fprintf (stderr, "error: insufficient arguments.\n"
                "usage: %s filename\n", argv[0]);
        return 1;
    }

    filep = fopen (argv[1], "r");   /* open file given as 1st argument */
    if (!filep) {                   /* validate file is open for reading */
        perror ("fopen-filep");
        return 1;
    }

    while (fscanf (filep, "%s", word) != EOF)   /* read each word */
        addnode (&head, word);                  /* add to list */
    fclose (filep);                 /* close file, done reading */

    prn_list (head);    /* print list */
    free_list (head);   /* free all allocated memory */
}

(note: you must validate every allocation, reallocation and input to insure you do not invoke Undefined Behavior in every program you write, not just list programs)

The principals above apply generally to all linked list programs you will write. As mentioned above there are variations in how you can optimize adding nodes with forward-chaining or chaining in order using a tail pointer as well, but the basic passing of the information to add and the allocation of the node and storage for the data will basically work the same regardless.

Example Input File

$ cat ../dat/captnjack.txt
This is a tale
Of Captain Jack Sparrow
A Pirate So Brave
On the Seven Seas.

Example Use/Output

$ ./bin/ll_words ../dat/captnjack.txt

linked list:

This
is
a
tale
Of
Captain
Jack
Sparrow
A
Pirate
So
Brave
On
the
Seven
Seas.

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_words ../dat/captnjack.txt
==16920== Memcheck, a memory error detector
==16920== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==16920== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==16920== Command: ./bin/ll_words ../dat/captnjack.txt
==16920==

linked list:

This
is
a
tale
Of
Captain
Jack
Sparrow
A
Pirate
So
Brave
On
the
Seven
Seas.
==16920==
==16920== HEAP SUMMARY:
==16920==     in use at exit: 0 bytes in 0 blocks
==16920==   total heap usage: 33 allocs, 33 frees, 884 bytes allocated
==16920==
==16920== All heap blocks were freed -- no leaks are possible
==16920==
==16920== For counts of detected and suppressed errors, rerun with: -v
==16920== 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 further questions.

Answer 2

You don't seem to use pointer consistently. You might need to refresh on the different between pointer and value. This you should workout on your own to make sure that you understand the concept.

For this particular problem:

1) First change createNode to create a new node and initialize data:

Node * createNode(char *data) {
    Node *node = (Node *)malloc(sizeof(struct Node));
    node->next = NULL;
    node->data = (char *)malloc(strlen(data));
    strcpy(node->data, data);
    return node;
}

(Notice that we return pointer. Also, we allocate space to store data.)

2) Also, change add to accept pointers and return pointer

Node * add(Node *head, char *data) {
    Node *p = NULL;
    Node *temp = createNode(data);
    if (head == NULL) {
        head = temp;
    }
    else {
        p = head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = temp;
    }
    return head;
}

Note that the above function can handle empty list and none empty list, so your main doesn't have to.

3) In your main:

int main() {
    File *filep = fopen("dict.txt", "r");
    Node head = NULL;
    char word[256];

    while (fscanf(filep, "%s", word) != EOF) {
        head = add(head, word);
    }
    return 0;
}