Thread: Generic linked list

Could anyone help me by giving some sample codes of how to write a generic linked list using Void* pointers? i don' t understand how it works and i'm stucked at my assignment...

http://valis.cs.uiuc.edu/~sariel/tea.../99_05_25.html

That should be helpful.

I wont give you code, but I will give you an idea.
Create two files (there will be your "classes"), a linkedList file and a node file.

Create a struct in the linkedList (header) file which contains all the elements of the linkedList (i.e *next, *prev,*node). next is a pointer of the same type as the struct you are declaring it in, as is prev. The node pointer will be of void type. We will call the linkedList type 'List'. (i.e make a typedef struct to be List).

In the linkedList c file create a constructor for the linkedList which will basically take two pointers of type List (your next and prev) and a pointer to a node (of void type remember). Within the constructor create an object of type List and dynamically allocate the memory (use malloc() ). Then assign your new Object's members to the value of the pointers which you passed the constructor.

With this you can create a generic linked list. To actually create a working,usable linkedList you obvisouly need accessors, mutators etc etc.

Ray

Thx guys... i'll try to understand the sample.
And yeah i know i should have a struct like that
but i'm not sure what should i do when i write the add function...

i wanted to pass instances of a stuct from the main program to the linked list but i not sure how to do it with void pointer... Should i do this in the add function within the linkedlist?

Code:

 
 void add(struct node aUser, List** head)
 {
       ... //some code here
  }

To keep it generic, you may want to use a function pointer that points to a function that extracts data. So if you had it point to a get_node_data() function that basically just returns the value:

Code:

void* get_node_data(struct node* head)
{
        return head->data;
}

Obviously then you would need to make another function that handles normal integers, floats etc. This is what makes a generic linked list structure "generic".
So inside the add() or insert() function of your linked list, you will have a line similar to the following:

Code:

void* add(struct node** headRef, void* key, void*(get_data)(void*))
{
        /* Do something here */
        (*headRef)->data = get_data(key);
}

thx for the advise.

But how about if the node just hold a pointer to struct from the main program? As void* pointer can point to any data type we want and later when i walk through the linked list i just cast it back the the struct type like this:

Code:

(user*) node->data

So if i look at it that way, do i have to still use the follow in the add function?

Code:

void* add(struct node** headRef, void* key, void*(get_data)(void*))
{
        /* Do something here */
        (*headRef)->data = get_data(key);
}