Generic Linked List

Introduction

Linked lists are one of the best examples of why void pointers are useful.

Recall that our previous implementation of linked lists assumes that the values are integers.

typedef struct SList
{
    int value;
    struct SList* next;
} TList;

However, we may want a linked list of float values or even strings. What would be the solution? Defining multiple structures like TListInteger, TListFloat, and TListString isn’t ideal. We’d have to implement the list functions three times, once for each structure. They would be almost identical, with the only exception being the list’s type or perhaps how they handle the value field.

Generic linked lists

The solution is to change the value field from a value to a pointer. Then, we can turn this pointer into a void* by making it accept any data type.

typedef struct SGenericList
{
    void* value;
    struct SGenericList* next;
} TGenericList;

Of course, there are also disadvantages. One of them is that the code becomes slightly harder to write and manage since not only do we have to allocate the next field, but we’ll also have to allocate (and free) space for the value field.

Note: Since C is not object-oriented, we don’t have other choices. We must use a void* and manually manage its memory.

Everything else except the management of the value field remains the same for the linked lists with a concrete type as value.

Notice the following memory drawing. The node itself no longer contains the value. It contains a pointer to a memory block that holds the value.