C/C++: How can a structure contain a pointer pointing to itself?

Question

The question is more of theory-based than practical implementation.

What I would like to know is, in the code:

struct temp {
    int num;
    struct temp *next;
};

In the structure made above, how does the compiler decide how much of space should be allocated in memory when we instantiate it?

If I try to dry-run the code, the size of an integer would be 2 or 4 bytes, after that, if I try to find the size of the pointer to the structure itself, I enter a structure containing another integer and a pointer to itself.

By this logic, the compiler would enter an infinite loop when deciding to allocate space to an element of this structure, how then is the space decided?

P.S. I did try to find out the size of this structure myself (using the sizeof() operator, it turned out to be 16 bytes (the size of the integer being 4 bytes)... I'm interested in knowing how did it determine this figure of 16 bytes as the space required!

A pointer's size doesn't depend on the type of object it points to. The situation you describe is something like `struct temp { int num; struct temp next; };` which is, as you explain, not possible to resolve. — François Andrieux, Dec 03 '18 at 17:40
The memory has to be allocated at runtime. The compiler doesn't need to know the structure's size to allocate a pointer. — πάντα ῥεῖ, Dec 03 '18 at 17:40
16 bytes: 4 for the `int` and probably 8 for the pointer. the extra 4 are padding for [alignment](https://stackoverflow.com/questions/381244/purpose-of-memory-alignment). — user4581301, Dec 03 '18 at 17:43
The size of a pointer to some type T and the size of T are unrelated. — melpomene, Dec 03 '18 at 17:44
[`this` is what you want. `this` is what you get.](https://www.youtube.com/watch?v=O0bk6Hbz0ZU) — user4581301, Dec 03 '18 at 19:24

score 6 · Answer 1 · answered Dec 03 '18 at 17:49

A structure containing a pointer to itself is not a problem.

A pointer has a fixed size, so it doesn't matter how big the size of the structure it points to is. On most systems you're likely to come across, a pointer will be either 4 bytes or 8 bytes in size.

For the struct you've given, the int field will probably use 4 bytes and the struct temp * field will probably use 8 bytes. This means the struct will be at least 12 bytes in size, probably 16 due to padding for proper alignment.

If on the other hand you had something like this:

struct temp {
    int num;
    struct temp next;
};

This would not be legal because the struct contains a copy of itself, which would in turn contain a copy of itself, and so on.

score 2 · Accepted Answer · edited Jun 20 '20 at 09:12

In the structure made above, how does the compiler decide how much of space should be allocated in memory when we instantiate it?

Pointer types take up a fixed size, which is not dependent on the pointed-to type (IOW, the size and representation of struct temp * is not in any way dependent on the size or representation of struct temp). Furthermore, all pointer to struct types have the same size:

6.2.5 Types
...
28 A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.⁴⁸⁾ Similarly, pointers to qualified or unqualified versions of compatible types shall have the same representation and alignment requirements. All pointers to structure types shall have the same representation and alignment requirements as each other. All pointers to union types shall have the same representation and alignment requirements as each other. Pointers to other types need not have the same representation or alignment requirements.

^{C 2011 online draft}

On platforms like x86, all pointer types have the same size and representation, but the standard has to take oddball architectures into account.

It's no different than if you had a pointer to int or pointer to void as a member. The only thing that makes it look weird is that you're creating a self-referential pointer, which is allowed:

6.7.2.1 Structure and union specifiers
...
3 A structure or union shall not contain a member with incomplete or function type (hence, a structure shall not contain an instance of itself, but may contain a pointer to an instance of itself), except that the last member of a structure with more than one named member may have incomplete array type; such a structure (and any union containing, possibly recursively, a member that is such a structure) shall not be a member of a structure or an element of an array.

^ibid.

Even though the struct type itself is not complete until the closing } of the definition, any pointer to it is complete (that is, its size is known).

The size of the pointed-to type matters for pointer arithmetic (i.e., the address value resulting from p + 1 will depend on the size of the thing p points to). However, it doesn't matter for storing the pointer itself.

C/C++: How can a structure contain a pointer pointing to itself?

2 Answers2