Thread: Generic implementation of linked lists in C

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    2

    Generic implementation of linked lists in C

    Hi everyone

    I currently study an example of a generic implementation of linked lists in C from a book.

    The implementation defines two structures, one for the elements of the list and one for the "overhead data" of the list.

    Code:
    typedef struct ListElmt_ {
        
        void *data;
        struct ListElmt_ *next;
        
    } ListElmt;
    
    typedef struct List_ {
        
        int size;
        
        int (*match) (const void *key1, const void *key2);
        void (*destroy) (void *data);
        
        ListElmt *head;
        ListElmt *tail;
        
    } List;
    The use of the variables size, head and tail seems quite obvious. Destroy points to a user defined function, which will be called by the function that destroys the entire linked list. But I don't get the purpose of that function-pointer match.

    The book only tells that match will not be used by the linked list itself, but by the data types derived of the linked list. The book will deal with other data structures and algorithm later, so maybe my question will be explained later in the book, but i will probably help my overall understanding if somebody can give me a hint. Any help is much appreciated!

    Thanks and have a relaxed weekend.

    Sokrates

    PS: It's probably not a pure C-question but more an algorithm topic. Hope it is anyway fine to ask here.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > But I don't get the purpose of that function-pointer match.
    Well the whole idea with having a bunch of function pointers in the List structure is to allow the generic list to implement any kind of functionality which involves traversing the list.

    Essentially, every list API function (foo) is going to do your basic list traversal, and call some specific function.
    Code:
    // data is some data pointer
    void foo ( List *list, void *data ) {
      ListElmt *n = list->head;
      while ( n != NULL ) {
        // call the user's foo function, passing in the current list user data, and
        // the supplied data pointer.
        list->foo(n->data,data);
        n = n->next;
      }
    }
    > int (*match) (const void *key1, const void *key2);
    So I'd guess that match gets passed key1 = the current node data, and key2 = whatever is trying to be found.
    Who knows what the int means
    - success / fail
    - a count of total matches
    - an index to the first match
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Take a look at glib (Gnome Library). There are linked lists, trees, and lots of generic stuff there.

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    2
    Thanks, that helped.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 1
    Last Post: 11-21-2011, 06:13 AM
  3. Replies: 5
    Last Post: 07-01-2011, 11:35 AM
  4. Polymorphism and generic lists
    By Shibby3 in forum C# Programming
    Replies: 9
    Last Post: 07-26-2010, 05:27 AM
  5. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM

Tags for this Thread