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() {
int (*add_function)(int a, int b);
add_function = &foo;
int n = add_function(1, 2);
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->head = NULL; // set the head to NULL
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) {
if(list->head != NULL) {
new_node->next = list->head;
}
list->head = new_node;
} 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) {
node = list->head;
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;
prev_node = list->head;
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->head = NULL;
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.
Hope this article was useful!