Generic linked list?

Question

I was wondering if that was possible to use generic function for linked lists in C, (i don't want to do that in C++ but in C) example :

struct first_struct
{
    struct first_struct *next;
    int a;
    int b;
};
struct second_struct
{
     struct second_struct *next;
     int a;
     int b;
     int c; // just one more variable than first-struct
};

am i force to make a function each time for the two lists :

add_node(struct first_struct *mystruct)// doesn't matter the function here juste let's assume they add correctly a node
add_node1(struct second_struct *mystruct)
//and so on each time i want to make some others function always make them twice

or is there a better way to do that ?

Answer 1

You could implement a generic linked list by using two features of C, namely void pointers and function pointers.

The latter (function pointers) is not crucial for building the linked list, but it is crucial if you want to do something useful with the data of the linked list such as printing.

Here is a full working example:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct node {
    void *data;
    struct node *next;
} node;


int lst_nodeAdd(
    node **head,
    node **tail,
    const void *data,
    size_t szData);

void lst_nodePrint(
    node *head,
    void(*print)(const void *));

void lst_nodeFree(node *head);

/* PRINTING FUNCTIONS */
void print_int(const void *a);
void print_string(const void *str);


int main(void)
{
    const char *str[] = {
        "0x0001",
        "0x0002",
        "0x0003",
    };

    // head & tail
    node *head = NULL; 
    node *tail = NULL;

    // List of strings
    lst_nodeAdd(&head, &tail, str[0], strlen(str[0]) + 1);
    lst_nodeAdd(&head, &tail, str[1], strlen(str[1]) + 1);
    lst_nodeAdd(&head, &tail, str[2], strlen(str[2]) + 1);

    lst_nodePrint(head, print_string);
    lst_nodeFree(head);
    head = NULL;
    tail = NULL;
    //....................................................

    // List of ints
    int int_array[] = {
        0,
        1,
        2,
    };
    lst_nodeAdd(&head, &tail, &int_array[0], sizeof(int));
    lst_nodeAdd(&head, &tail, &int_array[1], sizeof(int));
    lst_nodeAdd(&head, &tail, &int_array[2], sizeof(int));

    lst_nodePrint(head, print_int);
    lst_nodeFree(head);
    head = NULL;
    tail = NULL;


    system("PAUSE");
    return 0;
}


int lst_nodeAdd(
    node **head,
    node **tail,
    const void *data,
    size_t szData)
{
    void *tmp;
    tmp = malloc(sizeof(node));

    if (!tmp)
    {
        return 0;
    }

    ((node *)tmp)->next = NULL;
    ((node *)tmp)->data = malloc(szData);

    if (!((node *)tmp)->data)
    {
        free(tmp);
        return 0;
    }

    memcpy(((node *)tmp)->data, data, szData);

    if (!*head)
    {
        *head = (node *)tmp;
    }
    else
    {
        (*tail)->next = (node *)tmp;
    }
    *tail = (node *)tmp;
    return 1;
}

void lst_nodePrint(
    node *head,
    void(*print)(const void *))
{
    while (head)
    {
        print(head->data);
        head = head->next;
    }
}

void lst_nodeFree(node *head)
{
    node *tmp = head;
    while (head)
    {
        head = head->next;
        free(tmp->data);
        free(tmp);
        tmp = head;
    }
}

void print_int(const void *a)
{
    printf("%d\n", *(const int *)a);
}

void print_string(const void *str)
{
    puts((const char *)str);
}

Answer 2

You can implement a generic linked list fairly easy using a void pointer in your struct.

Here is an example of a such list created by me:

list.c

#include <stdlib.h>
#include "list.h"
#include <malloc.h>
#include <stdio.h>
#include <string.h>

void listNew(list* list, unsigned int elementSize, freeMemory freeFn,        
printList print) {

    list->numOfElem = 0;
    list->freeFn = freeFn;
    list->pr = print;
    list->head = NULL;
    list->sizeOfElem = elementSize;
}

node * listPushFront(list *list, void* data) {

    node *listNode = (node*)malloc(sizeof(node));

    if (listNode == NULL) {

        return NULL;
    }

    listNode->object = malloc(sizeof(list->sizeOfElem));

    if (listNode->object == NULL) {

        return NULL;
    }

    memcpy(listNode->object, data, list->sizeOfElem);

    listNode->pNext = list->head;
    list->head = listNode;

    list->numOfElem++;

    return listNode;
}

void listDestroy(list *list)
{
    node *current;

    while (list->head != NULL) {
        current = list->head;
        list->head = current->pNext;

        if (list->freeFn) {
            list->freeFn(current->object);
        }

        free(current->object);
        free(current);
    }
}

void listPrint(list *l) {

    node* temp = l->head;
    int i = 0;

    if (temp == NULL) {

        printf("\nEmpty list.");
        return;
    }

    while (temp) {

        printf("\nPrint element %d", i);

        l->pr(temp->object);
        temp = temp->pNext;

        i++;
    }
}

list.h

#ifndef __LIST_H
#define __LIST_H

typedef void(*freeMemory)(void*);
typedef void(*printList)(void*);

typedef struct _node {

    void* object;
    struct _node* pNext;

}node;

typedef struct _list {

    unsigned int sizeOfElem;
    unsigned int numOfElem;
    node* head;
    freeMemory freeFn;
    printList pr;

}list;

void listNew(list* list, unsigned int elementSize, freeMemory freeFn,             
printList print);
node * listPushFront(list *list, void* data);
void listDestroy(list *list);
void listPrint(list *l);

#endif

main.c

#include <stdlib.h>
#include "list.h"
#include <stdio.h>
#include <string.h>

typedef struct _TLV {

    unsigned int tag;
    unsigned int length;
    unsigned char* value;

}TLV;


void listFree(void* data) {

    TLV** ptr = (TLV**)data;

    free((*ptr)->value);
}

void Print(void* data) {

    TLV** ptr = (TLV**)data;

    printf("\nTag = %d", (*ptr)->tag);
    printf("\nLength = %d", (*ptr)->length);
    printf("\nValue = ");

    for (int i = 0; i < (*ptr)->length; i++) {

        printf("%d", (*ptr)->value[i]);
    }
}

TLV* allocateTLV(unsigned int tag, unsigned int length, unsigned char* 
value) {

    TLV* elem = (TLV*)malloc(sizeof(TLV));

    if (elem == NULL) {

        return NULL;
    }

    elem->tag = tag;
    elem->length = length;
    elem->value = (unsigned char*)malloc(length);

    if (value == NULL) {

        return NULL;
    }

    memcpy(elem->value, value, length);

    return elem;
}

int main()
{
    list l;
    TLV* tag;

    unsigned char test2[2] = { 1,2 };
    unsigned char test3[3] = { 1,2,3 };
    unsigned char test4[4] = { 1,2,3,4};

    listNew(&l, sizeof(TLV*), listFree, Print);

    tag = allocateTLV(2, sizeof(test2), test2);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    tag = allocateTLV(3, sizeof(test3), test3);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    tag = allocateTLV(4, sizeof(test4), test4);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    listPrint(&l);

    listDestroy(&l);

    return 0;
}

main.c is an example of creating a list of pointers to the struct TLV.

Answer 3

Personally, I have implemented a generic linked list : it work by providing a function to compare two node, and an optional function to destroy a node (free string, close file, etc etc).

#include <stdbool.h>
#include <stddef.h>

typedef struct link {
    void        *data;
    struct link *previous;
    struct link *next;
} link_s;

typedef struct list {
    link_s *head;
    link_s *tail;
    size_t nbLink;

    /* function pointer */
    int    (*Data_Compare)(const void *data1, const void *data2);
    void   (*Data_Destructor)(void *data);
} list_s;

#define LIST_CONSTRUCTOR(f_compar, f_destructor) {.head = NULL, \
                                                  .tail = NULL, \
                                                  .nbLink = 0, \
                                                  .Data_Compare = f_compar, \
                                                  .Data_Destructor = f_destructor}

void List_Constructor(list_s *self, int (*Data_Compare)(const void *data1, const void *data2), void (*Data_Destructor)(void *data));
void List_Destructor(list_s *self);

bool List_Add(list_s *self, void *data);

void *List_RemoveByLink(list_s *self, link_s *link);
void *List_RemoveByData(list_s *self, void *data);
void *List_RemoveByCondition(list_s *self, bool (*Data_Condition)(const void *data));

void List_DestroyByLink(list_s *self, link_s *link);
void List_DestroyByData(list_s *self, void *data);

void List_DestroyByCondition(list_s *self, bool (*Data_Condition)(const void *data));

void List_Sort(list_s *self);
void List_Merge(list_s *to, list_s *from);
void List_Reverse(list_s *self);

This way, you can add whatever you want into the list. Just be carefull to have a propre comparison function and destroy function.

Answer 4

The better way is to abstract out the link handling (what makes a structure into a list node) and then re-use that by starting each listable structure with the node structure.

Like so:

struct list_node {
  struct list_node *next;
};


struct first_struct {
  struct list_node list_node;
  int a;
  int b;
};


struct second_struct {
  struct list_node list_node;
  int a;
  int b;
  int c;
};

Then make list functions that deal with (pointers to) struct list_node.

This is commonly called "intrusive lists", since it requires the application-level data structure to "know" that it's possible to put it in a list. It also means an instance of a structure can only be on one list at a time.

The other way is to make a list library that only deals with pointers to data (void *), that removes the limitation but brings others instead (more heap allocation, annoying when data is small).