Generic Linked List Library

Introduction

This page describes the Generic Linked List library available for Applications.

The lib_lists provides two types of linked list implementations:

• Forward lists (flist_*): Singly-linked lists with minimal memory overhead
• Doubly-linked lists (list_*): Bidirectional lists with previous pointers

Both implementations share a common architecture with generic node structures that can be embedded in any data structure. This design is based on the app-ethereum implementation and is optimized for embedded systems like Ledger devices.

Node Structures

Forward List Node (Singly-Linked)

The forward list node contains only a next pointer:

typedef struct flist_node_t {
    struct flist_node_t *next;
} flist_node_t;

Usage:** Embed flist_node_t as the first member of your structure:

typedef struct my_data_s {
    flist_node_t node;  // Must be first member
    int value;
    char name[32];
} my_data_t;
 
flist_node_t *my_flist = NULL;  // Empty forward list

Memory overhead:** 4-8 bytes per node (one pointer)

Doubly-Linked List Node

The doubly-linked node contains both next and previous pointers:

typedef struct list_node_t {
    flist_node_t        _list;  // Contains next pointer
    struct list_node_t *prev;   // Previous pointer
} list_node_t;

Usage:** Embed list_node_t as the first member of your structure:

typedef struct my_data_s {
    list_node_t node;  // Must be first member
    int value;
    char name[32];
} my_data_t;
 
list_node_t *my_list = NULL;  // Empty doubly-linked list

Memory overhead:** 8-16 bytes per node (two pointers)

Choosing Between Forward Lists and Doubly-Linked Lists

Feature	Forward List (flist)	Doubly-Linked (list)
Memory per node	4-8 bytes	8-16 bytes
Insert/remove at front	O(1)	O(1)
Insert/remove at back	O(n)	O(1) ⚡
Insert after node	O(1)	O(1)
Insert before node	Not available	O(1) ⚡
Backward traversal	No	Yes ⚡
Reverse operation	O(n)	O(n)

Best practice:** Use forward lists when memory is critical and you don't need backward traversal or frequent tail operations. Use doubly-linked lists when you need bidirectional access or O(1) tail operations.

Understanding Time Complexity

The documentation uses Big O notation to describe algorithm performance:

• O(1) - Constant time: The operation takes the same time regardless of list size
  • Example: Adding to the front of the list always requires the same steps
  • Performance: Excellent for embedded systems ✓
• O(n) - Linear time: Time increases proportionally with the number of elements (n)
  • Example: Finding the last element requires traversing all n elements
  • Performance: Acceptable for small to medium lists

• O(n²) - Quadratic time: Time increases with the square of the number of elements

  • Example: Bubble sort compares elements multiple times
  • Performance: Avoid for large lists in embedded systems

  Concrete examples:**

  List Size	O(1)	O(n)	O(n²)
  10 items	1 step	10 steps	100 steps
  100 items	1 step	100 steps	10,000 steps
  1000 items	1 step	1,000 steps	1,000,000 steps

  Best practice:** Always prefer O(1) operations when possible for optimal performance.

Basic Operations

All operations are available for both forward lists and doubly-linked lists with similar APIs:

• Forward list functions: flist_*
• Doubly-linked list functions: list_*

All mutating functions return bool to indicate success or failure.

Insertion Operations

Push Front** - Add a node at the beginning (O(1) for both types):

// Forward list example
my_data_t *data = malloc(sizeof(my_data_t));
data->node.next = NULL;  // Must be NULL before insertion
data->value = 42;
 
if (flist_push_front(&my_flist, &data->node)) {
    // Successfully inserted
}
 
// Doubly-linked list example
my_data_t *data2 = malloc(sizeof(my_data_t));
data2->node._list.next = NULL;
data2->node.prev = NULL;  // Both pointers must be NULL
data2->value = 43;
 
if (list_push_front(&my_list, &data2->node)) {
    // Successfully inserted
}

Push Back** - Add a node at the end:

• Forward list: O(n) - must traverse entire list
• Doubly-linked: O(1) - direct access via prev pointer ⚡

// Forward list: O(n)
if (flist_push_back(&my_flist, &data->node)) {
    // Successfully inserted
}
 
// Doubly-linked: O(1) - faster!
if (list_push_back(&my_list, &data->node)) {
    // Successfully inserted
}

Insert After** - Insert a node after a reference node (O(1) for both):

my_data_t *new_data = malloc(sizeof(my_data_t));
new_data->node._list.next = NULL;
new_data->node.prev = NULL;
 
if (list_insert_after(&my_list, &ref_node, &new_data->node)) {
    // Successfully inserted after ref_node
}

Insert Before** - Insert a node before a reference node:

• Forward list: Not available (requires backward traversal)
• Doubly-linked: O(1) - direct access via prev pointer ⚡

// Only available for doubly-linked lists
my_data_t *new_data = malloc(sizeof(my_data_t));
new_data->node._list.next = NULL;
new_data->node.prev = NULL;
 
if (list_insert_before(&my_list, &ref_node, &new_data->node)) {
    // Successfully inserted before ref_node
}

Removal Operations

All removal functions return bool to indicate success or failure (except remove_if). They accept an optional deletion callback to clean up node data.

Pop Front** - Remove the first node (O(1) for both):

void my_delete_func(flist_node_t *node) {
    my_data_t *data = (my_data_t *)node;
    // Clean up data if needed
    free(data);
}
 
// Forward list
if (flist_pop_front(&my_flist, my_delete_func)) {
    // First node was removed and freed
}
 
// Doubly-linked list
if (list_pop_front(&my_list, (f_list_node_del)my_delete_func)) {
    // First node was removed and freed
}

Pop Back** - Remove the last node:

• Forward list: O(n) - must find second-to-last node
• Doubly-linked: O(1) - direct access via prev pointer ⚡

// Forward list: O(n)
if (flist_pop_back(&my_flist, my_delete_func)) {
    // Last node was removed
}
 
// Doubly-linked: O(1) - faster!
if (list_pop_back(&my_list, (f_list_node_del)my_delete_func)) {
    // Last node was removed
}

Remove** - Remove a specific node (O(n) for forward, O(1) for doubly-linked):

// Forward list: O(n) - must find previous node
if (flist_remove(&my_flist, &node_to_remove, my_delete_func)) {
    // Node was found and removed
}
 
// Doubly-linked: O(1) - direct access via prev pointer ⚡
if (list_remove(&my_list, &node_to_remove, (f_list_node_del)my_delete_func)) {
    // Node was removed instantly
}

Remove If** - Remove all nodes matching a predicate (O(n) for both):

bool is_negative(const flist_node_t *node) {
    const my_data_t *data = (const my_data_t *)node;
    return data->value < 0;
}
 
// Returns the number of removed nodes
size_t removed = flist_remove_if(&my_flist, is_negative, my_delete_func);
printf("Removed %zu negative values\n", removed);

Clear** - Remove all nodes (O(n) for both):

if (flist_clear(&my_flist, my_delete_func)) {
    // All nodes were removed and list is now empty
}

Utility Operations

Get Size** - Count the number of nodes (O(n) for both):

size_t count = flist_size(&my_flist);
size_t count2 = list_size(&my_list);

Check Empty** - Test if list is empty (O(1) for both):

if (flist_empty(&my_flist)) {
    printf("Forward list is empty\n");
}
 
if (list_empty(&my_list)) {
    printf("Doubly-linked list is empty\n");
}

Sort** - Sort the list using a comparison function (O(n²) for both):

bool my_compare_func(const flist_node_t *a, const flist_node_t *b) {
    my_data_t *data_a = (my_data_t *)a;
    my_data_t *data_b = (my_data_t *)b;
    return data_a->value <= data_b->value;  // true if in correct order
}
 
// Forward list
if (flist_sort(&my_flist, my_compare_func)) {
    // List is now sorted
}
 
// Doubly-linked list
if (list_sort(&my_list, my_compare_func)) {
    // List is now sorted
}

Unique** - Remove consecutive duplicate nodes (O(n) for both):

bool are_equal(const flist_node_t *a, const flist_node_t *b) {
    const my_data_t *data_a = (const my_data_t *)a;
    const my_data_t *data_b = (const my_data_t *)b;
    return data_a->value == data_b->value;
}
 
// Returns the number of removed duplicates
size_t removed = flist_unique(&my_flist, are_equal, my_delete_func);
printf("Removed %zu duplicates\n", removed);

Reverse** - Reverse the order of nodes (O(n) for both):

if (flist_reverse(&my_flist)) {
    // List is now reversed
}
 
if (list_reverse(&my_list)) {
    // List is now reversed
}

List Traversal

Forward List Traversal (Forward Only)

// Forward iteration only
for (flist_node_t *node = my_flist; node != NULL; node = node->next) {
    my_data_t *data = (my_data_t *)node;
    printf("Value: %d\n", data->value);
}

List Traversal

// Forward iteration
for (list_node_t *node = my_list; node != NULL; node = (list_node_t *)node->_list.next) {
    my_data_t *data = (my_data_t *)node;
    printf("Value: %d\n", data->value);
}
 
// Backward iteration - only possible with doubly-linked lists!
list_node_t *tail = my_list;
if (tail != NULL) {
    // Find the tail
    while (tail->_list.next != NULL) {
        tail = (list_node_t *)tail->_list.next;
    }
    // Traverse backward
    for (list_node_t *node = tail; node != NULL; node = node->prev) {
        my_data_t *data = (my_data_t *)node;
        printf("Value: %d\n", data->value);
    }
}

Safety and Error Handling

The library implements several safety checks:

1. NULL pointer checks: All functions validate their parameters
2. Node state validation:
   • Forward list: Insertion functions verify that node->next == NULL
   • Doubly-linked: Insertion functions verify that both node->_list.next and node->prev are NULL
   • This prevents:
     • Creating cycles in the list
     • Accidentally linking nodes from different lists
     • Losing track of existing node chains
3. Return value checking: All mutating operations return bool:
   • true: Operation succeeded
   • false: Invalid parameters or operation failed (e.g., node not found)

4. Counter operations: remove_if, unique, and size return size_t with count information

   Common error scenarios:**

// Forward list error
my_data_t *data = malloc(sizeof(my_data_t));
data->node.next = some_other_node;  // Already linked!
 
if (!flist_push_front(&my_flist, &data->node)) {
    // ERROR: node->next was not NULL
    // This prevents accidentally breaking another list
}
 
// Doubly-linked list error
my_data_t *data2 = malloc(sizeof(my_data_t));
data2->node.prev = some_node;  // Already linked!
 
if (!list_push_front(&my_list, &data2->node)) {
    // ERROR: node->prev was not NULL
}

Best Practices

1. Always initialize node pointers to NULL before insertion:

   // Forward list
   my_data_t *data = malloc(sizeof(my_data_t));
   data->node.next = NULL;  // Critical!
    
   // Doubly-linked list
   my_data_t *data2 = malloc(sizeof(my_data_t));
   data2->node._list.next = NULL;  // Critical!
   data2->node.prev = NULL;        // Critical!

2. Check return values to detect errors:

   if (!flist_push_front(&my_flist, &data->node)) {
       // Handle error
   }

3. Use the deletion callback to prevent memory leaks:

   flist_clear(&my_flist, my_delete_func);

4. Choose the right list type:
   • Use flist (forward list) for minimal memory usage
   • Use list (doubly-linked) for bidirectional access or frequent tail operations
5. Prefer front operations when order doesn't matter:
   • flist_push_front is O(1)
   • list_push_front is O(1)
   • Both are faster than push_back for forward lists
6. Don't reuse nodes across multiple lists without proper unlinking

Complete Examples

Forward List Basic Usage

#include "lists.h"
#include <stdlib.h>
#include <stdio.h>
 
typedef struct person_s {
    flist_node_t node;
    char name[32];
    int age;
} person_t;
 
void delete_person(flist_node_t *node) {
    person_t *person = (person_t *)node;
    printf("Deleting: %s\n", person->name);
    free(person);
}
 
int main(void) {
    flist_node_t *people = NULL;
 
    // Add some people
    person_t *alice = malloc(sizeof(person_t));
    alice->node.next = NULL;
    strcpy(alice->name, "Alice");
    alice->age = 30;
    flist_push_front(&people, &alice->node);
 
    person_t *bob = malloc(sizeof(person_t));
    bob->node.next = NULL;
    strcpy(bob->name, "Bob");
    bob->age = 25;
    flist_push_back(&people, &bob->node);
 
    // Print all people
    for (flist_node_t *node = people; node != NULL; node = node->next) {
        person_t *p = (person_t *)node;
        printf("%s is %d years old\n", p->name, p->age);
    }
 
    // Clean up
    flist_clear(&people, delete_person);
 
    return 0;
}

Doubly-Linked List with Backward Traversal

#include "lists.h"
#include <stdlib.h>
#include <stdio.h>
 
typedef struct person_s {
    list_node_t node;
    char name[32];
    int age;
} person_t;
 
void delete_person_dl(flist_node_t *node) {
    person_t *person = (person_t *)node;
    printf("Deleting: %s\n", person->name);
    free(person);
}
 
int main(void) {
    list_node_t *people = NULL;
 
    // Add people (O(1) for both front and back!)
    person_t *alice = malloc(sizeof(person_t));
    alice->node._list.next = NULL;
    alice->node.prev = NULL;
    strcpy(alice->name, "Alice");
    alice->age = 30;
    list_push_back(&people, &alice->node);  // O(1) - fast!
 
    person_t *bob = malloc(sizeof(person_t));
    bob->node._list.next = NULL;
    bob->node.prev = NULL;
    strcpy(bob->name, "Bob");
    bob->age = 25;
    list_push_back(&people, &bob->node);  // O(1) - fast!
 
    // Forward traversal
    printf("Forward:\n");
    for (list_node_t *node = people; node != NULL; node = (list_node_t *)node->_list.next) {
        person_t *p = (person_t *)node;
        printf("  %s is %d years old\n", p->name, p->age);
    }
 
    // Backward traversal - only possible with doubly-linked!
    printf("Backward:\n");
    list_node_t *tail = people;
    while (tail && tail->_list.next) {
        tail = (list_node_t *)tail->_list.next;
    }
    for (list_node_t *node = tail; node != NULL; node = node->prev) {
        person_t *p = (person_t *)node;
        printf("  %s is %d years old\n", p->name, p->age);
    }
 
    // Clean up
    list_clear(&people, delete_person_dl);
 
    return 0;
}

Sorting Example

bool compare_age(const flist_node_t *a, const flist_node_t *b) {
    const person_t *pa = (const person_t *)a;
    const person_t *pb = (const person_t *)b;
    return pa->age <= pb->age;  // Sort by age ascending
}
 
// Sort forward list
if (flist_sort(&people, compare_age)) {
    printf("Forward list sorted by age\n");
}
 
// Sort doubly-linked list
if (list_sort(&people_dl, compare_age)) {
    printf("Doubly-linked list sorted by age\n");
}

Advanced: Remove Duplicates and Reverse

// Remove consecutive duplicates after sorting
bool are_equal(const flist_node_t *a, const flist_node_t *b) {
    const person_t *pa = (const person_t *)a;
    const person_t *pb = (const person_t *)b;
    return pa->age == pb->age;
}
 
flist_sort(&people, compare_age);
size_t removed = flist_unique(&people, are_equal, delete_person);
printf("Removed %zu duplicates\n", removed);
 
// Reverse the list
if (flist_reverse(&people)) {
    printf("List reversed (now descending order)\n");
}
 
// Remove all minors
bool is_minor(const flist_node_t *node) {
    const person_t *p = (const person_t *)node;
    return p->age < 18;
}
 
size_t removed_minors = flist_remove_if(&people, is_minor, delete_person);
printf("Removed %zu minors\n", removed_minors);

Performance Characteristics

Forward List Performance

Operation	Time Complexity	Notes
flist_push_front	O(1)	Constant time
flist_pop_front	O(1)	Constant time
flist_push_back	O(n)	Must traverse entire list
flist_pop_back	O(n)	Must find second-to-last node
flist_insert_after	O(1)	Constant time if reference known
flist_remove	O(n)	Must find previous node
flist_remove_if	O(n)	Traverses list once
flist_clear	O(n)	Must visit all nodes
flist_size	O(n)	Must count all nodes
flist_empty	O(1)	Just checks if head is NULL
flist_sort	O(n²)	Bubble sort implementation
flist_unique	O(n)	Single pass after sorting
flist_reverse	O(n)	Single pass, reverses pointers

Memory overhead:** 4-8 bytes per node (one pointer)

Performance Characteristics

Operation	Time Complexity	Notes
list_push_front	O(1) ⚡	Constant time
list_pop_front	O(1) ⚡	Constant time
list_push_back	O(1) ⚡	Direct access via prev!
list_pop_back	O(1) ⚡	Direct access via prev!
list_insert_before	O(1) ⚡	Direct access via prev!
list_insert_after	O(1) ⚡	Constant time
list_remove	O(1) ⚡	Direct access via prev!
list_remove_if	O(n)	Traverses list once
list_clear	O(n)	Must visit all nodes
list_size	O(n)	Must count all nodes
list_empty	O(1) ⚡	Just checks if head is NULL
list_sort	O(n²)	Bubble sort implementation
list_unique	O(n)	Single pass after sorting
list_reverse	O(n)	Single pass, swaps pointers

Memory overhead:** 8-16 bytes per node (two pointers)

Performance Comparison

When to use forward lists (flist):**

• Memory is critical (saves 4-8 bytes per node)
• Only need forward traversal
• Rarely need tail operations

• Example: Stack-like data structures, one-directional iteration

  When to use doubly-linked lists (list):**

• Need frequent tail operations (O(1) vs O(n) ⚡)
• Need to insert/remove at known positions efficiently
• Need bidirectional traversal
• Memory overhead is acceptable
• Example: LRU caches, undo/redo systems, navigation histories

Limitations

Forward List Limitations

1. No backward traversal: Cannot iterate backward through the list.
2. No tail pointer: push_back and pop_back are O(n). For frequent tail operations, use doubly-linked lists instead.
3. No insert_before: Cannot insert before a node without traversing from head. Use doubly-linked lists for O(1) insert_before.
4. Bubble sort: The sort implementation is O(n²). For large lists, consider using an external sorting algorithm.

Limitations

1. Memory overhead: Uses twice the memory per node compared to forward lists (two pointers instead of one).
2. Bubble sort: The sort implementation is O(n²). For large lists, consider using an external sorting algorithm.
3. No tail caching: While tail operations are O(1), finding the tail initially requires traversal. For repeated tail access, cache the tail pointer in your application.

Common Limitations (Both Types)

1. No built-in search: Searching requires manual traversal. Implement application-specific search functions.
2. No thread safety: The library is not thread-safe. Implement external synchronization if needed.
3. No automatic memory management: Applications must manage node allocation and provide deletion callbacks.

When to Use Alternatives

Consider alternatives if you need:

Instead of forward lists (flist):**

• Frequent tail operations: Use doubly-linked list (list) for O(1) tail access ⚡
• Bidirectional traversal: Use doubly-linked list (list)

• Insert before operation: Use doubly-linked list (list) for O(1) insert_before ⚡

  Instead of doubly-linked lists (list):**

• Minimal memory usage: Use forward list (flist) to save 4-8 bytes per node

• Simple one-directional access: Use forward list (flist) for simplicity

  Instead of any linked list:**

• Fast random access: Use array-based structures (indexing is O(1) vs O(n))
• Efficient sorting of large datasets: Pre-sort data before insertion or use array + qsort
• Memory profiling: Use lib_alloc for allocation tracking and debugging

• Fixed-size collections: Use static arrays for better cache locality

  Hybrid approaches:**

• Maintain a separate tail pointer with forward lists for O(1) tail access
• Use ring buffers for fixed-size FIFO/LIFO operations
• Combine with hash tables for O(1) lookup + ordered iteration