NAME
clibx_ll - generic singly-linked list implementation
SYNOPSIS
#include \<clibx/ll.h>
DESCRIPTION
clibx_ll is a generic, type-agnostic singly-linked list implementation. It uses void pointers to store arbitrary data of any type, making it suitable for storing integers, strings, structs, or any other data type.
The list maintains both head and tail pointers for efficient O(1) append operations.
DATA TYPES
clibx_ll_node
: A single node in the linked list.
typedef struct clibx_ll_node {
void *data; /* Pointer to user data */
struct clibx_ll_node *next; /* Next node in list */
} clibx_ll_node;
clibx_ll
: The linked list container.
typedef struct {
clibx_ll_node *head; /* First node */
clibx_ll_node *tail; /* Last node (for O(1) append) */
size_t count; /* Number of elements */
} clibx_ll;
FUNCTIONS
Initialization
clibx_ll clibx_ll_init(void)
: Initialize an empty linked list. Time complexity: O(1). Space complexity: O(1).
Insertion
void clibx_ll_push_back(clibx_ll *list, void *data)
: Append data to the end of the list. Time complexity: O(1). Space complexity: O(1).
void clibx_ll_push_front(clibx_ll *list, void *data)
: Prepend data to the beginning of the list. Time complexity: O(1). Space complexity: O(1).
Access
void* clibx_ll_get(clibx_ll *list, size_t index)
: Get data at a specific 0-based index. Returns NULL if index is out of bounds. Time complexity: O(n). Space complexity: O(1).
void* clibx_ll_front(clibx_ll *list)
: Get data at the front of the list. Returns NULL if list is empty. Time complexity: O(1). Space complexity: O(1).
void* clibx_ll_back(clibx_ll *list)
: Get data at the back of the list. Returns NULL if list is empty. Time complexity: O(1). Space complexity: O(1).
Search
int clibx_ll_contains(clibx_ll *list, void *value, int (*cmp)(void*, void*))
: Check if a value exists using the provided comparison function. The comparison function should return non-zero if values are equal, 0 otherwise. Time complexity: O(n). Space complexity: O(1).
Removal
void* clibx_ll_pop_front(clibx_ll *list)
: Remove and return the first element. Caller is responsible for freeing the returned data. Time complexity: O(1). Space complexity: O(1).
void* clibx_ll_remove_at(clibx_ll *list, size_t index)
: Remove and return the element at the specified index. Caller is responsible for freeing the returned data. Returns NULL if index is out of bounds. Time complexity: O(n). Space complexity: O(1).
void clibx_ll_remove_all(clibx_ll *list, int free_data)
: Remove all nodes from the list. If free_data is non-zero, also calls free() on each node\'s data. Time complexity: O(n). Space complexity: O(1).
Query
int clibx_ll_is_empty(clibx_ll *list)
: Check if the list is empty. Time complexity: O(1). Space complexity: O(1).
size_t clibx_ll_size(clibx_ll *list)
: Get the number of elements in the list. Time complexity: O(1). Space complexity: O(1).
Memory Management
void clibx_ll_free(clibx_ll *list, int free_data)
: Free all memory used by the list. If free_data is non-zero, also calls free() on each node\'s data. Time complexity: O(n). Space complexity: O(1).
MACROS
CLIBX_LL_FOR_EACH(node, list)
: Iterate over all nodes in the list.
clibx_ll_node *node;
CLIBX_LL_FOR_EACH(node, &list) {
printf("%d\n", *(int*)node->data);
}
EXAMPLE
#include <clibx/ll.h>
int main(void) {
clibx_ll list = clibx_ll_init();
/* Add integers */
int *a = NEW(int); *a = 10;
int *b = NEW(int); *b = 20;
int *c = NEW(int); *c = 30;
clibx_ll_push_back(&list, a);
clibx_ll_push_back(&list, b);
clibx_ll_push_back(&list, c);
/* Access front/back */
printf("Front: %d\n", *(int*)clibx_ll_front(&list)); /* 10 */
printf("Back: %d\n", *(int*)clibx_ll_back(&list)); /* 30 */
/* Iterate */
clibx_ll_node *node;
CLIBX_LL_FOR_EACH(node, &list) {
printf("Value: %d\n", *(int*)node->data);
}
/* Pop and remove */
void *removed = clibx_ll_pop_front(&list);
if (removed) {
printf("Removed: %d\n", *(int*)removed);
free(removed);
}
/* Clean up */
clibx_ll_free(&list, 1); /* Free list and all data */
return 0;
}
ITERATING WITH CUSTOM TYPES
typedef struct {
int id;
char name[50];
} Person;
int main(void) {
clibx_ll people = clibx_ll_init();
Person *alice = NEW(Person);
alice->id = 1;
strcpy(alice->name, "Alice");
clibx_ll_push_back(&people, alice);
/* Iterate */
clibx_ll_node *node;
CLIBX_LL_FOR_EACH(node, &people) {
Person *p = (Person*)node->data;
printf("ID: %d, Name: %s\n", p->id, p->name);
}
clibx_ll_free(&people, 1);
return 0;
}
SEARCHING WITH CUSTOM COMPARATORS
int int_cmp(void *a, void *b) {
return *(int*)a == *(int*)b;
}
int main(void) {
clibx_ll list = clibx_ll_init();
int *val1 = NEW(int); *val1 = 42;
int *val2 = NEW(int); *val2 = 99;
clibx_ll_push_back(&list, val1);
clibx_ll_push_back(&list, val2);
int target = 42;
if (clibx_ll_contains(&list, &target, int_cmp)) {
printf("Found 42 in list\n");
}
clibx_ll_free(&list, 1);
return 0;
}
TIME COMPLEXITY
TABLE
NOTES
Memory Management
: The list does not automatically manage the lifetime of user data. Callers must ensure proper cleanup:
- Use clibx_ll_free(&list, 1) to free both nodes and data
- Use clibx_ll_free(&list, 0) to free only nodes (data freed
separately)
- When removing elements with clibx_ll_pop_front() or
clibx_ll_remove_at(), the caller becomes responsible for freeing
the returned data
Type Safety
: Since the list uses void pointers, there is no compile-time type checking. Ensure consistent data types are stored and retrieved from a single list. Cast carefully when retrieving data.
Generic Usage
: The list works with any data type: primitives, strings, structs, or pointers. Simply cast to the appropriate type when accessing data.
SEE ALSO
clibx(3), clibx_print(3)
AUTHOR
David Balishyan \<davidbalishyan12@gmail.com>
BUGS
Report bugs to the project repository.
LICENSE
See LICENSE file in the project root.