C Generic Double Linked List each node Holding Multiple Items

Question

I'm trying to design a generic linked list where each node can store more than one items such as color, shape, and size.

This is what my .h file looks like

typedef struct linked{
    char type;
    void * item;
    struct linked * next;
    struct linked * prev;
}LinkedList;

LinkedList * NewLinkedList();
LinkedList * next(Iterator **I);
int hasNext(Iterator *I);
void insertion(LinkedList **a, void *b);
void printStringList(LinkedList *L);
void printIntList(LinkedList *L);
void printDoubleList(LinkedList *L);
void delete(LinkedList *L, void *n);

Should I modify the struct by adding void * item2 and void * item3 ...? Or is there better ways to do it.

My second question is: do I have to typecast the void pointers every time when I use them? This is my code for printIntList

void printList(LinkedList *L)
{
    LinkedList *tmp = NULL;
    tmp = L;
    while(L)
    {
        printf("%d\n",*(int*)L->item);
        L=L->next;
    }
}

And I have printIntList, printDoubleList and printStringList. Is there any way I can combine them?

Thanks!

Answer 1

You could do something like this:

typedef struct links {
    struct links * next;
    struct links * prev;
} links;

typedef struct outer_node {
  links l; // links to outer_node.l
  struct inner_node * children;
} outer_node;

typedef struct inner_node {
  links l; // links to inner_node.l
  char type;
  void * item;
} inner_node;

Basically, you have a linked list and each node of it is a linked list of its own.

Both lists are organized using the same kind of links, so you don't need to duplicate your linking/unlinking code.

You will need to use the offsetof() macro to get from a pointer to links its container inner_node or outer_node.

Here's a full demo:

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

typedef struct links {
    struct links * next;
    struct links * prev;
} links;

typedef struct outer_node {
  links l; // links to outer_node.l
  struct inner_node * children;
} outer_node;

typedef struct inner_node {
  links l; // links to inner_node.l
  char type;
  void * item;
} inner_node;

void linkNodes(links* l1, links* l2)
{
  links* tmp = l1->prev;
  l1->next->prev = l2->prev;
  l1->next = l2;

  l2->prev->next = tmp;
  l2->prev = l1;
}

inner_node* createNode(char type, void* item, inner_node* sibling)
{
  inner_node* n = malloc(sizeof(*n));
  n->type = type;
  n->item = item;
  n->l.prev = &n->l;
  n->l.next = &n->l;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;
}

outer_node* createOuterNode(inner_node* child, outer_node* sibling)
{
  outer_node* n = malloc(sizeof(*n));
  n->l.prev = &n->l;
  n->l.next = &n->l;
  n->children = child;
  if (sibling != NULL)
    linkNodes(&n->l, &sibling->l);
  return n;  
}

void PrintList(links* l, int level)
{
  links* l2 = l;
  do
  {
    if (level == 0)
    {
      outer_node* n = (void*)((char*)l2 + offsetof(outer_node, l));
      printf("{\n");
      PrintList(&n->children->l, level + 1);
      printf("}\n");
    }
    else
    {
      inner_node* n = (void*)((char*)l2 + offsetof(inner_node, l));
      printf("  type: %d, item: %s\n", n->type, (char*)n->item);
    }
    l2 = l2->next;
  } while (l2 != l);
}

int main(void)
{
  outer_node* root = 
    createOuterNode(
      createNode(0, "something",
        NULL
      ),
      createOuterNode(
        createNode(1, "foo",
          createNode(2, "bar",
            NULL
          )
        ),
        createOuterNode(
          createNode(3, "red",
            createNode(3, "green",
              createNode(3, "blue",
                NULL
              )
            )
          ),
          createOuterNode(
            createNode(4, "cat",
              createNode(5, "dog",
                createNode(6, "raven",
                  createNode(7, "shark",
                    NULL
                  )
                )
              )
            ),
            NULL
          )
        )
      )
    );

  PrintList(&root->l, 0);

  return 0;
}

Output (ideone):

{
  type: 0, item: something
}
{
  type: 1, item: foo
  type: 2, item: bar
}
{
  type: 3, item: red
  type: 3, item: green
  type: 3, item: blue
}
{
  type: 4, item: cat
  type: 5, item: dog
  type: 6, item: raven
  type: 7, item: shark
}

Answer 2

You need to consider whether the items defined per element are really dynamic or not. Are colour, size, shape the limit of what you need to store?

If that's all you really need, why not keep it simple and minimize the indirection/ memory allocation:

enum ShapeFlags { sizeDefined = 0x01, colorDefined = 0x02, shapeDefined = 0x04 };

typedef struct shapeList {
    ShapeFlags shapeFlags;
    Size  size;
    Color color;
    Shape shape;
    struct Linked * next;
    struct Linked * prev;
} ShapeList;

If on the other hand you really have a very dynamic set of properties, an alternative to list of lists might be to have a single list with sentinels.

enum FieldFlag { terminator = 0x01, size = 0x02, color = 0x04, shape = 0x08 };

typedef struct list
{
  FieldFlag type;
  void* value;
  struct list* next;
  struct list* previous;
} List;

You can then iterate as normal and use the terminator flag to know the end of an object.

Answer 3

You can make a generic list using discriminated union types:

typedef struct listitem
{
  char type;
  union
  {
    integer i;
    double d;
    char *s;
    // etc.
  } u;
} Listitem;

Use this listitem in your LinkedList.

Answer 4

Should I modify the struct by adding void * item2 and void * item3 ...? Or is there better ways to do it.

It depends on how generic is your list. If it is used to hold some specific values, you may create them all, or create a struct for them, if it might hold different type of values you might want to create a union, and if it might hold many values in one node, you probably better create some array of the values.

do I have to typecast the void pointers every time when I use them?

When you assign to / from them (int * a = a_void_pointer / a_void_pointer = an_int_pointer)- No

When you dereference such a pointer (*a_void_pointer) - yes.

Answer 5

Yes you probably should use three pointers, or can some shape have no color or size? If not, you should consider creating three pointers, each having type of what they point to, so you won't have to cast and deleting type.

The structure could look something like this:

typedef struct linked{
    Size * size;
    Color* color;
    Shape* shape;
    struct linked * next;
    struct linked * prev;
}LinkedList;

If you do want to store more items of the same type in one node (such as two colors...) you should consider using union.

To answer the second question... Yes you should cast void pointers every time you use them (at least in your case =). You should consider union once again for prettier code...