Thread: linked list library

  1. #1
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40

    linked list library

    Hi,

    I would like to code a simple linked list library with functions like adding and deleting nodes, sorting a list etc. Also I wish this library to be as general as possible.

    Now my problem is, firstly functions like adding nodes result in a modification of the head pointer,

    so if my main program looks like:-

    Code:
    #include "listlib.h"
    
    struct node
    {
          char name[20];
          unsigned int age;
          struct node *next;
    };
    
    int main(void)
    {
           struct node *head=NULL;
    
           head=create_list(head);
    
           return 0;
    }
    How should I go about coding listlib.h?, right now i know that the create_list function should return struct node *, but what if someone else defines his nodes differently?

    how do i generalize my library, so as to work around this issue?

    Thanks,
    Sahil

  2. #2
    Unregistered User
    Join Date
    Sep 2005
    Location
    Antarctica
    Posts
    341
    maybe have

    Code:
    struct node
    {
        void *pData;
        struct node *next;
    };
    let them add whatever structure they want as the pData portion.

  3. #3
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    What I infer from this is that I define my node structure in the library itself. What i dont infer is how do I use your above example?, how do let users define their own data types and then cast void *pData?

    To put it simply, I would like some more elaboration if possible.

    Thanks,
    Sahil

  4. #4
    Unregistered User
    Join Date
    Sep 2005
    Location
    Antarctica
    Posts
    341
    Code:
    struct MyStruct
    {
       int num1;
       int num2;
       char *pName;
    }
    
    node *n = (allocate node);
    n->next = NULL;
    n->pData = (allocate MyStruct);

  5. #5
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    Code:
             
              typedef struct MyStruct * structptr;
    
             structptr s;
        
             node * n=malloc(sizeof(*n));
             n->next=NULL;
             n->pData=malloc(sizeof(*s);
    Is my above translation to C correct?

    Thanks,
    Sahil

  6. #6
    Unregistered User
    Join Date
    Sep 2005
    Location
    Antarctica
    Posts
    341
    sure, then when you want to access values:

    Code:
    ((structptr)n->pData)->num1 = 777;

  7. #7
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    Ummm...I'll have to cast each time I access values?

    cant i permanently cast n?
    Thanks,
    Sahil

  8. #8
    Unregistered User
    Join Date
    Sep 2005
    Location
    Antarctica
    Posts
    341
    of course, you can do something like:

    Code:
    structptr s = (structptr)n->pData;
    s->num1 = 777;
    s->num2 = 888;

  9. #9
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    Thanks a lot for your help, I hope i'll be able to code my list library now
    Thanks,
    Sahil

  10. #10
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    I've attached what I was able to manage last night, some questions:-

    1.I am unable to write a create_list function, because I dont really know what kind of data the user wants to enter into his nodes.

    2.For the same reason, i cant sort or search the list as well.

    I am unable to think of any workaround to this, is there any?

    Secondly, what else can I have in my library?
    Thanks,
    Sahil

  11. #11
    Registered User
    Join Date
    Sep 2005
    Location
    Sydney
    Posts
    60
    Your create function can take void *s and put them in the list - your library does not need to know what data type they are. In order to sort, you would need your sort function to take a pointer to a comparison function - similar to what qsort() does, so you can look that up for an example. Your search function would do the same thing - look up bsearch() for an example of this (note that bsearch works on already sorted arrays).

    Essentially, your library should not know or care what type of data it is storing. You take pointers to void and let the caller cast them back to what they really are when they access them, since it is the caller who will know what data type they are. You let the caller tell you how to compare them so you can sort and search. Your library doesn't need to worry about what the actual type is.

  12. #12
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    Hi,

    Alright i'll try to gather what you just told me:-

    1.My create_list should look like this:-

    Code:
    nodeptr create_list(size_t node)
    {
    	nodeptr p=malloc(sizeof(*p));
    
    	nodeptr head=NULL;
    
    	
    	p->data=malloc(node);
    	
    	do list making stuff;
    
    	return head;
    }
    So now it's upto the library user to set the info part of the nodes.

    2.Now onto sorting, how can i compare two void ptrs? kindly elaborate.

    3.If I can sort, I can search as well.

    4.If you had a look at my code, could you point out any suggestions, on any front.
    Thanks,
    Sahil

  13. #13
    Registered User
    Join Date
    Aug 2005
    Location
    New Delhi
    Posts
    40
    Hi,

    I am sorry for bumping such an old thread, but I think bumping it is better than starting a new one based on the same topic.

    I would really like someone to check out my code and tell me if I am going wrong on any front.
    Thanks,
    Sahil

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. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  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