llwfp

A C library for singly linked lists
Login

A C library for singly linked lists

⇦ previousnext ⇨

2. Generic node definition - using void * for data

While using a specific data type for the data definition is ok for a simple linked list implementation, a library should be able to handle any kind of data.
A more generic approach is to replace 'int | char * | struct | double[] | whatever' with 'void *':

    typedef struct node_t
    {
      struct node_t *next;
      void *data; /* A BIT MORE COMPLEX, BUT GENERIC */ 
    } node_t;

Let's see what advantages and disadvantage this brings us.

2a. Mix data types in a list

One advantage with a generic data definition is the possibility to have various data types in one single list:

    const int data1 = 12;
    const char *data2 = "99";
    const double data3 = 37.0;

    node1->data = (void *)&data1;
    node2->data = (void *)&data2;
    node3->data = (void *)&data3;

    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;

2b. Data assignment becomes more complex

Let's forget about C assignment operators for node data:

    node1->data = 12; /* SIMPLE ASSIGNMENT DOESN'T WORK */

Pointing node data to a read-only variable works as expected:

    const int data1 = 12;
    node1->data = (void *)&data1; /* OK, BECAUSE DATA IS DECLARED AS const */

Pointing node data to a read/write variable may work as expected, but is not recommended:

    int data1 = 12;
    node1->data = (void *)&data1; /* NOT RECOMMENDED FOR READ/WRITE VARIABLES */

Why?
Using a pointer to a loop variable will probably not do what you want:

    int i = 0;
    for (i = 0; i < 100; ++i)
    {
      node->data = (void *)&i;  /* DON'T DO THIS, NOT WORKING AS EXPECTED */
      node->next = calloc(1, sizeof(*node));
      node = node->next;
    }
    i = 666; /* OOPS, EVIL SURPRISE, DATA FOR ALL 100 NODES JUST CHANGED! */

Instead, allocate data for each node and copy the current value of the loop variable:

    int i = 0;
    for (i = 0; i < 100; ++i)
    {
      node->data = calloc(1, sizeof(i));
      memcpy(node->data,  &i, sizeof(i));  /* WORKING AS EXPECTED */
      node->next = calloc(1, sizeof(*node));
      node = node->next;
    }
    i = 666; /* NO EVIL SURPRISES HERE, NODE DATA IS NOT AFFECTED */

2c. Dereferencing data casting also becomes more complex

How to cast void * data to print with gdb?

    cast to TYPE     : gdb) p *(TYPE *)node->data
    cast to int      : gdb) p *(int *)node->data
    cast to char *   : gdb) p *(char **)node->data
    cast to struct   : gdb) p *(struct *)node->data

2d. Apply previous examples using void *

See the example below for how to replace int, char *, struct and double[] with void *.

One detail to notice is that memory for node data is always allocated (even for "simple" types as int) when using void *, so the cleanup always requires an extra call to free(), both for node data, and the node itself.
Additionally, if node data is a structure, any dynamically allocated struct member obviously also has to be free():ed.

Example 2: Using 'void *' type for node data

We see that using one single generic node type node_t permits to unify source code to some extent, such as node_get_by_index().
Anyhow, handling data is still "data type dependent".
For example, there are still several node_add_xxx() and node_print_xxx() functions, one per data type.
In the next section, callbacks will be used to reduce the number of functions.

⇦ previousnext ⇨