3

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

SeasonalShot
  • 2,357
  • 3
  • 31
  • 49
  • 1
    A pointer does not need the whole class/struct definition. He just needs a simple declaration like `struct node;`. – Blacktempel Apr 02 '15 at 04:46
  • 1
    The size of a pointer is not related to the size of the object it points to, in the same way as you don't need a bigger envelope to send a letter to Buckingham Palace than to your neighbour, since the addresses are the same size.. – rici Apr 02 '15 at 04:49
  • @rici Yes precisely, the size of a pointer would be the same. Then why not use the int *p or char *p? That is another way we can store the address. But int a=10; [NOT THIS(int *p=&a);] char *p=&a; p is a pointer to an char (and if we ignore the de-referencing part which in this case will point to an char. ) we can very well store the pointer address like this,can we not? – SeasonalShot Apr 02 '15 at 04:55
  • 1
    @SeasonalShot: Without getting into obscure corners of the standard, you could use `void*` for all pointers and explicitly cast them on use. Once upon a time (in C's predecessor, B, for example) that was exactly what was done, but for many decades it has been considered useful to identify what a pointer points at; it helps to avoid stupid bugs even if it is not necessary for the low level implementation. – rici Apr 02 '15 at 05:04
  • 1
    (To correct my comment above, it is possible that an implementation will require a wider pointer for a narrower object, in order to implement character pointers on a machine which only has word addresses. Such implementations are probably about as common as modern uses of the C predecessor I referred to, but they are still contemplated by the C standard. – rici Apr 02 '15 at 05:06
  • @rici That's something new i didn't know before. Have to look it up .Thanks – SeasonalShot Apr 02 '15 at 05:10
  • You say you're asking about C. Why do you have the "c++" tag? – Keith Thompson Apr 02 '15 at 05:14
  • This c++ tag is relative. We have structures in c++ as well and the concept behind structures in c is same as c++ ,Even though structures are native to C, they are also available in c++ . That is why the C++ tag is relevant to this question. – SeasonalShot Apr 02 '15 at 05:25
  • 1
    @KeithThompson: The C++ tag is relevant because the code is not valid (self-contained) C code, but it is valid C++ code. The type `node` referenced in the second structure is not, in C, the `struct node` type but some other typedef type, or it is a compilation error if there is no type `node` already defined. In C++, the name `node` does refer to the `node` defined by `struct node`. This is a subtle difference between the two languages. I initially removed the C++ tag because the question specifically asks about C in the title, but then replaced when I noticed that the code was C++ and not C. – Jonathan Leffler Apr 02 '15 at 06:28
  • 1
    @JonathanLeffler: I'm not convinced that the OP was aware of that. SeasonalShot: There is a relevant difference between C and C++ here. In C, defining `struct node { ... }` only lets you refer to the type as `struct node`; if you want to refer to it as `node`, you need a `typedef` in addition to the struct definition. In C++, a type defined as `struct node { ... }` can be referred to either as `struct node` or as `node` (the latter is generally preferred). You code, since it refers to the type as `node`, appears to be valid C++ but *not* valid C. You need to be aware of that. – Keith Thompson Apr 02 '15 at 17:23
  • @KeithThompson Thank you for the constructive suggestion. I have made an edit to my question. – SeasonalShot Apr 02 '15 at 17:26

2 Answers2

4

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.
doptimusprime
  • 9,115
  • 6
  • 52
  • 90
  • I think i am getting your answer, and it makes perfect sense and it totally agrees to my concept. however The only reason and existence of a node pointer is to point something to it's type (in this case node) right? @rici's comment gave me clarification to some level but i don't think i totally understand it yet. – SeasonalShot Apr 02 '15 at 05:09
  • Yes. It is to point something of its own type. To understand, try to implement linked list and understand its concept. – doptimusprime Apr 02 '15 at 05:59
  • You really need to point out that the code in the question is not valid C code, but it is valid C++ code. See also my comment to the main question. – Jonathan Leffler Apr 02 '15 at 06:43
2

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

Community
  • 1
  • 1
nerez
  • 437
  • 4
  • 18