Size of a linked list node

Question

I find this thing a little tricky and recursive as to how sizeof operator calculates the size of one node in a linked list. I've the below structure as one node in list for example:

struct ll_core
{
    char c_ll;
    struct ll_core * next;
};

printf("size of struct ll_core = %d\n\n",sizeof(struct ll_core));

it gives me an answer 8. Now how does it decides the size 8, because to add sizes of individual struct element it agains encounter the same struct ll_core. So it's a kind of loop or recursion while calculating size. Please excuse me and let me know if I'm missing any basic thing in my head while thinking like this.

Answer 1

It doesn't need the size of the struct again, since the struct only contains a pointer to the struct, not the struct itself.

The size of "pointer to struct ll_core" has nothing to do with size of struct ll_core, they are two distinct types. One is pointer, the other one isn't.

You can't declare a "truly" recursive data structure, since it would be infinite.

Answer 2

because to add sizes of individual struct element it agains encounter the same struct ll_core.

No, it encounters a pointer to a struct ll_core. If it encountered the struct itself, that would lead to infinite sizes. The compiler knows the size and alignment requirements of a struct ll_core * even without knowing anything about struct ll_core, so it can add the sizes of the members plus the padding required for alignment (of the next member in this case) to find the size of the struct ll_core.

Answer 3

Assuming you are running your code on 32 bit machine, size of pointer will be 4 bytes. As structure will be aligned on word boundary, 3 bytes will be padded and so the size will be 8 bytes.

this structure will actually be like,

struct ll_core{
    char       c_11:
    char const byte[3];  //padded bytes for alignment reasons
    struct ll_core *next;
};

Answer 4

struct ll_core
{
    char c_ll;
    struct ll_core * next;
};

sizeof operator adds the size of the member of the structure ll_core. Here it is a character (c_ll) and a pointer(next).

A little more information about how the size is calculated.

Structure Padding:

In a 64 bit system, data will read and written as 8 byte chunks. So when the size of the structure is calculated, padding happens. Means compiler will insert some gaps between the members of the structure to "align" to the architecture address boundaries. Something as follows:

struct ll_core
{
    char c_ll;
    /* 7 bytes of padding */
    struct ll_core * next;
 };

So the size of this structure in a 64-bit system will be 16 bytes.

Structure Packing:

You can prevent compiler from doing structure padding by doing structure packing. In GCC, it is done like this:

struct __attribute__((__packed__)) ll_core
{
    char c_ll;
    struct ll_core * next;
};

Now the size would be 9 bytes on a 64 bit machine.

sizeof(char) + sizeof(pointer)

Edit - From your question it seems you are running on a 32-bit machine. In a 32-bit machine, data will be read and written as 4 byte chunks.

Answer 5

Many processors work better if certain types are aligned on certain addresses. This means that the compiler pads your structure after the single char element so that the pointer is on a native word boundary.

As for the "recursion" in the structure, there is none because the next field is a pointer to the structure and not the structure itself.

Answer 6

you are missing the point, look carefully... 'next' is just a pointer. you cannot do just 'struct ll_core next'..that is without *. So, as long as it is a pointer. The size will be calculated for the size of the pointer only. In general, the pointer size is 4.

If you have any confusion, remove the * from next and try compiling the code.

Answer 7

There 2 elements are a char (size 1) and a pointer (size 4), so you'd think the size would be 5 but structures are padded to 4 bytes (word size). The char is padded to 4 bytes giving a total of 8.