C implementation of a singly linked list

Question

I've done plenty of corrections of the previous code. Dangling pointers seem a fixed problem (correct me If I'm mistaken). The swap/reverse functions are going to be changed soon due to high time complexity. Also the LinkedList_Find() function is not enough specialized for different types of data, such as Person, because it simply compares void pointers: the intention was to write general purpose code, the choice of making this current linked list of type Person was done to show the adaptability of void* to all types (sorry for my influence of java generics :p). Any suggestions and corrections on design patterns and more efficient code are highly appreciated.

LinkedList.h

#ifndef NYO_LINKED_LIST
#define NYO_LINKED_LIST

#include "stdbool.h"
#include "stdio.h"
#include "stdlib.h"

typedef struct Node
{
    void *data;
    struct Node *next;


} Node;

typedef struct LinkedList {
    Node *head, *tail;
    int length;
} LinkedList;

bool LinkedList_Init(LinkedList*);
bool LinkedList_Add(LinkedList*, Node*);
Node* createNode(void*);
bool LinkedList_PushFront(LinkedList*, Node*);
void* LinkedList_GetDataAt(LinkedList*,int);
Node *getNode(LinkedList*,int);
bool LinkedList_DeleteLast(LinkedList*);
bool LinkedList_Find(LinkedList*,void*);
void LinkedList_Reverse(LinkedList*, void(*)(int*,int*));
void LinkedList_Clear(LinkedList*);
bool LinkedList_InsertAt(LinkedList*,int,void*);
bool LinkedList_DeleteAt(LinkedList*,int);
void LinkedList_Free(LinkedList*);

#endif

LinkedList.c

#include "LinkedList.h"
#define DEBUG
#undef DEBUG          

bool LinkedList_Init(LinkedList *list)
{
    list->head = NULL;
    list->tail = list->head;
    list->length = 0;
    return true;

}

bool LinkedList_Add(LinkedList *list, Node* node)
{
    if(list->head!=NULL)
    {
        list->tail->next = node;
    }
    else
    {
        list->head = node;
    }

    list->tail = node;
    ++list->length;
    return true;
}

Node* createNode(void* data)
{
    Node *tmp = (Node*)malloc(sizeof(Node));
    tmp->data = data;
    tmp->next = NULL;
    return tmp;
}

bool LinkedList_PushFront(LinkedList *list, Node* node)
{
    if(list->head==NULL){

        LinkedList_Add(list, node);

    } else {

        node->next = list->head;
        list->head = node;

        ++list->length;
    }
    return true;
}
void* LinkedList_GetDataAt(LinkedList *list, int index)
{
    Node *tmp = list->head;
    int count = 0;
    if(index >= 0 && index < list->length)
    {
        while(tmp!=NULL)
        {
            if(count == index) return tmp->data;
            ++count;
            tmp = tmp->next;
        }
    }
    return 0;
}

Node *getNode(LinkedList *list, int index)
{

    Node *tmp = list->head;
    int count = 0;
    if(index >= 0 && index < list->length)
    {
        while(tmp!=NULL)
        {
            if(count == index) return tmp;
            ++count;
            tmp = tmp->next;
        }
    }
    return NULL;
}

bool LinkedList_DeleteLast(LinkedList *list)
{

    Node *tmp = list->head;
    int i;
    Node *beforeLast;

    if(list->length>1)
    {
        for (i = 0; i < list->length; ++i)
        {
            if(i == list->length-2)
            {
                beforeLast = tmp;

            }
            tmp = tmp->next;
        }

        free(beforeLast->next);
        beforeLast->next = NULL;
        list->tail = beforeLast;
    }
    else
    {
        free(list->head);
        LinkedList_Init(list);
    }
    if(list->length>0)
    {
        --list->length;
    }
    return true;
#ifdef DEBUG
    printf("Actual length -> [%d]\n",list->length);
#endif
}

bool LinkedList_Find(LinkedList *list, void* toFind)
{
    Node *tmp = list->head;
    while(tmp!=NULL)
    {
        if(toFind==tmp->data) return true;
        tmp = tmp->next;
    }
    return false;
}
void LinkedList_Reverse(LinkedList *list, void(*swap)(int*,int*))
{
    int len, i;
    for (i = 0, len = list->length-1; i < len; ++i, --len)
    {
        swap((int*)getNode(list,i), (int*)getNode(list,len));
    }

}

bool LinkedList_InsertAt(LinkedList *list, int index, void* data)
{

    Node *tmp = list->head;
    Node *newNode = createNode(data);
    Node *left, *right;
    int count = 0;
    if(index > list->length) return false;
    if(index == 0)  LinkedList_PushFront(list,createNode(data));
    else if (index == list->length) LinkedList_Add(list,createNode(data));
    else if(index > 0 && index < list->length)
    {
        {
            while(tmp!=NULL)
            {
                left = tmp;
                right = tmp->next;
                if(count == index - 1)
                {
                    left->next = newNode;
                    newNode->next = right;
                    ++list->length;
                    break;

                }
                ++count;
                tmp = tmp->next;
            }

        }

    }
    return true;
}

bool LinkedList_DeleteAt(LinkedList *list, int index)
{

    Node *left, *right;
    Node *tmp = list->head;
    int count = 0;
    if(index > list->length) return false;
    if(index > 0 && index < list->length-1)
    {

        while(tmp!=NULL)
        {

            left = tmp;
            right = tmp->next;
            if(count == index-1)
            {
#ifdef DEBUG
                printf("left -> %d right -> %d\n", left->data, right->data);
#endif
                left->next = right->next;
                free(right);
                right = NULL;

                break;
            }

            ++count;
            tmp = tmp->next;
        }
        --list->length;

    }
    else if (index == list->length-1)
    {
        LinkedList_DeleteLast(list);
    }
    else if(index == 0)
    {
        if(list->length > 1)
        {
            list->head = list->head->next;
            free(tmp);
            tmp = NULL;
            --list->length;
        }
        else
        {
            LinkedList_DeleteLast(list);
        }

    }
    return true;
}
void LinkedList_Free(LinkedList *list)
{
    LinkedList_Clear(list);
    free(list);
    list = NULL;
}


void LinkedList_Clear(LinkedList *list)
{
    while(list->head!=NULL)
    {
        LinkedList_DeleteAt(list,0);
    }
}

Main.c

#include "LinkedList.h"
#define MAXSIZE 4

void swap(int*,int*);
void showData(LinkedList*);

typedef struct Person
{
    const char* name;
    int age;

} Person;

int main(int argc, char const *argv[])
{
    Person defaultUsers[MAXSIZE];
    int i;
    for(i = 0; i < MAXSIZE; i++)
    {
        defaultUsers[i].age = i;
        defaultUsers[i].name = "__generic__user__";
    }

    LinkedList *list = (LinkedList*)malloc(sizeof(LinkedList));
    if(LinkedList_Init(list))
    {

        for(i = 0; i < MAXSIZE; i++)
        {
            LinkedList_Add(list,createNode((Person*)&defaultUsers[i]));
        }

        LinkedList_Reverse(list,&swap);
        showData(list);
        LinkedList_Free(list);
    }
    return 0;

}
void showData(LinkedList *list)
{
    int i;
    for(i = 0; i < list->length; i++)
    {
        printf("%s is %d\n",(*((Person*)LinkedList_GetDataAt(list,i))).name, (*((Person*)LinkedList_GetDataAt(list,i))).age);
    }

}
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

Answer 1

LinkedList_Init

You've declared your function as bool LinkedList_Init(LinkedList*), but what information does the returned bool convey? You're always returning true, so no information is gleaned from the returned value. I'd suggest redeclaring your function to return void and remove the return statement.

This goes for a few of your other functions that return bool. If you're always returning the same value of true or false, just remove the return statement and declare the function to return void. Here's the list of such functions which I've changed below.

void LinkedList_Init(LinkedList*);
void LinkedList_Add(LinkedList*, Node*);
void LinkedList_PushFront(LinkedList*, Node*);
void LinkedList_DeleteLast(LinkedList*);

LinkedList_GetDataAt

In this function, when you are passed an invalid index, you return 0. This works, but is not the best way of doing things. This function is supposed to return a void*, so you should be returning NULL. You've used NULL elsewhere in your code, so it is helpful to be consistent.

LinkedList_Reverse

Your code grabs the Node* from the LinkedList then converts it to an int*, therefore treating a Node as an int. The swap function you defined swaps the values in the int*s, effectively swapping the first sizeof(int) bytes of your Nodes (most likely the void* data members). I'm not sure if this was intentional, but it certainly is pretty unintuitive and most likely unreliable. Instead, I would change your code to this, then redefine your swap function afterwards.

void LinkedList_Reverse(LinkedList *list) {
    int len, i;
    for (i = 0, len = list->length-1; i < len; ++i, --len)
    {
        swap(&(getNode(list,i)->data), &(getNode(list,len)->data));
    }
}

I think it would be helpful to redefine your swap function like so below. I would strongly suggest including the swap function in your "LinkedList.c" file as well. It is going to do the same thing no matter what is in your LinkedList, so why leave this implementation up to the user? Just define swap for yourself as a helper function.

void swap(void **a, void **b) {
    void *temp = *a;
    *a = *b;
    *b = temp;
}

This will swap void*s when passed addresses to void*s, a.k.a. void**s. Now your LinkedList_Reverse function will swap the void* data members in the Nodes correctly.

Answer 2

Casting

Generally speaking, you don't want to put explicit casts into your code unless they are actually needed. They usually just add noise to the code / make it harder to change the implementation in the future.

Since malloc returns a void, you don't need to cast it for example. So, this:

Node *tmp = (Node*)malloc(sizeof(Node));

Can just be:

Node *tmp = malloc(sizeof(Node));

You don't need to cast here:

LinkedList_Add(list,createNode((Person*)&defaultUsers[i]));

Because the compile knows what type defaultUsers is, it should simply be:

LinkedList_Add(list,createNode(&defaultUsers[i]));

Init

In its current form init feels dangerous and incomplete. Is it likely that the user is going to want to create a list without initialising it? It doesn't seem likely to me. I'd prefer to see something like this:

LinkedList *LinkedList_Init()
{
    LinkedList *list = malloc(sizeof(LinkedList));

    if(list) 
    {    
        list->tail = list->head = NULL;
        list->length = 0;
    }
    return list;
}

Note: This won't work currently with your code, because of the way you have implemented DeleteLast.

Consider Your API

At the moment, the users of your LinkedList know everything about the structure, all of its members and the data structures that it relies on. You've indicated that you've done Java programming before. This approach is the equivalent of declaring all of your classes members as public. This might be what you want to do, but I would tend to avoid it unless there's a good reason for it.

A better version of your header files definitions might look like this:

typedef struct LinkedList LinkedList;

LinkedList *LinkedList_Create();
void* LinkedList_GetDataAt(LinkedList* list, int index);
bool LinkedList_DeleteLast(LinkedList* list);
bool LinkedList_Contains(LinkedList* list, void* data);
void LinkedList_Reverse(LinkedList* list);
void LinkedList_Clear(LinkedList* list);
bool LinkedList_InsertAt(LinkedList* list, int index, void* data);
bool LinkedList_DeleteAt(LinkedList*list, int index);
void LinkedList_Free(LinkedList* list);  
unsigned LinkedList_Size(LinkedList *list);    
bool LinkedList_Add(LinkedList*, void *data);

Things to notice:

• I've removed the Node datatype and removed it from all function declarations. This is an implementation detail of the list, there's no need for the clients to know about it.
• I've changed the name of LinkedList_Init to LinkedList_Create to reflect the fact that it creates + initialises the list in one step.
• I've added a Size function to return the size of the list. This helps to complete the API, so that the client need access to the contents of the LinkedList struct.
• I've renamed LinkedList_Find to LinkedList_Contains, since it seems to check if the item exists in the list, rather than returns it.
• I've added parameter names to the declarations. Adding a name gives a hint as to what the expected parameter might be for.
• I've removed the swap parameter from Reverse. As has been said by @kamoroso94, swap is unlikely to change and so shouldn't be provided by the client. It is really an implementation detail of the list that should be in the LinkedList.c file.

Answer 3

Some style related feedback.

Make logical blocks within functions

It helps reading your code.

If-statement should be a boolean expression

Do not use if (list), use a boolean expression in the brackets.

Where a data value is to be tested against zero then the test should be made explicit. The exception to this rule is when data represents a Boolean value, even though in C this will in practice be an integer. This rule is in the interests of clarity, and makes clear the distinction between integers and logical values. (from MISRA rule 13.2)

Use brackets if more than one comparison is in if-statement

if(index >= 0 && index < list->length)

should be

if ((index >= 0) && (index < list->length))

Consistency

Decide to which code style you want to stick e.g.

} else { 

or

}
else
{

Use typedefs for function pointers

While others already pointed out that the swap function should be implemented in the list, I just wanted to add that in general typedefs should be used whenever dealing with function pointers.

Do not mix test code with production code

Use unit tests to test your code. You only have two #ifdef in your code, but if every developer adds his #ifdefs then you will soon have a big mess and the code is not going to be readable anymore.

Always check for NULL pointers in public functions

While it is debateable if you should check them for private functions, public functions should always check for NULL pointers.

bool LinkedList_PushFront(LinkedList *list, Node* node)
{
    if(list==NULL){
        return false;
    }

    if(list->head==NULL){
        LinkedList_Add(list, node);
    } else {
        ...
    }
    return true;
}