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;
   

• cslrnr: 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; } // should we need to check for null for the psList ? in the beginning ?
• R Sahu: Not all all. If psList is NULL, it is empty list. The new list will contain only one item. If it is not NULL, then the new list will contain one more item.

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.

• cslrnr: I have found this bug while debugging the code , i have written and posted the code before trial run ...the head node had junk data because of this. thanks for pointing this out.

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.

• cslrnr: I planned to modify a global varilable head. Test cases written to make sure nodes added fine. Well what might be correct fucntion name you could provide instead of addNodeToHead ?
• John Hammond: If you only intend to provide one function, addNode is sufficient. If you intend to provide different methods with different implementations, I would use the naming system from known other APIs like C# - so addNodeBefore, addNodeAfter, addNodeFirst, addNodeLast, .... So it would be addNodeBefore() for your function, as it adds a node before the parameter node, which can be the head but doesn't have to be.

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;
} 

• cslrnr: comments are welcome for the last edit