linked list - 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.