how to create a linked list of structs in c

Question

I have 3 types of structures: book, CD (in the CD I have the struct "song"- and the CD contain a list of songs), and a DVD.

I need to create a linked list of products of a store My question is how to create a list of products without knowing which type is the pointer in it. It can be book, CD or DVD.

(I cannot use unions.)

Answer 1

You need to use void pointers for the data set. Here is a snippet of code from my linked list structures I use modified for your need:

#define CD 1
#define DVD 2
#define BOOK 3

/* Structure for linked list elements */
typedef struct ListElmt_ {
        void *data;
        unsigned datatype;    /* variable to know which data type to cast as */
        struct ListElmt_ *next;
} ListElmt;

#define list_data(element) ((element)->data)

Using the void pointer to pack your data into the list, you can now just test the datatype variable and uncast as necessary. I use a macro to return list data (defined above). So you could use something like:

CD_struct *cd_data
if (element->datatype == CD)
      cd_data = (CD_struct *) list_data(ListElmt)

Answer 2

Leaving the implementation of the CD / DVD data structures up to you, as well as the implementation of the linked list, you would probably want to do something like this:

enum ptype {
    PTYPE_BOOK,
    PTYPE_CD,
    PTYPE_DVD,
};

struct book {
    char *author;
    char *title;
    char *publisher;
    char *isbn;
};

struct product {
    enum ptype type;
    void *data;
};

struct product_list {
    struct product *product;
    struct product_list *next;
};

The enumeration is responsible for distinguishing the type of product being pointed to. To create a book, for instance:

struct product *
create_book(char *author, char *title, char *publisher, char *isbn)
{
    struct product *p;
    struct book *b;

    p = calloc(1, sizeof (*p));
    if (p == NULL) {
        return NULL;
    }
    p->type = PTYPE_BOOK;
    p->data = calloc(1, sizeof(*b));
    if (p->data == NULL) {
        free(p);
        return NULL;
    }
    b = p->data;

    b->author = author;
    b->title = title;
    b->publisher = publisher;
    b->isbn = isbn;

    return p;
}

This is a typical interface when unions can't be used for whatever reason. It's unfortunate in that it requires much more memory allocation (and in reality, you'll probably have to strdup(3) author / title / publisher / isbn).

To retrieve a book from a product, you might like to have something like this:

static inline struct book *
get_book(struct product *p)
{

    assert(p->type == PTYPE_BOOK);
    return p->data;
}

You don't need to (and shouldn't) cast a void pointer in C. If you're using or supporting a C++ compiler, you may need to use return (struct book *)p->data;. You'd implement something similar for your CD and DVD types. Then, when you need to extract the product:

switch (p->type) {
case PTYPE_BOOK:
    b = get_book(p);
    break;
case PTYPE_CD:
    c = get_cd(p);
    break;
case PTYPE_DVD:
    d = get_dvd(p);
    break;
}

You may also want to look at using something other than a linked list for storing these things, especially if they will be read / traversed many times after they are created. (A vector would not be a bad idea). If you know how many items you'll have, this can help reduce the number of allocations you must perform, and the contiguous memory access will improve speed.

If you need to search entries, I suspect you'll need an external searchable data structure anyway.

Answer 3

if every struct has ITEMTYPE is first member, you can use LinkedList.itemtype on all

this is because the offset to itemtype does not depend on inner struct order, since by rule i said itemtype is same type in all and first in all

Answer 4

One way could be :

• Create a generic Structure 'Product'
• Keep a variable to keep track of the current type of product.
• Keep three pointers of Book, CD & DVD each.

Or As in Archie's Comment :

• Create a generic Structure 'Product'
• Keep a variable to keep track of the current type of product.
• Keep a void * pointer & cast when needed.

I think the first one is useful, if at a later stage, the product can be of multiple type. Eg - Book + CD