Why dynamic allocation (linked lists/trees), c

Question

I get confused why you use dynamic allocation and the concept of allocating enough memory for the data. So we are covering linked lists in my class and there is this code:

NODE *BuildTree(NODE *p, const char *str)
{
    if (p == NULL)
    size_t length = strlen(str) + 1;
    p = (NODE *)malloc(sizeof(NODE));
    p->string = (char *)malloc(length);
    ....
}

typdef struct Node NODE;
struct NODE
{
    char *string;
    size_t count;
    NODE *left, *right;
};

The code is supposed to create a tree with strings that is entered from the user. I am assuming you dynamically allocate the NODE because you obviously do not know how many children you are going to need. But then, why do you need to alocate the size for the string str that is goign to be entered? Or is that done because of the way the struct is defined and you want to allocate the exact amt, vs if the struct said size_t count[50], and just had wasted memory. Is that the idea? Thanks!

Answer 1

You are dynamically allocating the string because you do not know the size of the string at compile time. You are dynamically allocating the nodes because you do not know how many nodes you need at compile time.

Basically, any time you do not know how much memory an object will use at compile time, you need dynamic allocation. I think it is possible to stick the string at the end of the node structure and do the whole thing in one dynamic allocation (so that the entire node is one contiguous blob of data).

Answer 2

The string is allocated because they are using a char* and the number of characters depends on what is being placed in the string.

If your professor did char blah[50]; you'd give it enough memory for 50 characters. So I assume he wants to allow someone to enter more then a static amount of characters.

Notice your professor's code:

size_t length = strlen(str) + 1;
p = (NODE *)malloc(sizeof(NODE));
p->string = (char *)malloc(length);

strlen is giving the length of a string and add one to it for the terminating character. Now length can be set to the size of the entire string, that is your professor can now allocate enough character bytes for the size of the string, in this case (length).

Answer 3

You need to allocate the size of the string because thats the actual data being stored in the node when it's created. The children of the node are just pointers to other nodes and are only taking up the size of the pointer inside each node

Answer 4

Your understanding is correct. If the strings entered by the user are of unknown length, then it is difficult at best to specify the size up front. If the maximum size were known, it could be declared as char string[N];. But, as you say, that can waste memory if there is a large variation in size. On the other hand, a benefit of creating the pre-defined size is that it can result in fewer allocations, which is sometimes beneficial.