CODEWITHSUNDEEP
cdata-structures
SeasonalShot
SeasonalShot

Reputation: 2569

Structure type in C

I have a very basic question. In C, we declare a structure like so:

Snippet 1:

struct node {
    int a;
    int b;
    char c;
};

I understand the basic concept behind structures. It can be viewed from many angles. It's a "structure", it is used to create a user defined type.

A structure is useless unless we define objects for it. We can create objects for it like so:

struct node obj1;
obj1.a=10; // corresponds to the value of obj1
obj1.c='A'; // ....
and so on..

Okay, Now this following code snippet I cannot understand.

Snippet 2:

struct node {
    node* left;
    node* right;
    int value;
};
  1. How can we define node* left and node* right in the structure named node when the structure node hasn't even been completely formed yet?
  2. What does it even mean? How can it point to something that hasn't even been formed yet?
  3. How does it even know the size of the object to allocate when we create an object of node?

Can anyone help me out on this?

Edit: The code in the question is not valid C code, but it is valid C++ code

Upvotes: 3

Views: 122

Answers (2)

nerez
nerez

Reputation: 447

Adding to the previous answer.

First you need to understand this What is the difference between a definition and a declaration? Self referencing is a feature programming languages offer. It gives the user (the programmer) flexibility in building data types (graphs, linked list and many more).

Self referencing is using the fact that pointers could be declared and only be defined later. It sounds a little far fetched for the beginner, but the reason that is that pointers have a fix size of 4 bytes. Therefore, the compiler already knows how much memory to allocate for it and it assumes the pointer will be declared later on.

Hope I made it clearer

Upvotes: 2

doptimusprime
doptimusprime

Reputation: 9395

How can we define node* left and node* rightin the structure named node when the structure node hasn't even completely formed yet?

  • node * is pointer and a pointer does not require complete definition. Only declaration of type is enough.

What does it even mean? How can it point to something that hasn't even been formed yet?

  • Such structures are known as self-referencing. They can refer to the an object which (must)have same type as they have. This is one of the basis of linked list, trees, graph and many data structure.

How does it even know the size of the object to allocate when we create an object of node?

  • As object contains pointer, size of pointer is fixed and is known before knowing the complete object. Hence, size of object can be allocated. In this case, it will be size of data members+size of pointers+some padding.

Upvotes: 4

Related Questions