Generic Singly Linked List with Tail Pointer in C

A clean, robust implementation of a generic singly linked list written in C, featuring a tail pointer for optimized append operations and support for arbitrary data types (void*).

This project was created to master low-level programming concepts, manual memory management, pointer manipulation, and clean API design in C.

Note

This is an educational implementation. It is not production-ready and was intentionally written to learn low-level programming concepts rather than to provide a complete container library.

---

Key Features & Enhancements

• Generic Data Support: Uses void* pointers to store any type of data (integers, strings, custom structs, etc.).
• O(1) Append Operations: Maintains a tail pointer to ensure push_back runs in constant time.
• Memory Safety Callbacks: Accept a pointer to a custom cleanup function (free_func) to safely deallocate complex user data inside nodes.
• Safe Traversal & Predicates: Includes advanced elements like list_find, list_delete_elem, and custom printing via callbacks.
• Opaque Types: Hides the inner structures of Node and List from the user to enforce strict encapsulation.
• Error Handling: Functions return explicit error status codes (e.g., SUCCESS, ERR_LIST_IS_NULL, VALUE_NOT_FOUND).
• Doxygen-Style Documentation: Ready for automated documentation generation.

---

Project Structure

.
├── list.h      # Public API definitions, error codes, and Doxygen documentation
├── list.c      # Core list implementation logic
└── main.c      # Complete example usage and test scenarios

---

Implemented API

List* list_create();
void list_destroy(List* list, void (*free_func)(void*));

int list_push_front(List* list, void* value);
int list_push_back(List* list, void* value);

int list_pop_front(List* list, void (*free_func)(void*));
int list_pop_back(List* list, void (*free_func)(void*));

Node* list_find(List* list, const void* value, int (*cmp)(const void*, const void*));
int list_delete_elem(List* list, const void* value, int (*cmp)(const void*, const void*), void (*free_func)(void*));

size_t list_get_size(List* list);
int list_is_empty(List* list);
void* node_get_value(Node* node);

void list_print(List* list, void (*func_print)(const void*));

---

Time Complexity

Operation	Complexity	Description
list_push_front	O(1)	Instant insertion at the head
list_push_back	O(1)	Instant insertion using the cached tail pointer
list_pop_front	O(1)	Instant removal from the head
list_pop_back	O(n)	Requires full traversal to locate the penultimate node
list_find	O(n)	Linear search using a user-provided comparison callback
list_delete_elem	O(n)	Searches and removes a specific node from any position
list_get_size	O(1)	Instantly reads cached size property
list_is_empty	O(1)	Quick check if head pointer is NULL
list_destroy	O(n)	Iterates and safely frees all nodes and their contents

---

Learning Goals & Concepts Practiced

• Manual Memory Management: Handling malloc, free, and preventing memory leaks with custom free_func pointers.
• Function Pointers: Implementing callbacks for polymorphism-like behavior in C (printing, comparing, and destroying items).
• Data Invariants: Keeping head, tail, and size always synchronized through multiple edge cases (such as deleting the last remaining node).
• API Design: Writing clean, predictable, and self-documenting code in standard C.

---

Quick Start & Usage Example

Here is a quick look at how to use the list with dynamic string data:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

int compare_strings(const void* a, const void* b) {
    return strcmp((const char*)a, (const char*)b);
}

void print_char(const void* value) {
    printf("\"%s\"", (char*)value);
}

int main() {
    List* my_list = list_create();

    // Add elements (using strdup to allocate strings in the heap)
    list_push_back(my_list, strdup("Banana"));
    list_push_front(my_list, strdup("Apple")); // List becomes: "Apple" -> "Banana"

    // Print the structure
    list_print(my_list, print_char);

    // Remove from the front
    list_pop_front(my_list, free); // "Apple" is freed, "Banana" remains

    // Delete a specific element
    list_delete_elem(my_list, "Banana", compare_strings, free);

    // Completely destroy the list and prevent memory leaks
    list_destroy(my_list, free);
    return 0;
}

To compile and run the project:

make example-run

---

Future Improvements

• Add a flexible iterator interface (list_begin, list_next) for easier loop traversals.
• Migrate to a doubly linked list structure to boost list_pop_back efficiency from O(n) to O(1).
• Add generic unit test suits using a C testing framework.
• Introduce CMake configuration support.

---

License

This project is available under the MIT License.