Reputation: 287
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!
Upvotes: 3
Views: 1545
Reputation: 62106
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
}
Upvotes: 1
Reputation: 6834
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.
Upvotes: 1
Reputation: 41220
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.
Upvotes: 1
Reputation: 137442
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.
Upvotes: 1
Reputation: 2992
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...
Upvotes: 1