Generic double linked list implementation with tests in C

Question

Can you please give your feedback to my double linked list implementation below? It comes with some very basic functions as well as separate code to test the implementation. The tests are only 'success' tests. I used valgrind to catch and fix any kind of memory-related issues that I came across and valgrind did not report any issues with the implementation. If it matters, I am running this under macOS; I do not know if valgrind on Linux systems would produce errors or warnings with the code.

Apologies in advance if the naming convention is a bit verbose or not like any C naming convention; I am still very new to C and my knowledge on naming conventions is limited.

DoubleLinkedList.h

#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H

// error codes
static const int ENOMEMORY = -1; // Could not allocate memory
static const int ENULLIST = -2; // The list is null; memory could not have been allocated to it
static const int EEMPTYNODE = -3; // The node is null

typedef struct DoubleLinkedList_Node
{
    void* data;
    struct DoubleLinkedList_Node* next;
    struct DoubleLinkedList_Node* previous;
} DoubleLinkedList_Node;

typedef struct DoubleLinkedList
{
    DoubleLinkedList_Node* head;
    DoubleLinkedList_Node* tail;
} DoubleLinkedList;

unsigned int DoubleLinkedList_Count(DoubleLinkedList *list);

DoubleLinkedList *DoubleLinkedList_Initialize(void);

int DoubleLinkedList_Destroy(DoubleLinkedList *list);

int DoubleLinkedList_Add(DoubleLinkedList *list, void *data_to_add);

DoubleLinkedList_Node *DoubleLinkedList_GetNode(DoubleLinkedList *list, void *data_to_search);

int DoubleLinkedList_GetNodes(DoubleLinkedList *list, void *data_to_search, DoubleLinkedList *return_list);

int DoubleLinkedList_Foreach(DoubleLinkedList *list, void (DoubleLinkedList_Node *callback));

int DoubleLinkedList_ForeachReverse(DoubleLinkedList *list, void (DoubleLinkedList_Node *callback));

int DoubleLinkedList_Clear(DoubleLinkedList *list);

int DoubleLinkedList_Remove(DoubleLinkedList *list, DoubleLinkedList_Node *node_to_remove);

int DoubleLinkedList_Find(DoubleLinkedList *list, void *data_to_find, DoubleLinkedList *return_list);

#endif //DOUBLELINKEDLIST_H

DoubleLinkedList.c

#include <stdlib.h>
#include "DoubleLinkedList.h"


unsigned int DoubleLinkedList_Count(DoubleLinkedList *list)
{
    if (!list) return ENULLIST;
    unsigned int count = 0;
    DoubleLinkedList_Node *current_node = list->head->next;
    while (current_node != list->tail)
    {
        count++;
        current_node = current_node->next;
    }
    return count;
}

DoubleLinkedList* DoubleLinkedList_Initialize(void)
{
    DoubleLinkedList* return_value = calloc(1, sizeof(DoubleLinkedList));
    if (return_value)
    {
        return_value->head = calloc(1, sizeof(DoubleLinkedList_Node));
        return_value->tail = calloc(1, sizeof(DoubleLinkedList_Node));

        if (return_value->head && return_value->tail)
        {
            return_value->head->next = return_value->tail;// connect the head to the tail
            return_value->tail->previous = return_value->head;// connect the tail to the head
            return_value->tail->data = NULL;
            return_value->tail->next = NULL;
            return_value->head->previous = NULL;

            return return_value;
        }
    }
    return NULL;
}
int DoubleLinkedList_Destroy(DoubleLinkedList* list)
{
    if (!list) return ENULLIST;
    while (list->head)
    {
        DoubleLinkedList_Node* node_to_free = list->head;
        list->head = list->head->next;
        free(node_to_free);
        node_to_free = NULL;
    }
    free(list->head);
    list->head = NULL;

    free(list);
    list = NULL;
    return 0;
}

int DoubleLinkedList_Add(DoubleLinkedList *list, void *data_to_add)
{
    DoubleLinkedList_Node* new_node = calloc(1, sizeof(DoubleLinkedList_Node));
    if (!new_node) return ENOMEMORY;

    list->tail->data = data_to_add;
    new_node->data = NULL;
    new_node->next = NULL;
    new_node->previous = list->tail;

    // make the new node the tail
    list->tail->next = new_node;

    //current tail is now the second to the last node
    list->tail = new_node;

    return 0;

}
DoubleLinkedList_Node* DoubleLinkedList_GetNode(DoubleLinkedList* list, void* data_to_search)
{
    // from head, iterate through the list to find the data
    DoubleLinkedList_Node* return_value = list->head;
    while (return_value)
    {
        if (return_value->data == data_to_search && return_value != list->head && return_value != list->tail)
        {
            return return_value;
        }
        // move to the next node
        return_value = return_value->next;
    }
    // at this point, we went through the entire list but couldn't find the value; return NULL
    return NULL;
}

int DoubleLinkedList_Foreach(DoubleLinkedList* list, void (*callback)(DoubleLinkedList_Node *))
{
    if (!list) return ENULLIST;

    DoubleLinkedList_Node* currentNode = list->head;
    while (currentNode != list->tail)
    {
        // don't include the head and the tail in the evaluation
        if (currentNode != list->head && currentNode != list->tail)
        {
            callback(currentNode);
        }
        currentNode = currentNode->next;
    }
    return 0;
}

int DoubleLinkedList_ForeachReverse(DoubleLinkedList *list, void(*callback) (DoubleLinkedList_Node *))
{
    if (!list) return ENULLIST;

    DoubleLinkedList_Node *currentNode = list->tail;
    while (currentNode != list->head)
    {
        // don't include the head and the tail in the evaluation
        if (currentNode != list->head && currentNode != list->tail)
        {
            callback(currentNode);
        }
        currentNode = currentNode->previous;
    }
    return 0;
}

int DoubleLinkedList_Clear(DoubleLinkedList *list)
{
    if (!list) return ENULLIST;

    DoubleLinkedList_Node *currentNode = list->head->next;
    while (currentNode != list->tail)
    {
        currentNode = currentNode->next;
        free(currentNode->previous);
        currentNode->previous = NULL;
    }

    // reconnect the head to the tail and the tail to the head

    list->head->next = list->tail; // connect the head to the tail
    list->tail->previous = list->head; // connect the tail to the head
    list->tail->data = NULL;
    list->tail->next = NULL;
    list->head->previous = NULL;

    return 0;
}

int DoubleLinkedList_Remove(DoubleLinkedList *list, DoubleLinkedList_Node *node_to_remove)
{
    if (!list) return ENULLIST;

    if (!node_to_remove) return EEMPTYNODE;

    DoubleLinkedList_Node *current_node = list->head->next;
    while (current_node != list->tail)
    {
        if (current_node->data == node_to_remove->data)
        {
            // connect the currentNode's previous to its next and vice-versa
            current_node->previous->next = current_node->next;
            current_node->next->previous = current_node->previous;
            free(current_node);
            current_node = NULL;

            return 0;
        }
        current_node = current_node->next;
    }
    // at this point, the record has not found.
    return 0;
}

int DoubleLinkedList_GetNodes(DoubleLinkedList *list, void *data_to_search, DoubleLinkedList *return_list)
{
    if (!list) return ENULLIST;

    if (!return_list) return ENULLIST;

    DoubleLinkedList_Node *current_node = list->head->next;
    while (current_node != list->tail)
    {
        if (current_node->data == data_to_search)
        {
            int addResult = DoubleLinkedList_Add(return_list, current_node->data);
            if (addResult != 0) return addResult;
        }
        current_node = current_node->next;
    }
    return 0;
}

int DoubleLinkedList_Find(DoubleLinkedList *list, void *data_to_find, DoubleLinkedList *return_list)
{
    if (!list) return ENULLIST;

    if (!return_list) return ENULLIST;

    DoubleLinkedList_Node *current_node = list->head->next;
    while (current_node != list->tail)
    {
        if (current_node->data == data_to_find)
        {
            int addResult = DoubleLinkedList_Add(return_list, current_node->data);
            if (addResult != 0) return addResult;
        }
        current_node = current_node->next;
    }
    return 0;
}

For testing:

DoubleLinkedListTests.h

#ifndef DOUBLELINKEDLISTTESTS_H
#define DOUBLELINKEDLISTTESTS_H

// runner

void DoubleLinkedList_Tests_RunAllTests(void);

// success tests

void DoubleLinkedList_SuccessTests_Count(void);

void DoubleLinkedList_SuccessTests_InitializeAndDestroy(void);

void DoubleLinkedList_SuccessTests_Add(void);

void DoubleLinkedList_SuccessTests_GetNode(void);

void DoubleLinkedList_SuccessTests_GetNodes(void);

void DoubleLinkedList_SuccessTests_Foreach(void);

void DoubleLinkedList_SuccessTests_ForeachReverse(void);

void DoubleLinkedList_SuccessTests_Clear(void);

void DoubleLinkedList_SuccessTests_Remove(void);

void DoubleLinkedList_SuccessTests_Find(void);

#endif //DOUBLELINKEDLISTTESTS_H

DoubleLinkedListTests.c

#include "DoubleLinkedList.h"
#include <assert.h>
#include <stddef.h>
static char *testData = "test data";

void DoubleLinkedListTests_Foreach_Callback(DoubleLinkedList_Node *node)
{
    assert(node->data == testData);
}

void DoubleLinkedList_SuccessTests_Count(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();

    for (int i = 0; i < 10; i++)
    {
        DoubleLinkedList_Add(list, &i);
    }
    assert(DoubleLinkedList_Count(list) == 10);
    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_InitializeAndDestroy(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();

    assert(list);

    assert(list->head->next == list->tail);

    assert(list->tail->previous == list->head);

    DoubleLinkedList_Destroy(list);

}

void DoubleLinkedList_SuccessTests_Add(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();

    int isSuccess = DoubleLinkedList_Add(list, testData);

    assert(isSuccess == 0);

    assert(list->head->next->data == testData);

    DoubleLinkedList_Destroy(list);

}

void DoubleLinkedList_SuccessTests_GetNode(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);

    DoubleLinkedList_Node *test = DoubleLinkedList_GetNode(list, testData);
    assert(test != NULL);

    assert(test->data == testData);

    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_GetNodes(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList *container = DoubleLinkedList_Initialize();

    DoubleLinkedList_Add(list, testData);
    DoubleLinkedList_Add(list, testData);
    DoubleLinkedList_Add(list, "invalid data");
    DoubleLinkedList_Add(list, "even more invalid data");

    int isSuccess = DoubleLinkedList_GetNodes(list, testData, container);

    assert(isSuccess == 0);

    assert(container->head->next->data == testData);
    assert(container->head->next->next->data == testData);

    DoubleLinkedList_Destroy(list);
    DoubleLinkedList_Destroy(container);

}

void DoubleLinkedList_SuccessTests_Foreach(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);

    int isSuccess = DoubleLinkedList_Foreach(list, DoubleLinkedListTests_Foreach_Callback);
    assert(isSuccess == 0);
    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_ForeachReverse(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);

    int isSuccess = DoubleLinkedList_ForeachReverse(list, DoubleLinkedListTests_Foreach_Callback);
    assert(isSuccess == 0);

    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_Clear(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);

    DoubleLinkedList_Clear(list);

    assert(list->head->next == list->tail);
    assert(list->tail->previous == list->head);

    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_Remove(void)
{
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);

    DoubleLinkedList_Remove(list, list->head->next);
    assert(list->head->next == list->tail);
    assert(list->tail->previous == list->head);


    DoubleLinkedList_Destroy(list);
}

void DoubleLinkedList_SuccessTests_Find(void)
{
    char test2 = '2';
    char *test3 = "testData";
    int test4 = 0;
    double test5 = -123.456;
    DoubleLinkedList *list = DoubleLinkedList_Initialize();
    DoubleLinkedList *container = DoubleLinkedList_Initialize();
    DoubleLinkedList_Add(list, testData);
    DoubleLinkedList_Add(list, &test2);
    DoubleLinkedList_Add(list, test3);
    DoubleLinkedList_Add(list, &test4);
    DoubleLinkedList_Add(list, &test5);

    DoubleLinkedList_Find(list, testData, container);

    assert(container->head->next->data == list->head->next->data);

    DoubleLinkedList_Find(list, &test2, container);
    assert(container->head->next->next->data == list->head->next->next->data);

    DoubleLinkedList_Find(list, test3, container);
    assert(container->head->next->next->next->data == list->head->next->next->next->data);

    DoubleLinkedList_Find(list, &test4, container);
    assert(container->head->next->next->next->next->data == list->head->next->next->next->next->data);

    DoubleLinkedList_Find(list, &test5, container);
    assert(container->tail->previous->data == list->tail->previous->data);

    DoubleLinkedList_Destroy(list);
    DoubleLinkedList_Destroy(container);

}

void DoubleLinkedList_Tests_RunAllTests()
{
    DoubleLinkedList_SuccessTests_Count();
    DoubleLinkedList_SuccessTests_InitializeAndDestroy();
    DoubleLinkedList_SuccessTests_Add();
    DoubleLinkedList_SuccessTests_GetNode();
    DoubleLinkedList_SuccessTests_GetNodes();
    DoubleLinkedList_SuccessTests_Foreach();
    DoubleLinkedList_SuccessTests_ForeachReverse();
    DoubleLinkedList_SuccessTests_Clear();
    DoubleLinkedList_SuccessTests_Remove();
    DoubleLinkedList_SuccessTests_Find();
}

main.c

#include "DoubleLinkedListTests.h"

int main(void)
{
    DoubleLinkedList_Tests_RunAllTests();
    return 0;
}

Answer 1

Overall this looks pretty good, and valgrind should catch most common errors in a linked list.

• Test running out of memory.
• Get someone to review your API in person. It's good, just a little weird.
• Write documentation for your API. Why is there no next method, is the programmer expected to use pointers? What do the error codes mean, and what can each API method return? What is and isn't safe during iteration? Can you delete during Foreach? Add nodes? For things like find, explicitly mention that the user is responsible for freeing the space, and how to.
• Right now this is "Generic" in the sense that it stores a void*, which is not the common usage of that term. When I hear 'generic' I expect 'takes one or more template types'. In C the usual method I've seen is to use lots of macros. The end effect is that either you have typed pointers, or you avoid the overhead of pointers by putting the object into the node struct. Code with lots of macros is ugly, so it's up to you if you want to do that.
• Efficiency. C users like low overhead, especially in a library like this.
  • It's more common to offer find as an increment search (give the find the last found node, and it finds the next one) instead of returning a list. Or you could define some kind of iterator and return that.
  • Have you encountered the xor trick for doubly linked lists? It's fine (arguably good) not to use it, but it's good to know it exists.
  • Why is an empty list two nodes, instead of one or zero? Something like a hash table may make one linked list per entry, so it may be worth optimizing.