Generic Linked List

A linked list is a fundamental data structure in computer science used to organize elements of data in a specific order. When working in a lower-level language like C, you often find yourself needing a linked list that can store any type of data. That's where a generic linked list comes in. A generic linked list allows any data type to be stored in its nodes by using the power of void pointers, rather than binding itself to a specific data type. In this tutorial, we will explore the concept, creation, and manipulation of a generic linked list in C.

Firstly, we need to understand what a Node in a linked list is. A Node is an individual element of a linked list which contains two parts: the data and a pointer to the next Node. In a generic linked list, the data can be of any type. Therefore, we use a void pointer to store data. Here's an example of how a generic Node structure is represented in C:

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

This Node structure has void *data which can point to data of any type and a Node *next pointer which points to the next node in the linked list. The typedef line allows us to refer to this structure by the simpler name Node.

Creating a new Node involves allocating memory for the Node and setting the data and next pointer:

Node* createNode(void *data) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

To add a new Node at the end of the linked list, we traverse the list until the end and then put our new Node at the end:

void addNode(Node **head, void *data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Notice that we're passing the head of the list by address. This allows us to modify the head within the function if the list is empty.

To delete a Node from the linked list, we again need to traverse the list. Once the Node is found, it is removed and the list is linked again:

void deleteNode(Node **head, void *data, int (*cmp)(void*, void*)) {
    Node *temp = *head, *prev;
    if (temp != NULL && cmp(temp->data, data) == 0) {
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && cmp(temp->data, data) != 0) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
    free(temp);
}

Here, cmp is a function pointer to a function which can compare the data we are storing. As our list is generic, we do not know beforehand how to compare data of this type, hence we require the user to provide a compare function.

These are the basics of a generic linked list in C. You can modify and extend this code to suit your needs, such as implementing other operations (e.g., inserting a node at a particular position, reversing the list, concatenating two lists, etc).
Hopefully, this guide has helped you understand the creation and use of a generic linked list in C. It’s a powerful tool to have in your toolbox when coding in such a lower-level language.