Generic Linked List in C

What are generic linked lists?

Generic linked lists are implementations of linked lists which can store data of any data type.

For Example:

The above two linked lists are having different types of data. The first one stores integer whereas the second one stores float. To implement the above mentioned linked lists generally, we would define two different nodes individually for both the linked lists.

But here we are going to look at a new concept called generic linked list, through which using a more general definition of a node we can implement both the linked list. These two linked lists would be created using generic nodes hence the name generic linked list.

In this article, we are going to discuss how to implement such a data structure in the C programming language.

Approach

Let’s look at the structure of a node in a singly linked list:

struct Node {
    int data;
    Node* next;
};

It can store two values:

  • the data
  • the pointer to the next node.

According to the definition of a generic linked list, it should be able to store data of any type.

It can be implemented using template in C++. But in a language like C, there is no support for generics. So how to tackle this limitation?

We have something called a ‘void pointer’ in C. The void pointer can store the address of any data type. It will allow the program to store the address of any data type as per there the user requirements and hence can be used to implement a generic linked list in C.
We can now change the structure of the node as:

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

So, now we have something called void pointer in our node using which we can create a generic linked list in C.

Now let us look at the implementation of two functions push_front() and printIt() on our generic linked list.

push_front()

push_front() function will take 'x' as one of its argument and will add this element ‘x’ at the beginning of the linked list.

Now, how to implement such a function for the generic linked list?
This function will require 2 information about the data being added:

  • size of new data
  • the data

Since the size of data is not predefined, we need to pass the data as a void pointer and also provide its size.

Algorithm

  • Allocate memory for new_node.
  • Allocate memory for the value of new_node using the size provided.
  • Set the next of this new_node to point to the current head.
  • Copy the new data 'x', to the new_node’s value byte by byte.
  • Change the head pointer to point to new_node.

printIt()

printIt() function will print the contents of the linked list.

To print the contents of a linked list, this function will require the pointer to the head of the linked list, along with the suitable function to print according to the type of data stored in it. For that, we have defined 2 helper functions to print integer and float type data. We can pass these functions to the printIt() function as a void pointer.

Code Implementation


#include
#include

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

// function to add a new node in the
// beginning of the linked list.
void push_front(struct Node** head, void *x, size_t x_size){
    
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    new_node->data  = malloc(x_size);
    new_node->next = (*head);
        
    // here we are copying the data x to new node created
    for(int i=0; i < x_size; i++){
        *(char *)(new_node->data + i) = *(char *)(x + i);
    }

    (*head) = new_node;
}

// function to print the linked list
void printIt(struct Node *node, void (*prt)(void *))
{
    while (node != NULL) {
        (*prt)(node->data);
        node = node->next;
    }
    printf("\n");
}

// function to print integer values
void prInt(void *x){
    printf(" %d", *(int *)x );
}

// function to print float values
void prFlt(void *x){
    printf(" %f", *(float *)x );
}

int main()
{
    struct Node *start = NULL;
 
    // Create and print linked list storing int data
    unsigned int_size = sizeof(int);
    int a[] = {7, 42, 11, 41, 5};
    for (int i=4; i>=0; i--)
       push_front(&start, &a[i], int_size);

    printIt(start, prInt);
 
    // Create and print linked list storing float data
    unsigned float_size = sizeof(float);
    start = NULL;
    float b[] = {1.1, 6.43, 4.2, 3.14, 5.08};
    for (int i=4; i>=0; i--)
       push_front(&start, &b[i], float_size);

    printIt(start, prFlt);
 
    return 0;
}

Output

7 42 11 41 5
1.1 6.43 4.2 3.14 5.08

Time complexity

push_front(): O(1)
printIt(): O(n), where n is the number of nodes in the linked list.

In this article, we went through understanding how a void pointer can be used to store the address of any data type and used it to implement a generic linked list in C. Thinking about problems like these is good for strengthening your grip over LinkedList. I would highly recommend you to practice some problems on a linked list from Linked List.

Previous post How to write C functions that modify the head pointer of a Linked List?
Next post Can we reverse a linked list in less than O(n)?

Leave a Reply

Your email address will not be published. Required fields are marked *