0

Im trying to create a linked list in C, where each node has a specific size entered by the user when the program launches. I already thought of a struct:

struct ListNode{

    char * str;

    struct ListNode * next_node;

};

but here the size of each node is fixed. Any ideas?

Thanks a lot in advance.

cchatzis
  • 13
  • 5
  • 3
    Size of what? This "node" has two fields of fixed size. – Eugene Sh. Feb 25 '19 at 18:34
  • @EugeneSh. Hi and thanks for your answer. I want each ListNode **as a whole** to be able to have a given size. – cchatzis Feb 25 '19 at 18:38
  • To have a size, it has to contain something of that size. What do you want it to contain, which will have the variable size? – Eugene Sh. Feb 25 '19 at 18:39
  • I want each node to contain n x strings. (n : as many strings fit in the given by the user size of each node) – cchatzis Feb 25 '19 at 18:42
  • 2
    This is an XY problem. What is the end goal? – SergeyA Feb 25 '19 at 18:43
  • 1
    Currently your `struct` has a *pointer* that might point to strings of different sizes. But these are technically are not a part of the `struct`, so their size is not included. Why this is not good enough for you? – Eugene Sh. Feb 25 '19 at 18:44
  • @SergeyA i want to create a hash table, but each bucket has to have a specific size! Hope that clarifies things up. – cchatzis Feb 25 '19 at 18:44
  • 1
    You can't have a [variable length array](https://stackoverflow.com/questions/32311269/can-we-have-a-struct-element-of-type-variable-length-array) in a `struct` but you can have a [flexible array member](https://stackoverflow.com/a/26183999/4142924). – Weather Vane Feb 25 '19 at 18:46
  • 1
    @cchatz than you most likely have to have a pointer to dynamically allocated bucket – SergeyA Feb 25 '19 at 18:46
  • @EugeneSh. That works too, but it would be preferred if each node had the size the user has given as input. – cchatzis Feb 25 '19 at 19:11
  • @SergeyA That sound actually like the one i need. Thanks a lot everyone for your time and quick answers. (I cant upvote comments yet?) – cchatzis Feb 25 '19 at 19:11

2 Answers2

1

It seems you need your data size that the node holds to change each time. You can achieve this by using a constant size node that holds a pointer to dynamically allocated data.

Note that in the example below the struct size stays sizeof(void*)+ sizeof(node*) but the size of data allocated for each node changes using the user input.

typedef struct Dnode
{
    void* data;
    struct Dnode* next;
}Dnode;

Dnode* CreateDnode(size_t data_size_bytes)
{
    Dnode* newNode = NULL;

    newNode =  malloc(sizeof(Dnode));/*always the same*/
    if(NULL == newNode)
    {
        return NULL;
    }
    newNode->data =  malloc(data_size_bytes);/*changes by input*/
    if(NULL == newNode->data)
    {
        return NULL;
    }
    newNode->next = NULL;
    return newNode;
}
marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
H.cohen
  • 517
  • 3
  • 9
  • Hi and thanks for the help!That works. Is there a way the whole node has this data_size_bytes? – cchatzis Feb 25 '19 at 19:19
  • you can allocate a block of memory and manage the hole thing by your self- that is you can just allocate Size, and decide that the first 8 bytes for example- depending on your pc architecture will be used for the next ptr and the rest of it will hold your data. but the size of Size will have to be greater than sizeof(void*) for you to be able to save the next ptr and maintain a list @cchatz – H.cohen Feb 25 '19 at 19:56
0

Sounds like you may be looking for the "flexible array member" feature whereby an incomplete array is placed at the end of a structure:

struct ListNode {
  struct ListNode *next;
  char data[];
};

This is allocated like:

struct ListNode *node = malloc(sizeof *node + data_size_bytes);

Then we can store values in node->data[i] for i from 0 to data_size_bytes - 1. The whole structure and data are in one linear block.

Note that a structure with a flexible member can't be used as an array element type.

Before the ISO C standard added the flexible array member in 1999, this was done as a popular "struct hack" using an array of size 1. If you're constrained to working in C90 it goes like this:

struct ListNode {
  struct ListNode *next;
  char data[1];
};

Now sizeof ListNode includes the one element array, and quite likely padding for alignment. For instance on a system with four byte pointers, the size is quite likely eight. If we use the same malloc line, we will allocate excess memory. The right malloc expression to use for the C90 struct hack:

#include <stddef.h>

struct ListNode *node = malloc(offsetof(struct ListNode, data) + data_size_bytes);

Unlike the flexible array member feature, the struct hack doesn't have formally well-defined behavior; it's just something that "works if it works".

Kaz
  • 55,781
  • 9
  • 100
  • 149