Utility functions for a linked list

Question

I have written code to add a node to the head of the list. Criticisms and feedback are welcome.

typedef struct sList
{
    void *data;
    struct sList *nextNode;
}sList;

sList *addNode2Head(sList *psList,void *data)
{
    if(psList == NULL)
        psList = newNode();
    else
    {
        psList = addHeadNode(psList);
        psList->data = data;
    }
    return psList;
}

sList *newNode(void)
{
    sList *psList =(sList *) malloc(sizeof(sList));
    //sList *psList = malloc(sizeof *sList); //Is it correct way ? if so why ?
    psList->nextNode = NULL;
    return psList;
}

sList *addHeadNode(sList *psList)
{
   sList *psListTemp = newNode();
   psListTemp->nextNode = psList;
   return psListTemp;
   //Another way ,
   //psList = psListTemp; //No return needed
}

Answer 1

1. The name addNode2Head will be better as addNodeToHead. Using the number 2 for the word to is rather poor choice in a function name.

2. The function addNodeToHead can be simplified to:

   sList *addNodeToHead(sList *psList, void *data)
   {
      sList* node = newNode();
      node->data = data;
   
      // It doesn't matter what psList is. The new
      // node is now the head of the list.
      node->nextNode = psList;
   
      return node;
   }
   

3. Given the simplified implementation of addNodeToHead, the function addHeadNode might be unnecessary.

4. Don't explicitly cast the return value of malloc. See Do I cast the result of malloc?

   Instead of

   sList *psList =(sList *) malloc(sizeof(sList));
   

   use

   sList *psList = malloc(sizeof(sList));
   

5. Always check the return value of malloc before proceeding to use it.

   sList *newNode(void)
   {
       sList *psList = malloc(sizeof(sList));
       if ( psList == NULL )
       {
          return NULL;
       }
       psList->nextNode = NULL;
       return psList;
   }
   

6. Make sure that you check the value returned by the above function.

      sList* node = newNode();
      if ( node == NULL )
      {
         // Decide how you want to handle the error.
         // return NULL???
      }
   
      node->data = data;
   

Answer 2

The implementation of addNode2Head has a bug, can you spot it?

sList *addNode2Head(sList *psList,void *data)
{
    if(psList == NULL)
        psList = newNode();
    else
    {
        psList = addHeadNode(psList);
        psList->data = data;
    }
    return psList;
}

If psList is NULL, it doesn't set the data for the head node, so it simply gets lost.

The answer of @RSahu fixes that, but I would go one step further: instead of setting the data after newNode returns, it would make sense to move that responsibility into newNode:

sList *newNode(void *data)
{
    sList *node = malloc(sizeof(sList));
    if ( node == NULL )
    {
       return NULL;
    }
    node->data = data;
    node->nextNode = NULL;
    return node;
}

This way callers cannot forget to set data, and now it's impossible to create a node without specifying data.

Answer 3

Regarding the updated code:

I don't like the use of the term head in the functions. You have this prototype:
sList *addNodeToHead(sList *psList,void *data)
The first question I would have is: What head are you talking about, there is psList and data? Does the function modify a global variable called head? Not even your unit test creates a variable called head as head of the list ;)

Your data is a void pointer and then you use printf("%d");, that's not legal, because the size of a void pointer can be different from the size of an int. It's already strange that you don't store a pointer to an int in data, but the int itself. Is this really what you want? Didn't you want to store the pointer to the int?

I assume you actually wanted:

psList = addNodeToHead(psList, &numbers[9]);

You added the cast likely because the compiler complained. But the problem was not the missing cast, but that you converted an integer to a pointer, instead of an integer pointer to a void pointer, which can be done without cast.

When you store a correct pointer, you can then display it correctly with:

printf("Data = %d \n", *((int *)psList->data));

That's a legal printf call, as now you pass an int, as the %d parameter expects.

Answer 4

Thanks for the answers from r sahu and janos for reviewing the code, as i have refactored the code as per their comments , still both of the answers answers the real question.

Here is the edited / updated code ,

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

/* A linked list node */
typedef struct sList
{
    void *data;
    struct sList *nextNode;
}sList;

//Function prototypes */
sList *newNode(void);
void unitTestLinkedList(void);
void displaySList(sList *psList);
sList *addNodeToHead(sList *psList,void *data);



int main(int argc,char *argv[])
{
    unitTestLinkedList();
    return 0;
}




sList *addNodeToHead(sList *psList,void *data)
{
    sList *psListNew = newNode(data);
    if(psListNew == NULL)
    {
        printf("DEBUG : Node not created succesfully !\n");
        return NULL;
    }
    psListNew->nextNode = psList;
    return psListNew;
}

sList *newNode(void *data)
{
    sList *psList = (sList *) malloc(sizeof(sList));
    if(psList == NULL)
    {
        printf("DEBUG :New Node not created succesfully !\n");
        return NULL;
    }
    psList->data = data;
    psList->nextNode = NULL;
    return psList;
}



void displaySList(sList *psList)
{
    if(psList == NULL)
        printf("DEBUG : List is empty !!!\n");
    else
    {
        while(psList != NULL)
        {
            printf("Data = %d \n", psList->data);
            psList = psList->nextNode;
        }
    }
}

void unitTestLinkedList(void)
{
    sList *psList = NULL;
    int numbers[10] = {1,2,3,4,5,6,7,8,9,10};
    //Test for empty list 
    displaySList(psList);
    psList = addNodeToHead(psList,(int *)numbers[9]);
    psList = addNodeToHead(psList,(int *)numbers[8]);
    psList = addNodeToHead(psList,(int *)numbers[7]);
    psList = addNodeToHead(psList,(int *)numbers[6]);
    psList = addNodeToHead(psList,(int *)numbers[5]);
    //Test in middle
    displaySList(psList);
    psList = addNodeToHead(psList,(int *)numbers[4]);
    psList = addNodeToHead(psList,(int *)numbers[3]);
    psList = addNodeToHead(psList,(int *)numbers[2]);
    psList = addNodeToHead(psList,(int *)numbers[1]);
    psList = addNodeToHead(psList,(int *)numbers[0]);
    //Test at end
    displaySList(psList);
}

To update nodes count or count nodes we can have a separate function to handle that or we can have a list container to update count , head , tail or what ever needed .

    typedef struct slistInfo
{
  sList *psListHead;
  sList *psListTail;
  unsigned int sListNodeCount;
}

We can update the above List every iteration of addNodeToHead
unsigned int sListNodeCount = 0;

we can update the above integer (global) through a separate function call

unsigned int sListCount(sList *psList)
{
   while(psList != NULL)
   {
     ++sListNodeCount ;
     psList = psList->nextNode;  
   }
   return sListNodeCount;
}