Aquarius TheGirl Aquarius TheGirl - 17 days ago 5
C Question

Understanding a structure which contains a pointer of its own type

struct node
int info;
struct node *llink;
struct node *rlink;

typedef node *nodep;

What does it mean to have a structure's pointer inside that structure itself?

Please explain the above structure in detail.


I am NOT talking about the trees logic. I am talking about the C struct and the pointer's behaviour.


struct node *llink
How does the memory gets allocated to this? This is a type which hasn't yet come into existence?


A pointer is just a reference to a location in memory ("address"). In the case of a node, a pointer to an instance of a node is a reference to the location in memory where that node instance is stored.

For your struct as defined, if you have an instance of a node that resides in one memory location, it can point to two other node instances that reside in their own memory locations (*llink, *rlink).

Using a real-world tree as a metaphor, the *llink and *rlink are pointers to left and right "branches" of a root node of a tree structure, respectively. Those pointers themselves may branch off into further and deeper left and right "subtrees".

Have a read of this introduction to binary trees.

binary tree