Data Structures in C (Single Linked List)

Question

NOTE: Added a follow-up question with the reviewed code

I am trying to get back to basics with C, so I am doing some data structures in it.

The following is my implementation of a Single Linked List (The code is on github with tests).

LinkedList.h

/* 
 * File:   LinkedList.h
 * Author: antoniocs
 *
 * Created on 26 de Setembro de 2015, 19:54
 */

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct LinkedList LinkedList;
    typedef struct LinkedListNode LinkedListNode;

    struct LinkedList {
        LinkedListNode *head;
        LinkedListNode *tail;
    };

    struct LinkedListNode {
        void *data;
        LinkedListNode *next;
    };

    LinkedList *LLInit();

    LinkedListNode *LLAddHead(LinkedList *, void *);
    LinkedListNode *LLAddTail(LinkedList *, void *);
    LinkedListNode *LLAdd(LinkedList *, void *);

    void *LLRemoveHead(LinkedList *);
    void *LLRemoveTail(LinkedList *);
    void *LLRemoveNode(LinkedList *, LinkedListNode *);

    typedef int (*LLFindCompareFuncPtr)(void *, void *);    
    LinkedListNode *LLFindNodeByData(LinkedList *, void *, LLFindCompareFuncPtr);
    LinkedListNode *LLFindNodeByNext(LinkedList *, LinkedListNode *);


#ifdef  __cplusplus
}
#endif

#endif  /* LINKEDLIST_H */

LinkedList.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "LinkedList.h"
#include "../../../dbg.h"

enum LLAddStrategy {
    HEAD,
    TAIL
};

struct LLFindNodeBaseParams {
    LinkedList *ll;

    void *data;
    LLFindCompareFuncPtr compareFunc;

    LinkedListNode *node;
    LinkedListNode *next;
};

struct FindResult {
    LinkedListNode *prev;
    LinkedListNode *node;
};


static struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *);

typedef bool(*findByFuncPtr)(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByData(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
//To the outside this function is not really necessary
static struct FindResult *LLFindNode(LinkedList *, LinkedListNode *);
static bool FindByNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static bool FindByNextNode(struct LLFindNodeBaseParams *, struct FindResult *, LinkedListNode *);
static struct FindResult *InitFindResult(void);
static bool FindResultSetResult(bool, struct FindResult *, LinkedListNode *);
//static struct LLFindNodeBaseParams *InitLLFindNodeBaseParams();



static LinkedListNode *NodeInit();
static LinkedListNode *LLAddBase(LinkedList *, void *, enum LLAddStrategy);

LinkedList *LLInit() {
    LinkedList *ll = malloc(sizeof (LinkedList));
    check(ll, "Unable to allocate memory for linked list");

    ll->head = NULL;
    ll->tail = NULL;

    return ll;

error:
    return NULL;
}

/**
 * Add an item to the linked list in the head or the tail
 * 
 * @param ll
 * @param data
 * @param type
 * @return int (will be 1 for failure and 0 for sucess)
 */
LinkedListNode *LLAddBase(LinkedList *ll, void *data, enum LLAddStrategy stype) {
    check(ll, "LLAddBase received null pointer");
    LinkedListNode *node = NodeInit(data, NULL);

    if (ll->head == NULL) {
        ll->tail = ll->head = node;
    } else {
        if (stype == HEAD) {
            node->next = ll->head;
            ll->head = node;
        } else {
            ll->tail->next = node;
            ll->tail = ll->tail->next;
        }
    }

    return node;
error:
    return NULL;
}

/**
 * Add a node to the start of the Linked List
 * 
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAddHead(LinkedList *ll, void *data) {
    return LLAddBase(ll, data, HEAD);
}

/**
 * Add a node to the end of the Linked List
 *
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAddTail(LinkedList *ll, void *data) {
    return LLAddBase(ll, data, TAIL);
}

/**
 * Shorter alias for LLAddTail
 * 
 * @param ll
 * @param data
 * @return
 */
LinkedListNode *LLAdd(LinkedList *ll, void *data) {
    return LLAddTail(ll, data);
}

/**
 *
 * @param data
 * @param next
 * @return
 */
LinkedListNode *NodeInit(void *data, LinkedListNode *next) {
    LinkedListNode *lln = malloc(sizeof (LinkedListNode));
    check(lln, "Unable to allocate memory for linked list node");

    lln->data = data;
    lln->next = next;

    return lln;
error:
    return NULL;
}

void *LLRemoveHead(LinkedList *ll) {
    return LLRemoveNode(ll, ll->head);
}

void *LLRemoveTail(LinkedList *ll) {
    return LLRemoveNode(ll, ll->tail);
}

void *LLRemoveNode(LinkedList *ll, LinkedListNode *node) {
    void *data = node->data;
    struct FindResult *res = LLFindNode(ll, node);

    check(res->node, "Node not found on List");

    if (node == ll->head) {
        if (ll->head->next == NULL) {
            ll->head = ll->tail = NULL;
        } else {
            ll->head = ll->head->next;
        }
    } else {
        if (node == ll->tail) {
            res->prev->next = NULL;
            ll->tail = res->prev;
        } else {
            res->prev->next = node->next;
        }
    }

    free(node);
    return data;

error:
    return NULL;
}

struct FindResult *LLFindNode(LinkedList *ll, LinkedListNode *node) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .node = node
    };
    struct FindResult *res = FindNodeBase(&fnbParams);
    return res;
}

LinkedListNode *LLFindNodeByData(LinkedList *ll, void *data, LLFindCompareFuncPtr func) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .data = data,
        .compareFunc = func
    };
    struct FindResult *res = FindNodeBase(&fnbParams);

    LinkedListNode *node = res->node;
    free(res);

    return node;
}

LinkedListNode *LLFindNodeByNext(LinkedList *ll, LinkedListNode *nodeNext) {

    struct LLFindNodeBaseParams fnbParams = {
        .ll = ll,
        .next = nodeNext
    };
    struct FindResult *res = FindNodeBase(&fnbParams);

    LinkedListNode *node = res->node;
    free(res);

    return node;
}

struct FindResult *FindNodeBase(struct LLFindNodeBaseParams *params) {
    findByFuncPtr fptr = NULL;

    if (params->data != NULL && params->compareFunc != NULL) {
        fptr = FindByData;
    } else if (params->node != NULL) {
        fptr = FindByNode;
    } else if (params->next != NULL) {
        fptr = FindByNextNode;
    } else {
        goto error;
    }

    LinkedListNode *node = params->ll->head;
    struct FindResult *res = InitFindResult();

    check(res, "Unable to allocate memory for FindResult structure");
    bool foundNode = false;

    while (node != NULL) {
        if ((foundNode = fptr(params, res, node))) {
            break;
        }
        node = node->next;
    }

    if (foundNode == false) {
        res->node = NULL;
        res->prev = NULL;
    }

    return res;

error:
    return NULL;
}

bool FindByData(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->compareFunc(params->data, node->data) == 0, res, node);
}

bool FindByNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->node == node, res, node);
}

bool FindByNextNode(struct LLFindNodeBaseParams *params, struct FindResult *res, LinkedListNode *node) {
    return FindResultSetResult(params->next == node->next, res, node);
}

bool FindResultSetResult(bool condition, struct FindResult *res, LinkedListNode *node) {
    if (condition) {
        res->node = node;
    } else {
        res->prev = node;
    }

    return condition;
}

struct FindResult *InitFindResult() {
    struct FindResult *res = malloc(sizeof (struct FindResult));
    check(res, "Unable to allocate memory for FindResult");

    res->node = NULL;
    res->prev = NULL;

    return res;

error:
    return NULL;
}

Please tell me if anything seems off.

I also thought about creating separate files for each of the functions and then having one header file that would just combine everything. What are your thoughts on that?

All the tests are passing (you can see the test file in the github link provided)

Thanks!

Answer 1

First, the header:

1. You are currently creating a typedef-name and a struct tag with the same name (so far, so good), and then defining the struct, in the same header-file but separately.
   Consider merging them:

   typedef struct LinkedList {
       /* lots of members here */
   } LinkedList;
   

2. Why do you define a typedef for the comparison-function?

3. Also, are you really sure the pointers given to the user-supplied comparison-function should not be const-qualified?

4. Finally, why don't you allow for a context-pointer?

   Just make it the same as qsort and qsort_s in the standard library.

Next, the sourcefile:

1. Why do you add forward-declarations instead of defining before use?
   DRY (Don't Repeat Yourself)

2. Avoid sizeof(SomeType), use sizeof expression instead.
   Thus the types cannot get out-of-sync.

There are many more good points in the other reviews.

Answer 2

When removing a head node:

if (node == ll->head) {
    if (ll->head->next == NULL) {
        ll->head = ll->tail = NULL;
    } else {
        ll->head = ll->head->next;
    }

ll->head becomes ll->head->next regardless of its NULLness. Code could be streamlined:

if (node == ll->head) {
    ll->head = ll->head->next;
    if (ll->head == NULL) {
        ll->tail = NULL;
    }

Similarly, in a general case the res->prev->next is also well-defined:

} else {
    res->prev->next = node->next;
    if (node == ll->tail) {
        ll->tail = res->prev;
    }
}

Answer 3

/**
 * Add an item to the linked list in the head or the tail
 * 
 * @param ll
 * @param data
 * @param type
 * @return int (will be 1 for failure and 0 for sucess)
 */
LinkedListNode *LLAddBase(LinkedList *ll, void *data, enum LLAddStrategy stype) {
    check(ll, "LLAddBase received null pointer");
    LinkedListNode *node = NodeInit(data, NULL);

    if (ll->head == NULL) {
        ll->tail = ll->head = node;
    } else {
        if (stype == HEAD) {
            node->next = ll->head;
            ll->head = node;
        } else {
            ll->tail->next = node;
            ll->tail = ll->tail->next;
        }
    }

    return node;
error:
    return NULL;
}

Your documentation here is wrong. You say I get int back, and what I get back is... a LinkedListNode*.

if (node == ll->head) {
    if (ll->head->next == NULL) {
        ll->head = ll->tail = NULL;
    } else {
        ll->head = ll->head->next;
    }
} else {
    if (node == ll->tail) {
        res->prev->next = NULL;
        ll->tail = res->prev;
    } else {
        res->prev->next = node->next;
    }
}

Else statement containing only an if-else chain, can be merged.

---

FindNodeBase silently fails with goto error and returning NULL if you provide it with bad params. You might want to replace this with a check(fptr, "Bad params for FindNodeBase, can't determine find function").