At this point in the course, you're comfortable with structs as a way to group related data. But real-world data rarely fits into a neat, flat box. Usually, data is either hierarchical—like a user profile that contains an address—or recursive, like a file system where a folder can contain other folders. This is where nested and self-referential structures come in.

The Infinite Size Paradox

I want to show you a mistake I see almost every beginner make when they first try to build a linked list. They think of a "Node" as something that simply contains a value and another "Node." It feels logically sound, so they write something like this:

struct Node {
    int data;
    struct Node next; // This is the mistake
};

If you try to compile this, your compiler is going to throw a fit. Why? Because the compiler needs to know exactly how many bytes a struct Node occupies in memory. But if a Node contains a Node, which contains a Node, and so on, the structure is infinitely large. It's a recursive definition that never terminates. You've essentially told C to create a box that must be large enough to hold itself, which is a physical impossibility in memory.

Breaking the Loop with Pointers

The fix is subtle but fundamental: we don't store the actual structure inside itself; we store a pointer to it. This is the core of a self-referential structure.

struct Node {
    int data;
    struct Node *next; // This works perfectly
};

Now, the compiler is happy. Why? Because regardless of what struct Node looks like, a pointer is always a fixed size (usually 4 or 8 bytes). We aren't nesting the box; we're putting a note inside the box that tells us where to find the next box. This allows us to build chains of data—linked lists, trees, or graphs—that can grow and shrink at runtime on the heap, rather than being locked into a fixed size on the stack.

Rigid Nesting vs. Dynamic Linking

Self-reference is for when you don't know how many elements you'll have. But what about when you do know the relationship is fixed? For example, let's say we're building a game engine. Every Entity has a Position. You could just put the X, Y, and Z coordinates directly in the Entity struct, but that's messy. Instead, we nest a Vector3 struct inside the Entity struct.

struct Vector3 {
    float x, y, z;
};

struct Entity {
    int id;
    char name[32];
    struct Vector3 position; // Nested structure
};

The trade-off here is about memory layout. By nesting Vector3 directly (by value) rather than using a pointer, the position data is stored contiguously with the id and name. When the CPU loads an Entity into the cache, it grabs the position data at the same time. If we had used a pointer to a Vector3, the CPU would have to jump to a different location in memory, which is a "cache miss" and slows your program down. I generally recommend nesting by value whenever the relationship is "is-a-part-of" and the size is fixed.

When the Nesting Gets Too Deep

While nesting is great for organization, be careful not to create a "Matryoshka doll" of structs that is five or six levels deep. If you find yourself writing player->stats->attributes->strength->current_value, you've gone too far. Not only is it a pain to type, but you're creating a rigid dependency chain. If you ever need to move strength to a different part of the system, you'll have to rewrite every single line of code that accesses it. If the data doesn't have a strict, permanent ownership relationship, stick to pointers and keep your hierarchy shallow.

📋 Practical Task

Implementing a Simple Undo History Stack

In this exercise, you will build a basic "Undo" system for a text editor. Instead of storing a full document, we will store "Change" objects. Each change will point to the change that happened immediately before it, creating a self-referential chain (a stack).

Your task:

• Define a struct called Change that contains an integer change_id and a pointer to the previous Change struct.
• Write a function push_change that takes the current "head" of the history and a new ID, allocates a new Change node on the heap, links it to the previous head, and returns the new head.
• Write a function pop_change that removes the most recent change and returns the previous head to the caller, ensuring you properly free() the memory of the removed node.
• In main, simulate three edits (IDs 101, 102, 103), then "undo" two of them, and print the ID of the current active change.