How Do I Build Generic Data Structures with Pointers and Functions?

After this lesson, you will be able to:

• Describe the four-callback pattern for generic containers (build, print, compare, clean)
• Implement a generic linked list node using void *data
• Write a free_list function that saves next before freeing each node
• Write type-specific callback functions that cast void * to the correct type

The Big Idea

You have function pointers (parameterize behavior) and void pointers (parameterize type). Combine them, and you can build a container that stores any type and operates on it through callbacks — without the container knowing the type.

This is C’s version of Java generics: ArrayList<T> built from raw pointers and function addresses.

The Generic Container Pattern

Four Callbacks

A generic container needs four operations, each provided by the caller:

The container calls these functions without knowing the type. Each callback casts the void * to the real type internally.

The Trick: Think of the generic container as a machine with four plugs. Different data types provide different plug implementations: ints plug in print_int, compare_int, etc. Strings plug in print_string, compare_string. Same machine, different plugs.

Linked List Node

A generic linked list stores void * data:

typedef struct node
{
    void *data;
    struct node *next;
} Node;

Building the List

Node *prepend(Node *head, void *data)
{
    Node *new_node = calloc(1, sizeof(Node));
    if (new_node == NULL) return head;

    new_node->data = data;
    new_node->next = head;
    return new_node;
}

Traversal with Callbacks

void print_list(Node *head, void (*print_fn)(void *))
{
    Node *current = head;
    while (current != NULL)
    {
        print_fn(current->data);
        current = current->next;
    }
}

Freeing the List

void free_list(Node *head, void (*clean_fn)(void *))
{
    Node *current = head;
    while (current != NULL)
    {
        Node *temp = current->next;
        if (clean_fn != NULL)
        {
            clean_fn(current->data);    // Free the data
        }
        free(current);                   // Free the node
        current = temp;
    }
}

Common Pitfall: When freeing a linked list, save current->next before freeing current. If you free the node first, you lose the next pointer — you can’t continue traversal. Use a temp variable.

Type-Specific Callbacks

For integers:

void print_int(void *data)
{
    int *p = (int *)data;
    printf("%d\n", *p);
}

int compare_ints(void *a, void *b)
{
    int *ia = (int *)a;
    int *ib = (int *)b;
    return *ia - *ib;
}

void clean_int(void *data)
{
    free(data);
}

For a Word struct with a dynamically allocated string:

typedef struct
{
    char *letters;
    int length;
} Word;

void print_word(void *data)
{
    Word *w = (Word *)data;
    printf("%s (%d chars)\n", w->letters, w->length);
}

void clean_word(void *data)
{
    Word *w = (Word *)data;
    free(w->letters);    // Free string first
    free(w);             // Then free struct
}

Key Insight: Each callback follows the same pattern: check for NULL, cast void * to the real type, do the work. The generic container never knows what type it holds — it just calls whatever callbacks the user provides.

From Java: This is equivalent to Java’s ArrayList<T> with custom Comparator, toString(), and close() methods. Java achieves this with interfaces and generics (compile-time type safety). C achieves it with void * and function pointers (no type safety — you must get it right yourself).

Step 1: Container calls print_fn(current->data)
        print_fn is a void (*)(void *)
        current->data is a void * pointing to a Word struct

Step 2: print_fn resolves to print_word (the callback we plugged in)

Step 3: Inside print_word:
        void print_word(void *data)    ← data is the void * from step 1
        {
            Word *w = (Word *)data;    ← cast to real type
            printf("%s (%d chars)\n", w->letters, w->length);
        }

Step 4: Memory layout being accessed:
        ┌──────────────┐
        │ Node         │
        │  data ───────────→ ┌──────────┐
        │  next ──→ ...│     │ Word     │
        └──────────────┘     │  letters ───→ "hello\0"
                             │  length = 5│
                             └──────────┘

Linked Lists vs. Arrays

Big Picture: Generic containers are how C libraries achieve reusability without templates or generics. The Linux kernel’s linked list implementation, SQLite’s B-tree, and the C standard library’s qsort all use this same pattern: void pointers for data, function pointers for operations. You’ve now built the same machinery that powers real-world systems software.

What’s Next

You’ve built the generic container pattern from scratch. In the next lesson, you’ll see how this applies to Lab 8 — implementing type-specific callbacks for a generic array that stores Word structs.