Generic Data Structures

Quick check before you start: Can you write a comparator for qsort and cast a void* to a typed pointer? If yes, you are ready for this lesson. If not, review Lesson 9a and Lesson 9b.

Practice this topic: Generic Containers skill drill

After this lesson, you will be able to:

• Explain the four-callback pattern for generic data structures
• Build a generic linked list that stores void* data
• Write build, print, compare, and clean callbacks for a specific type
• Describe what the clean callback is responsible for

The Four-Callback Pattern

In Java, generics and inheritance handle type-agnostic containers. In C, we use void* for data and function pointers for behavior. A generic container needs four callbacks:

The container stores void* and calls these function pointers whenever it needs to interact with the data. The container never knows the actual type.

A Generic Linked List Node

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

The node holds a void*. It could point to an int, a char*, a Student, or anything else. The node does not care.

The Callback Typedefs

typedef void* (*BuildFunc)(const void *data);
typedef void  (*PrintFunc)(const void *data);
typedef int   (*CompareFunc)(const void *a, const void *b);
typedef void  (*CleanFunc)(void *data);

Each typedef defines a function pointer type. Functions that operate on the list accept these as parameters.

Adding to the List

Node* add_front(Node *head, const void *data, BuildFunc build) {
    Node *new_node = calloc(1, sizeof(Node));
    if (new_node == NULL) { return head; }

    new_node->data = build(data);  // copy the data
    new_node->next = head;
    return new_node;
}

The build callback creates a deep copy of the data. The list owns the copy. The caller can modify or free the original without affecting the list.

Printing the List

void print_list(const Node *head, PrintFunc print) {
    const Node *cur = head;
    while (cur != NULL) {
        print(cur->data);
        cur = cur->next;
    }
}

The list traverses nodes. The print callback knows how to display the actual type.

The Clean Callback

The clean callback frees whatever the build callback allocated. This is critical. The list does not know what build did — maybe it allocated a string, maybe a struct with nested allocations. Only clean knows how to undo it.

void destroy_list(Node *head, CleanFunc clean) {
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        clean(cur->data);   // free the data
        free(cur);           // free the node
        cur = next;
    }
}

Without clean, the list can free nodes but not the data inside them — every element leaks.

Example: A List of Strings

void* build_string(const void *data) {
    const char *src = (const char*)data;
    char *copy = calloc(strlen(src) + 1, sizeof(char));
    if (copy == NULL) { return NULL; }
    strcpy(copy, src);
    return copy;
}

void print_string(const void *data) {
    printf("%s\n", (const char*)data);
}

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

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

Four functions. One per callback. Now the generic list can store strings:

Node *list = NULL;
list = add_front(list, "hello", build_string);
list = add_front(list, "world", build_string);
print_list(list, print_string);
destroy_list(list, clean_string);

Swap in different callbacks and the same list stores integers, structs, or anything else.

What Comes Next

You can build generic containers in C. Next week shifts from data structures to systems programming — you will learn how Unix creates new processes with fork and exec.

Next: Processes: fork & exec