static linked list in C that holds any data type but all of the same type

numq 0
Viewed 35

I'm trying to implement a static linked list in C that holds any data type. I know that the node struct should use a void* but I also want each list to hold the same data type. That is, lists can hold any data type but every item in the list must be of the same type. I know using void* allows nodes to have any data type but how do I make it so that a list only contains items of the same type?

linked-list nodes c
2 Answers

The problem with C is that it is a weakly typed language, this means that you can cast a Banana to a Truck and the compiler will be totally fine with that. Programmers in C are conditioned to keep this in mind and be very wary of what they are doing, that is to say it is the programmers responsibility to "think ahead" and make no such mistakes (e.g. like putting a Banana in a list of Trucks). You could work around this by adding another layer between your datatypes and the list nodes. A trust could hold a void* to the actual type together with an enum or an integer value representing the id of the data type you are trying to store in the list, you could call this a tagged node or something. The issue now becomes how to retrieve that tag or enum value. This will sadly add some boilerplate to your program, however, this might be automated using macro's.

Note that the problem you are highlighting (weak typing) is just part of the quirkiness of C. what I usually do in these situations is naming the variable holding the list accordingly and think very carefully of what I am doing with this variable.

A solution may be to, instead of using a List, use an array, this will at least produce a segmentation fault in some scenario's, but that will also be the case if you cast a Truck to a Banana and try to access fields which are out of memory range...

Hope this helps!

Plegeus0

You can use the macro system to handle non void * lists... if you do something like:

#define LIST_OF(_type) struct node_of_##_type {  \
    struct node_of_##_type *prev, *next;         \
    _type                   data;                \
}

then, you can declare as many list types as you want, you have only to say something like:

typedef char *string;

LIST_OF(string) *my_list = NULL; 
/* will expend to something similar to:
    struct node_of_string {
        struct node_of_string *prev, next;
        string                 data;
    } *my_list = NULL; 
 */

This is an attempt (well, too far yet to be comparable) to emulate the templates of C++. You will not have a list capable of storing anything, but a list adapted only to one type (but any type that can be typedef'd, as the type parameter must be a typename, not a type specification. And, as in C++, once you have that you have to instantiate every function using that type, to the proper type, forcing you to name it, (as functions cannot be overloaded in C) and to rewrite (by means of more macro expansions) to the actual code. Things get complicate soon, making it necessary some help from the language to use OOP techniques in C.

Luis Colorado0
Related