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() {
    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!