A linked list in C, as generic and modular as possible, for my personal util library

Question

I want to implement a linked list in C that I can add to my personal util library and keep it as generic and modular as possible

This is my header file containing all of the function prototypes and struct definitions:

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

typedef struct NodeType {
    void*     value;
    struct NodeType* next;
} Node;

typedef struct LinkedListType {
    Node*  head;
    int   (*compare)(void*, void*);
    void  (*free)   (void*);    
} LinkedList;

LinkedList* linkedList_init(LinkedList* list, 
                            int  (*compare)  (void*, void*),
                            void (*freeData) (void*));          // Initializes the generic functions and head of the list

int linkedList_isInitialized(LinkedList* list);                 // Return 0 if is empty, otherwise return 1

int linkedList_add(LinkedList* list, void* data);               // Add a node to the end

int linkedList_remove(LinkedList* list, int index);             // Remove a node at index

int linkedList_insert(LinkedList* list, int index, void* data); // Insert a node at index

void* linkedList_get(LinkedList* list, int index);              // Return value of node at index, otherwise if index out of bounds return NULL

void linkedList_free(LinkedList* list);                         // Free all the elements in the list

#endif

And this is my implementation

#include <linkedList.h>

#define INDEX_OUT_OF_BOUNDS fprintf(stderr, "Index out of bounds \n");

int linkedList_init(
    LinkedList* list, 
    int (*compare)(void*, void*), 
    void (*freeData)(void*))
{
    // Set generic functions in LinkedList
    list->compare = compare;
    list->freeData = freeData;
    
    // Create head node
    list->head = (Node*)malloc(sizeof(Node));
    list->head->next = NULL;
    
    return 0;
    
}

int linkedList_isInitialized(LinkedList* list)
{
    if(list->head == NULL)
    {
        fprintf(stderr, "List is not initialized");
        return 1;
    }
    
    return 0;
}

int linkedList_add(LinkedList* list, void* data)
{
    if(! linkedList_isInitialized(list)) return 1;
    
    // Iterate through list starting with head until next node is null
    Node* node = list->head;
    while(node->next != NULL)
    {
        node = node->next;
    }
    
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->value = data;
    
    // Link new node
    node->next = newNode;
    
    return 0;
}

int linkedList_remove(LinkedList* list, int index)
{
    if(! linkedList_isInitialized(list)) return 1;
    
    if(index < 0) {INDEX_OUT_OF_BOUNDS; return 1;}
    
    // Zero index edge case
    if(index == 0)
    {   
        Node* nodeToRemove = list->head->next;
        list->head->next = nodeToRemove->next;
        
        free(nodeToRemove);
        return 0;
    }
    
    // Traverse list and find node
    int i = 0;
    Node* previousNode = list->head;
    while(previousNode->next != NULL && i < index - 1)
    {
        previousNode = previousNode->next;
        i++;
    }
    
    // Check if index was out of bounds
    if(! internal_indexIsInBounds(i, index - 1)) return 1;
    
    Node* nodeToRemove = previousNode->next;
    previousNode->next = nodeToRemove->next;
        
    free(nodeToRemove);
    return 0;
}

int linkedList_insert(LinkedList* list, int index, void* data)
{
    if(! linkedList_isInitialized(list)) return 1;
    
    if(index < 0) {INDEX_OUT_OF_BOUNDS; return 1;}
    
    // Instantiate new node to be inserted
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = data;
    
    // Zero index insertion replaces head->next
    if(index == 0)
    {
        Node* nextNode = list->head->next;
        
        list->head->next = newNode;
        newNode->next = nextNode;
        
        return 0;
    }
    
    // Traverse list and find node
    int i = 0;
    Node* parentNode = list->head->next;
    while(parentNode->next != NULL && i < index - 1)
    {
        parentNode = parentNode->next;
        i++;
    }
    
    // Check if index was out of bounds
    if(! internal_indexIsInBounds(i, index - 1)) return 1;
    
    // Insert node after parent node
    
    Node* nextNode = parentNode->next;
    
    parentNode->next = newNode;
    newNode->next = parentNode;
    
    return 0;
}

void* linkedList_get(LinkedList* list, int index)
{
    if(! linkedList_isInitialized(list)) return NULL;
    
    if(index < 0) {INDEX_OUT_OF_BOUNDS; return NULL;}
    
    int i = 0;
    Node* node = list->head->next;
    while(node != NULL && i < index)
    {
        node = node->next;
        i++;
    }
    
    if(! internal_indexIsInBounds(i, index)) return NULL;
    
    return node->value;
}

static int internal_indexIsInBounds(int i, int index)
{
    if(index < 0) {INDEX_OUT_OF_BOUNDS; return 1;}
    
    if(i < index)
    {
        INDEX_OUT_OF_BOUNDS;
        return 0;
    }
    
    return 1;
}

I want this code to be as clear to read, easy to use, robust, and all around airtight as possible so please nitpick anything that seems dependent or non-modular. I plan to use this is a multitude of projects and I don't want to have to go back very often and deal with implementation or design details of lower level stuff like this.

Answer 1

Immediate notes:

• Casting malloc (as well as realloc and calloc) is not necessary in C. Leaving them out will not cause warnings or errors and may suppress warnings that would otherwise be helpful. It is necessary in C++, but that's only relevant if you're using a C++ compiler to compile C code. Some reading on Stack Overflow: Should I cast the result of malloc (in C)?
• You are not verifying that malloc has succeeded before dereferencing that pointer by checking it against NULL before use. This can lead to undefined behavior. See linkedlist_init for an example of this.
• In the same function you use the list argument before checking that it is not NULL. You may know that in your current use case a null pointer is never passed in, but can you guarantee that will always be the case?

From a general design standpoint, consider whether you really want to use linked lists extensively in your code, or if you want a dynamic array, more akin to C++'s std::vector. Linked lists have O(n) random access and must perform a dynamic memory allocation on each insertion. A dynamic array can have O(1) access and if designed properly, only O(log n) dynamic memory allocations, and O(1) on de-allocation.

You may wish to watch Bjarne Stroustrup: Why you should avoid Linked Lists.

---

If you decide you do want to pursue the linked list, then there are some key things to think about.

• You probably want your list struct to hold a pointer to the last in addition to the first node. This makes appending to the end an O(1) operation rather than O(n).
• You probably want to make this an opaque data type so that the user of a list cannot break things like that pointer to the last node. Stack Overflow reading: What defines an opaque type in C, and when are they necessary and/or useful?
  • If you do this, it's trivial to have your list contain a member describing its length. Any operation that modifies the length updates this member. With this, getting the length of a linked list becomes O(1) rather than O(n).
• Your node holds a pointer to the data it refers to. Do you want your lists to "own" the data they point to, or simply point to it? On freeing a list, should it also free that data?
  • It looks a bit like you were heading in the direction of letting your freeData function pointer decide this.
  • You might implement append and append_copy to handle this issue, with the latter copying data from the value passed in rather than just saving a pointer to it.

Answer 2

Overview

You never use the compare or freeData members of the linked list why are they there?

Also it obviously does not compile as the header it is free while in the code it is freeData (Copy and paste error?).

You have a lot of code checking the size of the list. Why not add a member to the "LinkedList" to store the number of members?

Bug(s)

You assume malloc() zeros out the memory that is returned. It does not. See the comment about the Init function.

Code Review

Seems a bit generic.

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

I would be worried that another library I include in my project has the same header guard.

---

If you have "free" are you not also going to need an "allocate" to go with that? Normally these functions come in pairs that need to match.

typedef struct LinkedListType {
    Node*  head;
    int   (*compare)(void*, void*);
    void  (*free)   (void*);    
} LinkedList;

---

The name isInitialized does not match the comment (is empty). Why the difference?

int linkedList_isInitialized(LinkedList* list);                 // Return 0 if is empty, otherwise return 1

---

Adding to the end is more commonly referred to as "append".

int linkedList_add(LinkedList* list, void* data);               // Add a node to the end

---

Why are you creating a node when the list is empty?

int linkedList_init(

   ....
    
    // Create head node
    list->head = (Node*)malloc(sizeof(Node));
     // Note: list->head->value has an indeterminate value.
     //       You could use malloc () to make sure it is zeroed out.
     //       But malloc does not do anything with the memory so
     //       it could potentially have any value.
    list->head->next = NULL;

---

Two issues:

1: This does not match the comments in the header file.

int linkedList_isInitialized(LinkedList* list)
{
    if(list->head == NULL)
    {
        fprintf(stderr, "List is not initialized");
        return 1;
    }
    
    return 0;
}

2: It is not guaranteed to work. If you have not called Init the value is indeterminate. You can't test to see if it is valid that way.

---

Answer 3

(It was suggested some suggestions in comments be posted as a full answer. Here we go...)

Silent functions

To make full use of library functions, those functions should never contain expectations that output messages can/will be read. Code intended to be packaged into a library can return published status codes allowing the calling application code to handle unfavourable situations appropriately. (An error message to stdout, even stderr might not be the right thing to do.)

(Always verify the return code from library or system functions.)

Linked List as a Stack

Without requiring a predefined allocation, the Linked List data structure is useful as a stack.

Code implementing both push() and pop() (and sizeOf(), and getTop()) would be programmer friendly.

Faster append()

Adding to the tail of a long LL would execute faster if the LL object maintained a pointer to the current tail node (as it does to the head node.)

Feature creep

Down the road, the OP may find a need for a "double linked list". Perhaps even a "circular linked list" or a "circular double linked list". The OP should consider how close to fulfilling many/all future needs the current code actually is before calling it a day.

Generic comes at a price

There are a number of Standard Library implementations of malloc() and its cousins. Inside that black box, its easy to imagine some form of linked list code that maintains pointers AND byte counts. On modern hardware, it's likely any heap allocation carries (at least) a 16 byte overhead.

The OP's "generic" Node is, itself, another 16 bytes, without considering any data stored. If that data is, trivially, an 8 byte double stored in another heap allocation (16 more bytes), one begins to see the cost. One double stored in a node of the OP's LL will consume (estimated) 56 bytes of memory. Ouch!

Accessing these nodes will also require both the system library functions and application functions to sequentially skip through their collections of occupied nodes.

Opacity

The current version requires the caller to include a header file that exposes the implementation of the linked list: those struct declarations. This risks coders taking short cuts, writing application code that directly manipulates the mechanics of the linked list. This increases the maintenance headache if/when the library implementation details are ever altered.

Application code should not be able to "see" the inside workings of a library function. (Eg: Without digging, a coder does not know how their malloc()/free() functions actually work; just that they do.)

Odd notes

Examine the function parameter list: LinkedList* list, int (*compare)(void*, void*),... Notice the first 'splat' adjacent to the parameter's datatype. Notice the second 'splat' adjacent to the token compare... Imagine the improved consistency if the "splat-space" were "space-splat" in ALL instances where a 'splat' is required. It's optional (when it's correct), but I recommend using "space-splat" always. (A variable or a returned value will be, first-and-foremost, a pointer. What that pointer points to - the datatype - is secondary...)

There's no apparent thought been given, yet, to multi-threaded code considerations. Everything in its time.

If the OP is thinking of getting-into coding embedded systems, it's worth noting that dynamic memory allocation is strongly NOT recommended. Just something to think about before dreaming of writing the ultimate library LL implementation.

("(Balanced) Binary Trees" and "Tries" are lurking just over the horizon, too...)