Generic Linked List in C

Last Updated on November 18, 2022 by Prepbytes

Introduction

In this article, we will discuss in detail about generic linked list in C. Data Structures are very important in the interview for any IT firm. Practicing more and more on data structures will help you to get placed in your dream company. Now, Let’s discuss 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 c generic linked list.

Approach For Generic Linked List In C

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 arguments 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 For Generic Linked List In C

• 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 For Generic Linked List In C:

#include<stdio.h>
#include<stdlib.h>

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 For Generic Linked List In C

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 on LinkedList. I would highly recommend you practice some problems on a linked list from Linked List.

FAQs Related To Generic Linked List In C

1. What is a generic linked list?

A linked list generated from the generic node is known as a generic linked list which can store any type of data.

2. Why do We Use a linked list?

Linked lists are often used because of their efficient insertion and deletion. They can be used to implement stacks, queues, and other abstract data types.

3. Where linked list is stored?

The Linked List is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. It is implemented on the heap memory rather than the stack memory.