Generic Linked List in C

Malay Gain
Last Updated: May 13, 2022

Introduction

Generic means in general which can be used for all. Similarly, a generic linked list can be used for any type of data members. It is not dependent on the type of data members that the node needs to store. Here we will discuss about the implementation of such a generic linked list.

Necessity

For storing data members of different data types in a linked list, we need to have a specific node for each data type. Such as if we want to store integer type elements in the linked list, then we need to declare a node having integer type data member, and for storing float type elements the node should have float type data member.

 

// node for storing integer type elements in the linked list

struct node{
  
         int data;
         struct  node* next;

}

// node for storing float type elements in the linked list

struct node{
  
         float data;
         struct  node* next;

}

 

So, it seems troublesome to define different nodes for different data types. Here the concept of generic node comes into the picture.

 

A generic node can store any type of data member. A linked list generated from the generic node is known as a generic linked list which can store any type of data. So, now we don’t need to change the definition of the node for a specific type of data member.

 

Let’s see how we can implement the generic linked list.

 

Implementation

According to the definition of a generic linked list, it is able to store any kind of data for the same definition of node. But in the C language, we don’t have such data type which can store any type of data whereas C++ uses template class for such generic implementation. 

 

We will use the concept of void pointer for defining generic node as a void pointer can store the address of any data type.

 

So, the structure of the generic node will be as shown below

 

struct node{
  
         void* data;
         struct  node* next;

}

 

As data member’s type is not predefined, for printing a generic linked list we need to have different functions for different types.

 

Now we will implement a function insert_end( ) to insert a new node in the generic linked list and then print_list() to print the contents of the generic linked list.

 

insert_end( ) 

To insert a value in the generic linked list, we need to pass the size of the data as well as the address of the data as a void pointer as the type of the data member is not predefined.

 

Steps

  • allocate memory for the new node
  • allocating memory for the data
  • storing the data of a new node by copying from one address to another
  • inserting the new node after the end node
  • updating end node pointer

 

node* insert_end(node** end,void* data,int size)
{
	//allocate memeory for new node
	node* new_node=(node*)malloc(sizeof(node));

	// allocating memory for the data
	new_node->data=malloc(size);
	//storing the data of new node by copying from one address to another

	memcpy(new_node->data,data,size);

	//insering the new node after the end node
	(*end)->next=new_node;
            	
    // updating end node pointer
	*end=new_node;


}

 

print_list()

To print the contents of the generic linked list, we need the head pointer of the linked list and function pointer for printing specific types of data.

 

void print(node* head,void* fun(void*))
{
	while(head!=NULL)
	{
	//function for printing specific type of data
	*fun(head->data);
	head=head->next;
	}
}

 

Code

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{
  
         void* data;
         struct  node* next;

}node;

void insert_end(node** end,void* data,int size)
{
	//allocate memeory for new node
	node* new_node=(node*)malloc(sizeof(node));

	new_node->next=NULL;
	// allocating memory for the data
	new_node->data=malloc(size);
	//storing the data of new node by copying from one address to another

	memcpy(new_node->data,data,size);

	(*end)->next=new_node;
	*end=new_node;

}

void print(node* head,void (*fun)(void*))
{
	while(head!=NULL) {
		//function for printing specific type of data
		(*fun)(head->data);
		head=head->next;
	}
}

void print_int(void* data)
{
	printf("%d ",*(int*)data);
}

int main()
{
	int elements[]={1,2,3,4,5};

	node* head=(node*)malloc(sizeof(node));
	node* end=head;
	head->data = malloc(sizeof(int));
	memcpy(head->data,elements,sizeof(int));
	head->next=NULL;

	int i;

	for( i=1;i<=4;i++)
	{
		insert_end(&end,&elements[i],sizeof(int));
	}

	print(head,print_int);

}

 

Output

 

1 2 3 4 5

 

FAQs

1). What is used in C++ for a generic definition?

There is a class called template which can be used to define generic structure.

 

2). What is a function pointer?

It is a pointer to a function that stores the address of the function.

 

void fun(int a )
{
       // function defination
}

//driver code

void (*fun)(int)= &fun;  // assigning address of the function to function pointer

 

3). What is memcpy() function in C?

It is a library function for copying a block of memory from one location to another.

 

Key Takeaways

This article covered how to implement Generic Linked List in C. A good grasp of Linked Lists can be a huge plus point in a coding interview.

 

Check out the CodeStudio library for getting a better hold of the data structures and algorithms.

 

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

 

Happy learning!

 

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think