Thread: Generic Linked List

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    6

    Generic Linked List

    Hi guys,

    I have a working linked list which holds ints. I want to hold a pointer rather than an int. (This way, the linked list is generic in that it could be a list of pointers to any datatype)

    I'm having trouble figuring out where I should be casting to and from the void pointer, though. When inserting, should I always pass a void pointer in the calling function? When removing, should I always cast from void to datatypexxx in the calling function? Is there any other way?

  2. #2
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    As long as your linked list simply acts as a container then it should accept and return pointers of type void. The programmer using this container would be responsible for casting to the right type for any manipulations requiring knowledge of type.

    This last part is important. To keep the list truely general, you cannot perform any operations within the linked list that requires any knowledge of the true datatype.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    6
    My second issue is free'ing the memory alloted to the packet of data inside each linked list node.

    Right now I have...

    Code:
    // free the given node (I should free what the void pointer val points to as well)
    
    void ll_destroyNode(node* victim){
            //free(victim->val);
            free(victim);
    }
    How can I free what val is pointing at when I have no way of knowing what type it is? If the sizeof(val's data type) was passed by the calling function, is there a way I could use that? i.e. Can you say "deallocate xx bytes starting at address yy"?

    Thanks!

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    6
    Quote Originally Posted by andyhunter
    To keep the list truely general, you cannot perform any operations within the linked list that requires any knowledge of the true datatype.
    Right. So a de-allocate function is probably a bad idea? (I should leave it in the hands of the programmer calling it?)

  5. #5
    Handy Andy andyhunter's Avatar
    Join Date
    Dec 2004
    Posts
    540
    No free expects a void* as the argument, aka
    Code:
    void free(void *memblock);
    Simply pass it your pointer to have it deallocate the memory.

    If your container allocates the memory it should free the memory.
    i don't think most standard compilers support programmers with more than 4 red boxes - Misplaced

    It is my sacred duity to stand in the path of the flood of ignorance and blatant stupidity... - quzah

    Such pointless tricks ceased to be interesting or useful when we came down from the trees and started using higher level languages. - Salem

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    6
    Quote Originally Posted by andyhunter
    No free expects a void* as the argument
    Really? That's interesting -- I'll have to read up on how free knows how many bytes to deallocate.

    Thanks a lot!

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    You might consider accepting a function handler. Something like:
    Code:
    void free_list(LIST *head, void (*free_node)());
    That way you can still use a free_list() function and the programmer can tell the library exactly how to free each node. Just in case it's a linked list of structures and the programmer also needs to free memory allocated for individual members.
    If you understand what you're doing, you're not learning anything.

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, 06: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, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM