Generic linked list

This is a discussion on Generic linked list within the C Programming forums, part of the General Programming Boards category; Could anyone help me by giving some sample codes of how to write a generic linked list using Void* pointers? ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    12

    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...


  2. #2
    Registered User
    Join Date
    Dec 2002
    Posts
    56

  3. #3
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    Code:
    struct node
    {
      struct node *next, *prev;
      void *data;
    };
    :wq

  4. #4
    Registered User
    Join Date
    Dec 2003
    Posts
    12
    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

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    12
    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
      }

  6. #6
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    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);
    }

  7. #7
    Registered User
    Join Date
    Apr 2005
    Posts
    12
    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);
    }

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What you should work out first, is how to simply create a linked list of any given type. Get that down so you understand how it works. Then change the portion that fills it with a specific type to fill it with a different type.

    Such as:
    Code:
    struct node
    {
        struct node *prev, *next; /* I prefer double linked lists. */
        struct data *data; /* Your data element. */
    };
    Now all you have to do is change the 'data' definition, so it contains type information and the actual data. Write functions to fill a given data type, and just stick that in your node.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21