llwfp: A C library for singly linked lists

1. Simple node definition

In this section we will one typedef for each data type.
It is not a generic approach, but may be sufficient for simple implementations.

1a. Using int for data

A typedef example for int data:

    typedef struct node_int_t
    {
      struct node_int_t *next;
      int data; /* STRAIGHTFORWARD, BUT NOT VERY GENERIC */ 
    } node_int_t;

Data assignment and access is straightforward:

    /* Create and print one node */
    node_int_t *node1 = calloc(1, sizeof(*node1));
    node1->data = 12;
    printf("node1->data=%d\n", node1->data);

    /* Create another 100 nodes, link first node in loop to node1 */
    for (i = 0; i < 100; ++i)
    {
      if (i == 0) node1->next = node;
      node->data = i;
      node->next = calloc(1, sizeof(*node));
      node = node->next;
    }
    printf("Data for node 5=%d\n", node1->next->next->next->next->data);

List cleanup is easy, as calloc() only has been used to reserve memory for nodes, but not for node data.
Calling free() for each node is sufficient:

    node_int_t *current = *head, *next = NULL;
    while (current)
    {
      next = current->next;
      free(current);
      current = next;
    }

Things become a bit more complicated when we want to store "string" data in a linked list.
Should we use a fixed max size for strings and avoid calloc()/free() for data, or use a more flexible approach, using dynamically allocated data?

1b. Using (fixed size) char[] for data

typedef for char[MAXSIZE] data:

    typedef struct node_char_arr_t
    {
      struct node_char_arr_t *next;
      char data[MAXSIZE]; /* LESS TO CLEANUP, BUT LESS FLEXIBLE, MORE MEMORY WAISTE */ 
    } node_char_arr_t;

Assigning node data is straightforward:

    snprintf(node->data, MAXSIZE, "%d", i);

Using a fixed data size makes the node cleanup as easy as for int data, no data cleanup is necessary.
Memory usage is not optimized, though, as node data always use MAXSIZE bytes, even for short strings.

1c. Using (dynamic) char * for data

typedef for char * data:

    typedef struct node_char_p_t
    {
      struct node_char_p_t *next;
      char *data; /* MORE TO CLEANUP, MORE FLEXIBLE */ 
    } node_char_p_t;

Assigning node data becomes a bit more complicated:

    char buf[BUFSIZE];
    snprintf(buf, BUFSIZE, "%d", i);
    node->data = calloc(1, strlen(buf)+1);
    memcpy(node->data, buf, strlen(buf)+1);

As an extra step, data for each node needs to be free():ed upon deletion

    void data_cleanup(node_char_p_t **node)
    {
      node_char_p_t *current = *node;
      while (current)
      {
        free(current->data);
        current = current->next;
      }
    }

1d. Using struct for data

As long as a struct only has static data members, it may be used for node data in the same way as an integer or a fixed size array.
For dynamically allocated members, the issues are the same as for char pointers described previously.
See the source code example for details.

    typedef struct html_header
    {
        header_level level;
        char *title;
    } html_header;

    typedef struct node_struct_t
    {
        html_header data; /* NOT VERY GENERIC */
        struct node_struct_t * next;
    } node_struct_t;

1e. Using double[] for data

When using variable-sized numeric arrays (integer or float, as opposed to char), there is another issue.
A char array (interpreted as a "string") ends with NULL, while this isn't true for a double array, for example.
This means that if each node will keep a variable-sized array, we need extra information to get the size using an arr_size node member:

    typedef struct node_double_arr_t
    {
      struct node_double_arr_t *next;
      double *data;    /* NOT VERY GENERIC */
      size_t arr_size; /* NOT VERY GENERIC */
    } node_double_arr_t;

Examples: simple node data types

Libraries/templates

%%% TODO %%% :
Finish header-only libs for the examples above:

If any of these header files is similar to what you need, you may just copy the code and stop reading here.
Anyhow, if you need something more generic, please read on.

⇦ previous next ⇨