#    Photo by JJ Ying on Unsplash

# C - Linked List with Variable Sized Data

This is actually an implementation that I did while reading the book, Introduction to Algorithms by Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen or better known as CLRS. This article is an attempt on describing how I implemented this linked list in C.

### How to Define Variable Size Data in C?

As some of you know in c there are no abstract classes and such, so how do we make c change the type of data used in different scenarios? this is where the `void`, `malloc` and `free` comes in handy. Given below are ways to allocate a arbitrary size of memory and keep it to store whatever data you want to store.

``````void *data_pointer;
data_pointer = malloc(size_of_data);
``````

So `data_pointer` keeps the location of the newly created data from the heap.

### Design Decisions

• nodes, when inserted to the list the data is copied (not a pointer to the data)
• when removing a node from the list the data is copied to a location that the caller of the function gives

### The Linked List Structure in C

To implement a linked list, first we need to define structures in c. The structures are `ListNode` and `List`, the `List` is the structure which is in charge of all the `ListNode` structures that belongs to it. First we'll code the structure of the `ListNode` which is easy.

``````typedef struct _ListNode {
struct _ListNode *next;
void *data;
} ListNode;
``````

The tricky part is the `List` data structure, the requirements from that data type are as follows

• know the size of the data type that we want to work with.
• know how to safely discard the data after it has been removed from the list with the above requirements in mind lets write the code for the `List`.
``````typedef struct {
ListNode *head; // pointer to the first node in the linked list
size_t item_size; // the size of an element
unsigned int count; // not really necessary
void (*destroy)(void *data); // a function pointer to give customized ways to delete the data inside the node
}
``````

The `unsigned int count` member is just a optimization that can be done on any linked list implementation to increase the performance when we need to find the size of the list.

As for the `void (*destroy)(void *data)`, don't be scared if you have not seen a pointer to a function before, it's just a complicated way of saying the type of the function that we want to have a pointer to. The syntax of a pointer to a function is as follows,

``````// return_type (*pointer_name)(arg1_type arg1, arg2_type arg2, ...);
// example

int foo(int num1, int num2) {
return num1 + num2;
}

void bar() {

n = (*add_function)(1, 2); // same as the above
}
``````

Hope that the above gave a simple idea of how pointers to functions works, if you still don't understand how they work I would suggest to read about them on the web and try one or two examples.

So back to the implementation... We now have to implement the actual working of the linked list, for this article I'll only be showing you how to,

• initialize the list
• insert node after a specific node
• remove node after a specific node
• cleanup the list

After implementing the above features all the other features should be really easy to implement, and also you could add in other features which you find important to a linked list.

### Initialize the List

To initialize the list we'll be implementing a function named `list_initialize`, creative right? Let's get right to it.

``````void list_initialize(List *list, size_t item_size, void (*destroy)(void *data)) {
list->item_size = item_size;
list->destroy = destroy;
list->count = 0;
}
``````

The initialization needs no explanation, but I'll explain it a little bit,

• set the `head` of the list to '0' because there are no items currently in the list
• set `item_size` to the size that the caller of the function provides
• set `destroy` pointer to the function that the caller provides, this can also be NULL
• set the count to 0

### Insert a Node After a Specific Node

To insert a node after a specific node we'll be implementing a function named `list_insert_after`, let's code this thing!

``````void list_insert_after(List *list, ListNode *node, void *data) {
ListItem *new_node = (ListItem*) malloc(sizeof(ListItem));
new_item->next = NULL;
if(node == NULL) {
}
} else {
new_node->next = node->next;
node->next = new_node;
}
new_node->data = malloc(list->item_size);
memcpy(new_node->data, data, list->item_size);
list->count++;
}
``````

As you can see the last 3 lines of the above function is the place where we can use to copy the needed data into another memory location in the heap. The rest of the code is the same as for all single linked lists.

### Remove a Node After a Specific Node

To remove a node after a specific node in the list we have to have a pointer to the node before the one that we need to remove, then the function `list_remove` can be used. If we want to remove from the head we set the to NULL, let's see it's implementation

``````void list_remove(List *list, ListNode *prev_node, void *data) {
ListNode *node;
if(prev_node == NULL) {
if(node != NULL) list->head = node->next;
} else {
node = prev_node->next;
if(node != NULL) prev_node->next = node->next;
}
if(node == NULL) return;
memcpy(data, node->data, list->item_size);
if(list->destroy != NULL) {
(list->destroy)(node->data);
}
free(node->data);
free(node);
node = NULL;
list->count--;
}
``````

As you can see after the boring link changing which has to be done in order to remove a node, we copy the content of the data into a caller specified location. Then we call the destroy function (if there is one) and the free up the allocated spaces. The count also has to be decremented.

### Cleanup the List

To cleanup the list we have to start from the head and remove all the linked nodes, then reset the list to the initial state. The code is as follows.

``````void list_cleanup(List *list) {
ListNode *prev_node, *node;
while(prev_node != NULL) {
node = prev_node->next;
if(list->destroy != NULL) {
(list->destroy)(prev_node->data);
}
free(prev_node->data);
free(prev_node);
prev_node = node;
}
list->destroy = NULL;
list->count = 0;
list->item_size = 0;
}
``````

### Conclusion

This implementation is just an idea into how the `malloc`, `free` and some memory management can be used to create a variable size data linked list.