3

Why do we use pointers in self-referential structs? It is obligatory or not? If not, what advantages does us having a pointer to struct in struct versus normal struct definition give?

typedef struct _Struct {
  struct _Struct* next;  // do we really need this pointer?
} Struct;
anonymoose
  • 1,169
  • 2
  • 21
  • 62
Anton Barinov
  • 183
  • 1
  • 3
  • 13
  • 8
    If a structure contains an instance of itself, then its size is infinity. – user3386109 Jan 29 '18 at 21:09
  • @user3386109 Only if it contains at least one additional field. Otherwise it would just be an infinite nest whose terminal fields would be inaccessible. – Tom Karzes Jan 29 '18 at 21:16
  • The member `next` is an odd name for a "self-referential structs". Perhaps post the context in which you see `struct _Struct` being used. I think the context you actually see is a linked-list. – chux - Reinstate Monica Jan 29 '18 at 21:52

3 Answers3

6

Pointer has fixed size, so compiler can determine the size of the struct _Struct when parsing it.

If _Struct contains itself physically, there is no way to determine its size, it's a cyclic definition.

llllllllll
  • 16,169
  • 4
  • 31
  • 54
  • 1
    so, there is no way to use it without pointer? – Anton Barinov Jan 29 '18 at 21:15
  • 1
    @AntonBarinov: If _Struct contained _Struct and a 32-bit integer it's size would be 4 bytes + _Struct. But now that's 8 bytes. No, wait, 12 bytes, 16 bytes, etc ... This is why a pointer of fixed size must be used. – Zan Lynx Jan 29 '18 at 21:18
  • 3
    @AntonBarinov: A member of a C structure is physically part of the structure, occupying as much memory as it would if it were defined as a separate variable. A structure can't contain an instance of itself. (You might be accustomed to other languages, in which a structure member of a structure is implemented as an implicit reference. C doesn't do that.) – Keith Thompson Jan 29 '18 at 21:19
  • @ZanLynx thanks a lot. – Anton Barinov Jan 29 '18 at 21:20
  • thanks everyone for explanations. – Anton Barinov Jan 29 '18 at 21:22
3

It makes no sense for a structure to contain a member that is an instance of the outer struct. In addition to requiring that you declare an incomplete type, it would be infinite and would never have enough bytes because each instance you add will also need an instance.

Using a pointer is no problem; however, and this approach is often use to create linked lists, for example. The pointer points to the next instance in a chain.

Jonathan Wood
  • 65,341
  • 71
  • 269
  • 466
2

You can't use the struct _Struct type member variable in the structure definition because it must be a complete type to do that. But struct _Struct is not complete until the declaration's } is met.

But for pointer we can do that because size of pointer is same be it a pointer to a complete type or incomplete one - so when compiler is reading them, it can decided it's size. (unlike the case where it is referring itself).

It has to be pointer not the structure itself because the type is not complete yet - it is not known what it's size will be.

Backing up what I said - From standard §6.7.2.1p3

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.

Also when is it complete? From §6.7.2.1p8

The presence of a struct-declaration-list in a struct-or-union-specifier declares a new type, within a translation unit. The struct-declaration-list is a sequence of declarations for the members of the structure or union. If the struct-declaration-list does not contain any named members, either directly or via an anonymous structure or anonymous union, the behavior is undefined. The type is incomplete until immediately after the } that terminates the list, and complete thereafter.

If anybody asks what is incomplete type for struct or union? From standard §6.2.5p22

A structure or union type of unknown content (as described in 6.7.2.3) is an incomplete type.

That is why the we cant use an instance of the struct which is being declared - because simply it's size is not possible to know.

user2736738
  • 30,591
  • 5
  • 42
  • 56