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.
nextpointer. In C, you're still going to need these functions to inline for performance not to suck even more than linked lists already do, so you still need a copy of the code in every project that uses them, or in headers \$\endgroup\$LinkedList* list, int (*compare)(void*, void*),...Notice the first 'splat' adjacent to the return type. 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 is, first-and-foremost, a pointer. What it points to - the datatype - is secondary...) Just free advice... \$\endgroup\$linkedList_free()from the implementation file, and that makes it hard for reviewers to fully test the code using Valgrind or similar. \$\endgroup\$