What is self-referencing structure in C?

Question

struct LinkedList  
{  
    int data;
    struct LinkedList *next;
};

In the code, within the definition of struct LinkedList there is a pointer to the structure itself.

How does it work?

Answer 1

So, the code

struct LinkedList  
{  
    int data;
    struct LinkedList *next;
};

defines a struct type containing two members named data and next, with the next member storing the address of a different object of the same type. Given the code:

struct LinkedList Node1 = { .data = 1, .next = NULL };
struct LinkedList Node0 = { .data = 0, .next = &Node1 };

you get something that sort of looks like this:

Node0              Node1
+---+--------+    +---+------+
| 0 | &Node1 |--->| 1 | NULL |
+---+--------+    +---+------+

(Note that you would never create a linked list this way, this is just for illustration).

This is possible for two reasons:

1. C allows you to declare pointers to incomplete types;
2. Pointers to struct types all have the same size and representation.

This is an example of a self-referential data type, which simply means that the type stores a reference (pointer) to a different object of the same type.

Answer 2

What you talk about are recursive data structrues and the question is how to let a data structure reference itself.

In C this can be done by declaring a pointer to itself in the definition of the data structure, "self" meaning a thing of its own type.

Note that when you write the expression, the data structure is not yet complete. Therefore it is not possible to let a data structue contain an occurence of itself, for once because the definition is not yet completely known and for two because the data strutcure would be never ending containing an occurrence of itself, itself,...

But you can declare a pointer to itself. The compiler now only allocates storage for the pointer and if you later assign/dereference the pointer it knows the storage pointed to contains an occurrence of itself. That is what you do in your example.

Answer 3

A self-referential pointer which points to the address of whatever it is a part of. So for example,

typedef struct node {     
   char data[30]; 
   struct node *this; 
   struct node *next; 
} Node; 

*this is a self-referential pointer if it is assigned to whatever is applied to.

,and

Clearly a Cell cannot contain another cell as it becomes a never-ending recursion.

However a Cell CAN contain a pointer to another cell.

Refer this post as well.