The Gateway to Computer Science Excellence
+1 vote
I have learnt that self-referential structure is one which contains a structure of same type in it as an element. 
But I have a doubt regarding how that line is compiled successfully (i.e, how compiler knows how much space should 
be allocated and its elements)when the definition of that structure is not yet finished?  

struct node {
      int data;
      struct node *next;

correct me If I am wrong in understanding this.

in Programming by Junior (779 points) | 205 views
The memory space is created when an object is declared of the type structure and not when we define a structure.
but how the datatype is identified when it is not defined.?

I am not sure but

when we write the struct keyword then the compiler knows that we are creating a datatype named 'node' and whatever will be inside { } will be its element.

so when you write

struct node *next;

the compiler checks whether we are

creating a datatype named node or whether the datatype named node is already defined.

here we are creating the datatype node so the compiler says Ok.

Then it defines the pointer named *next of struct node type.

when the } comes and compiler sees ; then it understands that we have finished defining the datatype and then the new datatype named node is created.

Ok, but I am not convinced with the answer. how does it work?
yes I am also not sure thats why I have written it in comments
Memory is not allocated when we define a structure. We are just telling prototype to the compiler. Memory is allocated when we actually create variable.

That's why we can't initialise structure variables.

2 Answers

+1 vote

Memory allocation is not always done at compilation.

  • Global and static variables are allocated fixed size in the data section at the time of compilation and hence mostly there sizes need to be declared at the time of compilation itself.
  • Local variables to a function are not allocated space at the time of compilation. It is done at execution on the program stack section.
  • The self referential structures which you are talking about is mostly created dynamically using malloc function, in this case the space is allocated in the heap section at runtime dynamically.
  • Considering your code:
struct node {
      int data;                // memory is allocated to this
      struct node *next;      // memory is allocated only to this pointer not to the node pointed by it 
  • The compiler only provides space enough to store ' int data' and  a pointer 'next'. The location for next itself is not located. It has to be created again using a different malloc call and should be assigned to this previous node's next pointer.


by (187 points)
0 votes
I think in view of memory allocation, while allocation only the data type is important. So the variable 'next' in your example is nothing but a pointer and in most architectures all pointers are of same size (it may vary on some architecture).

But you can always know the space needed to be allocated from the data type, which is here of type pointer to structure. You need not know anything about the data items within structure.
by (41 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
105,321 users