Creating nodes for linked list in a while loop in C

Question

I am trying to create nodes for a linked list in a while loop. The code works, but it is not very pretty. How would I get the same results the proper way?

root = malloc(sizeof(struct node)); // Allocates memory for first node
pointer = root; // Set pointer to first node
char buf[MAXBUF]; // Buffer for each line

int size = 1; // Counts nodes.

/* Write to list */
while(fgets(buf, MAXBUF, f) != NULL) // Puts each line in a node through buffer
{
    strncpy(pointer->data, buf, MAXBUF); // Puts line in character array in node
    pointer->next = malloc(sizeof(struct node)); // Allocates memory for new node
    size++; // Increments for each node. Root is 1, so first round in loop is 2
    pointer = pointer->next; // Sets pointer to next node
}
size--; // Removes 1 count for last node
free(pointer); // Frees last allocated node
pointer = NULL; 

Answer 1

The technique you're trying to accomplish in building your ordered linked list is called forward-chaining. A pointer-to-pointer makes the task trivial for building a simple linked list while retaining its input order. Error checking memory allocations not-withstanding, it is done something like this:

struct node *root = NULL, **pp = &root;
char buf[MAXBUF] = {0};
size_t size = 0;

while (fgets(buf, MAXBUF, f) != NULL)
{
    *pp = calloc(1, sizeof(**pp));
    strncpy((*pp)->data, buf, MAXBUF-1);
    pp = &(*pp)->next;
    ++size;
}
*pp = NULL; // terminate the last node 

---

How It Works

The parts of this that mandate further elaboration follow this general algorithm:

1. Utilize a pointer-to-pointer to always hold the address of the pointer that will be populated with the address of the next node to add. The initial value of this pointer-to-pointer is the address of the root pointer: &root.
2. Acquire a new node, storing its address in *pp, where pp is the pointer-to-pointer from (1)
3. Once the node is finished being configured, change the address stored in pp to be the address of the next member pointer held within the node just added. This step sets up the target location where the next node will be added if needed.
4. When finished processing input, the last-node-added's next member pointer has its address currently held in pp. If no nodes were added to the list, then pp still holds the address of root. To terminate the list, this pointer must be set to NULL.

So on to the code:

struct node *root = NULL, **pp = &root

The above line declares the root pointer, initialized to NULL (optional, but I hate indeterminate pointers anywhere in-code), and a pointer-to-pointer that holds the address of root. From there...

*pp = malloc(sizeof(**pp));

This allocates a new node, storing its address at whatever pointer is currently being addressed by the pointer-to-pointer pp. On the initial pass that pointer is the root pointer. On subsequent passes it will always hold the address of the `next member within the last-node-added on a prior iteration. But it always holds the address of pointer that is to receive the next new node.

After the current node is finished being configured copy, then this is done:

pp = &(*pp)->next;

This stores the address of the just-added-node's next member in the pointer-to-pointer. When we loop around for the next iteration, this is where we will hang the next new node. Finally, after the loop finishes, this is done:

*pp = NULL; 

This sets the pointer pointed-to by pp to NULL. Now think about what pointer that is:

• If no items were populated in the list, then pp still holds the address of root and this will reestablish root as NULL; exactly what you want if the list is empty.
• If any nodes were read, then pp will hold the address of the last added-node's next pointer, which should set to NULL to terminate the linked list. Again, exactly what this code does.

---

Addendum: Printing the list

Per request, printing the list after this is simply:

struct node *ptr = root;
while (ptr)
{
    printf("data: %s\n", ptr->data);
    ptr = ptr->next;
}

For C99 and later,

for (struct node *ptr = root; ptr; ptr = ptr->next)
    printf("data: %s\n", ptr->data);

Answer 2

Memory management

You have a memory management bug due to pointer aliasing.

root = malloc(sizeof(struct node));
pointer = root;
char buf[MAXBUF];

int size = 1; // Counts nodes.

So far, we have

$$ \newcommand{rptr}[1]{\overset{\mathtt{#1}}{\longrightarrow}} \newcommand{lptr}[1]{\overset{\mathtt{#1}}{\longleftarrow}} \mathtt{root} \rptr{}\ \fbox{struct node} \lptr{} \mathtt{pointer} \\ \mathtt{size} = 1 $$

Suppose that there is no input at all. That means that we'll skip the while loop, and proceed with

size--;
free(pointer);
pointer = NULL;

Then we end up with

$$ \newcommand{rptr}[1]{\overset{\mathtt{#1}}{\longrightarrow}} \mathtt{root} \rptr{}\ \textit{freed memory} \qquad \mathtt{pointer} \rptr{}\ \textit{NULL} \\ \mathrm{size} = 0 $$

One would expect the result to be equivalent to root = NULL. The best remedy is to allocate the node when it is actually needed, as written by @WhozCraig.

Style

Writing every statement twice — once in code, and again in a comment — is tedious. The comments don't provide insight. If anything, they become a maintenance liability.

Rather, you should write your code to be more self-explanatory. For example, naming your pointers head and tail would be a huge hint as to their purpose. In contrast, naming your pointer pointer is redundant and unhelpful.

Answer 3

1. Rather than print to buf and then copy to pointer->data, skip the middle-man

   while(fgets(pointer->data, sizeof pointer->data, f) != NULL) 
   

2. Rather than start count at 1, start at 0 and skip the final decrement.

   int size = 0;
   while (...) {
     ...
     size++;
   }
   // size--;
   

3. Simplify malloc() usage, IMO this style easier to maintain and less error prone.

   // root = malloc(sizeof(struct node));
   // pointer->next = malloc(sizeof(struct node));
   root = malloc(sizeof *root);
   pointer->next = malloc(sizeof *(pointer->next));
   

4. IMO, initializing the complete structure promptly after memory allocation is a good thing. (Also with root)

   pointer->next = malloc(sizeof *(pointer->next));
   pointer = pointer->next;
   pointer->next = NULL;
   pointer->data[0] = '\0';
   pointer->other_fields = 0;
   
   // or
   
   pointer->next = calloc(1, sizeof *(pointer->next));
   

5. Checking if malloc() returned NULL is good also.

6. Like the setting the pointer to NULL after free(). A good compiler will optimize out if it can, but good to scrub pointers when done.

   free(pointer);
   pointer = NULL; 
   

Answer 4

My normal approach would be to encapsulate the linked list and provide functions to create a list, add a node, remove a node, etc. So your example comes down to:

List *list = list_create(...);
if (!list) {
    // handle error and exit
}
char buf[MAXBUF];
while (fgets(buf, sizeof buf, f) != NULL) {
    if (list_add(list, buf) < 0) {
        // handle error and exit
    }
}