Linked list - append, insert, print

Question

I am a beginner in C and am learning linked lists. I have made a program to implement a linked list, allowing certain operations on the linked list.

There are 3 functions:

• addnode() adds node to end of list
• printlist() prints the whole linked list
• insertnode() inserts a node after a specified node

addnode():

void addnode(struct node **head)
{
     if (*head == NULL)
     {
        struct node *newNode = (struct node*) malloc(sizeof(struct node));
        *head = newNode;
        printf("enter data: ");

        scanf("%d",&((*head)->data));
        (*head)->node = NULL;
     }
     else
     {
        struct node *newNode = (struct node*) malloc(sizeof(struct node));
        printf("enter data: ");
        scanf("%d", &(newNode->data));
        newNode->node = NULL;

        struct node *temp = *head;
        while (temp->node != NULL)
        {
              temp = temp->node;
        }

        temp->node = newNode;
     }
}

printlist():

void printlist(struct node **head)
{
     struct node *temp = *head;
     while (temp->node != NULL)
     {
           printf("%d--", temp->data);
           temp = temp->node;
     }
     printf("NULL\n");
}

insertnode():

int insertnode(struct node **head)
{
    int i, j = 0;

    printf("enter what node you want to insert node after: ");
    scanf("%d", &i);

    struct node *temp = *head;

    while (temp->node != NULL)
    {
          if (i-1 == j)
          {
             struct node *newNode = (struct node*) malloc(sizeof(struct node));

             printf("enter data: ");
             scanf("%d", &i);

             newNode->data = i;
             newNode->node = temp->node;

             temp->node = newNode;
             break;
          }
          temp = temp->node; j++;
    }
    return 0;
}

How well have I implemented these functions?

Is my code easy to read?

What could I improve?

Does it abide by popular good coding practices?

Here is my main() function and function prototypes:

struct node
{
       int data;
       struct node *node;
};

void addnode(struct node **head);
void printlist(struct node **head);
int insertnode(struct node **head);

int main()
{
    struct node *head = NULL;
    addnode(&head);
    addnode(&head);
    addnode(&head);
    addnode(&head);

    printlist(&head);

    insertnode(&head);
    printlist(&head);


    return 0;
}

Answer 1

We're missing includes of the library headers which provide function prototypes:

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

---

A popular naming convention is to use a distinctive prefix (rather than a suffix) for the function names, so that they appear together in alphabetical lists: node_add(), node_insert(), node_print().

---

We're missing a function to return the memory we're using. If we run under Valgrind, we see that we leak the memory we allocated, so we really need a node_free() function.

---

addnode() performs two functions: reading user input and inserting the node. It would be more useful if we separate the functions:

addnode(struct node **head, int value);

The same is true for insertnode().

---

insertnode() always returns 0. It looks like you were anticipating a different return value when the target node wasn't found, but didn't implement that.

---

printnode() would be better if it weren't restricted to writing only to standard output. Users might want to write to standard error, or a file, a device or a socket.

---

We are not robust when allocating memory:

         struct node *newNode = (struct node*) malloc(sizeof(struct node));
         newNode->data = i;
         newNode->node = temp->node;

malloc() returns a void*, which can be assigned directly to any object-pointer type without needing a cast. A good practice for computing the required size is to measure the size of the pointed-to value, rather than its type:

         struct node *newNode = malloc(sizeof *newNode);

Then we need a test before we dereference the pointer:

         if (!newNode) {
             return NODE_FAILURE;
         }

---

The other area where we need to be more robust is user input. We're ignoring the return value from scanf(), but that means we have no idea whether it succeeded or not. That leads to unpredictable behaviour, as Valgrind reveals:

valgrind --leak-check=full ./265776 <<<''
==2932516== Memcheck, a memory error detector
==2932516== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2932516== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==2932516== Command: ./265776
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DE29F: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091B0: main (265776.c:19)
==2932516== 
==2932516== Use of uninitialised value of size 8
==2932516==    at 0x48C3EFB: _itoa_word (_itoa.c:179)
==2932516==    by 0x48DD8B7: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091B0: main (265776.c:19)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48C3F0C: _itoa_word (_itoa.c:179)
==2932516==    by 0x48DD8B7: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091B0: main (265776.c:19)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DE660: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091B0: main (265776.c:19)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DDA2E: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091B0: main (265776.c:19)
==2932516== 
enter data: enter data: enter data: enter data: 0--0--0--NULL
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x109362: insertnode (265776.c:83)
==2932516==    by 0x1091BC: main (265776.c:21)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DE29F: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091C8: main (265776.c:22)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DE660: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091C8: main (265776.c:22)
==2932516== 
==2932516== Conditional jump or move depends on uninitialised value(s)
==2932516==    at 0x48DDA2E: __vfprintf_internal (vfprintf-internal.c:1687)
==2932516==    by 0x48C9D9A: printf (printf.c:33)
==2932516==    by 0x1092E7: printlist (265776.c:66)
==2932516==    by 0x1091C8: main (265776.c:22)
==2932516== 
enter what node you want to insert node after: 0--0--0--NULL
==2932516== 
==2932516== HEAP SUMMARY:
==2932516==     in use at exit: 64 bytes in 4 blocks
==2932516==   total heap usage: 6 allocs, 2 frees, 5,184 bytes allocated
==2932516== 
==2932516== 64 (16 direct, 48 indirect) bytes in 1 blocks are definitely lost in loss record 4 of 4
==2932516==    at 0x483877F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2932516==    by 0x1091F1: addnode (265776.c:37)
==2932516==    by 0x109180: main (265776.c:14)
==2932516== 
==2932516== LEAK SUMMARY:
==2932516==    definitely lost: 16 bytes in 1 blocks
==2932516==    indirectly lost: 48 bytes in 3 blocks
==2932516==      possibly lost: 0 bytes in 0 blocks
==2932516==    still reachable: 0 bytes in 0 blocks
==2932516==         suppressed: 0 bytes in 0 blocks

---

With some care, we don't need a separate code path for an empty list:

int node_add(struct node **head, int value)
{
    while (*head) {
        head = &(*head)->node;
    }

    struct node *newNode = malloc(sizeof *newNode);
    if (!newNode) {
        return 1;
    }

    newNode->data = value;
    newNode->node = NULL;
    *head = newNode;
    return 0;
}