self referential structures

This C Tutorial explains Self-Referential Structures in C Programming with examples.

Consider the structure declaration below,

struct NODE {
             struct NODE new;    /* 'new' declared variable */
             int value;
    };

As we know that structure template tells compiler how to allocate storage to its members and makes computer not to allocate memory to them. When compiler reaches the line

    struct NODE new;

template struct NODE is not fully defined. Further, its member ‘new’ of type struct NODE contains a member ‘new’ of type struct NODE which in turn contains a member ‘new’ again of type struct NODE and so on indefinitely. In such an instance, compiler can’t evaluate correctly how much storage to allocate to ‘new’ member of template struct NODE. So we observed here that a member of struct NODE can’t be a variable of type struct NODE. Then, how can we make structure struct NODE self-referential? Let’s take one more try, this time we declare a ‘pointer-to-struct NODE’ as a member of template struct NODE,

struct NODE {
             struct NODE *new;    /* 'new' a pointer-to-struct NODE */
             int value;
    };

As compiler starts compiling the template struct NODE and reaches line

    struct NODE *new;

it finds ‘new’, a ‘pointer-to-struct NODE’, and also member of struct NODE template, it evaluates correctly how much bytes of storage to be allocated to ‘new’. On linux system, any pointer type takes 8 bytes of storage. There’s no problem in using ‘pointer-to-struct NODE’ as a member of struct NODE. Because ‘new’ is a ‘pointer-to-struct NODE’, structure struct NODE is called self-referential structure.

typedef struct NODE {
             struct NODE *new;
             int value;
    }Node;
 
int main(void)
{
    Node previous, current;
 
    /* accessing members of 'previous' */
    previous.new = &current;
    /* previous.new is a 'pointer-to-struct NODE' */
    previous.value = 100;
}

In above fragment of code, ‘previous.new’ is pointing to ‘current’ Node.
Self-referential structures have their applications in Advanced Data Structures like, Linked Lists, Binary Trees etc..