3

I have a question regarding structures definition and pointers.

In the definition of linked list node structure we define the structure as follows:

typedef struct node
{
    int data;
    struct node *next;
}Node;

Why whould we use this way of declaration instead of:

typedef struct node
{
    int data;
    struct node next; //changed this line
}Node;

Thanks in advance!

Nimrod Naim
  • 145
  • 9
  • 1
    Does this answer your question? [Why use pointers?](https://stackoverflow.com/questions/162941/why-use-pointers) – John3136 Dec 27 '19 at 09:43
  • 1
    Because you need to define something (completely) first before creating a variable of that type but you can have a pointer because the compiler already knows there is a `struct node` (the definition of which is incomplete) when you reach line `4`. The size of an incomplete data type is unknown to the compiler but the size of a pointer is always same for a given arch. – babon Dec 27 '19 at 09:45
  • 1
    even if it's allowed to declare a struct inside itself then the size of the struct is undeterminable because it depends on how many levels of structs are nested – phuclv Dec 27 '19 at 09:46
  • 1
    You can have a pointer to an incomplete type, but you cannot have an instance of an incomplete type. – machine_1 Dec 27 '19 at 09:47
  • 1
    If this was somehow possible to declare, the resulting struct would be infinitely recursive. A node contains a node which contains a node, etc. forever. It would be infinite size. – TrentP Dec 27 '19 at 09:48
  • Note that the second code snippet implies infinite recursion. – machine_1 Dec 27 '19 at 09:48

3 Answers3

1

A structure is defined after its closing brace. Until it a structure has an incomplete type. But a definition of a structure requires that all its members except a flexible array shall have complete types.

So in this declaration

typedef struct node
{
    int data;
    struct node next; //changed this line
}Node;

the data member next has an incomplete type.

From the C Standard (6.7.2.1 Structure and union specifiers)

  1. ...The type is incomplete until immediately after the } that terminates the list, and complete thereafter.

and

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.

As for pointers then they always have complete types because their sizes are known.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
  • Suppose you had a reference to another type of struct there? Would it be preferable to have a pointer because otherwise the struct will take up more space? – Alex Leibowitz Sep 12 '22 at 16:55
  • @AlexLeibowitz It depends on the context. For example the structure node instead of the scalar data member data can contain an object of a structure type as for example person. – Vlad from Moscow Sep 12 '22 at 16:57
1

Actually we do that because, we avoid the recursive call. Suppose think your second case. You call node inside a node itself. So what is the sizeof the node. sizeof(int) + sizeof(node). Then again for the node the size become sizeof(int)+sizeof(node). So this is a unstoppable recursive process. So we use the first case because avoid the recursive process. It just point to the object of same type structure.

MANJURUL HAQUE
  • 146
  • 10
1

The compiler needs to determine the size of whatever it is that comes its way.

This needs completeness in definition, so that a determined calculation can be made.

In the first case of self referential structure, we have a pointer. A pointer is os struct node * type has a definite size determined by the architecture.

In the second case - struct node next, what would be the size of next? Would it be the size of struct node? Okay, let's say it is, but then again - what is the size of struct node? Well, the answer is sizeof(int) + sizeof(struct node). Okay, but then again... wait...what??... go back and read this entire para again, and realize the catch-22 situation here...

The compilers won't and don't appreciate this!

Siddharth
  • 321
  • 1
  • 5