What are Self Referential Structures in C- C Programming Course With Examples

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Free C Programming Course · Structure and Union · Lecture 27

Self Referential Structures in C

A structure that points to another structure of its own type is the secret behind linked lists, trees and packet queues. Learn it step by step in this free C tutorial for embedded systems.

Every real embedded program eventually needs data that grows and shrinks while it runs: a queue of received packets, a list of connected Bluetooth devices, a chain of pending timer events. Fixed arrays cannot do that gracefully. The tool C gives you is the self referential structure in C, a structure that contains a pointer to another structure of the same type. This lecture of our free C programming course and free embedded C course explains the idea slowly, with a program you can run.

What You Will Learn

  • What a self referential structure is and why it is legal in C
  • Why a structure cannot contain itself, but can contain a pointer to itself
  • How one link member builds a chain, and two link members build a tree
  • How to follow links with the arrow operator
  • How big these structures are, and why the pointer size matters on embedded targets
  • Typical mistakes that cause crashes in embedded C programming

Prerequisites

You need structures, the dot and arrow operators, and the basics of pointers and NULL. If you have followed the previous lectures of this free C tutorial, you are ready.

What Is a Self Referential Structure?

A self referential structure is a structure that has, among its members, at least one pointer whose type is a pointer to that very structure. The structure does not hold a copy of another record inside itself. It holds the address of another record somewhere else in memory.

struct pkt {
    int id;
    unsigned int len;
    struct pkt *next;   /* pointer to the same type */
};

Think of each struct pkt as an index card. The card carries its own data (id and len) plus a note saying where the next card is kept. You never need to know how many cards exist in advance. Follow the notes and you reach all of them.

Three packet descriptors chained by their next pointer
id 101 | len 8next →id 102 | len 64next →id 103 | len 20next = NULL

Why a Pointer and Not the Structure Itself?

You might wonder why we cannot write a member of type struct pkt inside struct pkt. The compiler would need to know the size of the structure to lay it out, but the size would include another full copy of itself, which includes another copy, and so on forever. The size would be infinite, so the compiler rejects it.

A pointer breaks the cycle. Whatever structure it points to, a pointer is always one fixed size: 4 bytes on a typical 32-bit microcontroller and 8 bytes on a 64-bit PC. The compiler knows the pointer size even though the structure is not yet finished, and that is why the self pointer is allowed.

Member inside struct pktLegal?Reason
struct pkt next;Nosize would be infinite
struct pkt *next;Yesa pointer has a fixed size
struct other o; (a completed type)Yesordinary nested structure

Remember

Inside its own definition the structure is an incomplete type. You may declare pointers to it, but you may not create objects of it or take sizeof of it until the closing brace.

One Link, Two Links

How many self pointers you add decides what you can build.

  • One link (next) gives a singly linked list: a line of records.
  • Two links along the same line (next and prev) give a doubly linked list, which can be walked both ways.
  • Two links to children (left and right) give a binary tree, used for fast searching.
struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
};
Same idea, different shapes
list nodedata + 1 linka line of records
tree nodedata + 2 linksbranching records

Following Links With the Arrow Operator

If p points to a struct pkt, then p->id reads its id and p->next is the pointer to the following record. Because p->next is itself a pointer to a structure, you can chain the arrow: p->next->id reads the id of the second record. The end of a chain is marked by a NULL pointer, so a loop that walks the chain stops when it sees NULL.

for (p = &a; p != NULL; p = p->next)
    printf("pkt id=%d len=%u\n", p->id, p->len);

Complete Program: Build and Run

Save this as selfref.c. It links three ordinary variables into a chain, with no dynamic memory yet, so you can focus on the pointer idea alone.

#include <stdio.h>

struct pkt {
    int id;
    unsigned int len;
    struct pkt *next;
};

struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
};

int main(void)
{
    struct pkt c = { 103, 20, NULL };
    struct pkt b = { 102, 64, &c };
    struct pkt a = { 101, 8,  &b };
    struct pkt *p;

    printf("sizeof(struct pkt)   = %zu\n", sizeof(struct pkt));
    printf("sizeof(struct tnode) = %zu\n", sizeof(struct tnode));
    printf("sizeof(struct pkt *) = %zu\n", sizeof(struct pkt *));

    for (p = &a; p != NULL; p = p->next)
        printf("pkt id=%d len=%u\n", p->id, p->len);

    printf("b.next->id = %d\n", b.next->id);
    printf("a.next->next->len = %u\n", a.next->next->len);
    return 0;
}
$ gcc -Wall -Wextra -o selfref selfref.c
$ ./selfref

Expected output on a 64-bit Linux PC:

sizeof(struct pkt)   = 16
sizeof(struct tnode) = 24
sizeof(struct pkt *) = 8
pkt id=101 len=8
pkt id=102 len=64
pkt id=103 len=20
b.next->id = 103
a.next->next->len = 20

Reading the sizes

struct pkt holds a 4-byte int, a 4-byte unsigned int and an 8-byte pointer: 16 bytes in total. struct tnode has a 4-byte key, then padding so that the first pointer starts on an 8-byte boundary, then two 8-byte pointers: 24 bytes. On a 32-bit Cortex-M the pointers shrink to 4 bytes, so the same struct pkt would be 12 bytes. Always let sizeof tell you.

Real-World Uses

Embedded use caseWhat each node represents
UART or BLE receive queueone received packet descriptor
Software timer listone pending timer, ordered by expiry
RTOS ready listone task waiting to run
Menu system on a small displayone menu item with child and sibling links
File system directory entriesone entry linking to the next

Common Mistakes

  • Leaving the link uninitialised. A local structure that is not initialised holds a random pointer. Always set next to NULL when you create a record.
  • Dereferencing NULL. Writing p->next->id when p->next is NULL crashes the program. Check before you follow.
  • Linking to a local variable that dies. If a function links a node that lives on its stack and then returns, the pointer now refers to memory that is gone. Records that must outlive a function belong in static storage or on the heap.
  • Using the structure tag before it exists. Inside the structure, use struct pkt * with the full tag. A typedef name is not available until after the closing brace.
Embedded caution: many safety-critical coding standards discourage malloc. When you build linked structures on such targets, take nodes from a fixed pool of preallocated records instead. The pointer logic you learn here stays exactly the same.

Best Practices

  • Name the link member by its meaning: next, prev, left, right, parent.
  • Initialise every link when the node is created.
  • Keep the data members first and links last, or follow one consistent order across your project.
  • Draw the structure on paper before writing code. Boxes and arrows prevent most pointer bugs.

Suggested Images for This Lecture

Image ideaALT text
Three boxes connected by arrows labelled nextself referential structure in C free C programming course diagram
Comparison of list node and tree nodefree C tutorial linked list node versus tree node in embedded C
Terminal output of the selfref programself referential structure program output free embedded C course

Key Takeaways

  • A self referential structure holds a pointer to its own type, never the structure itself.
  • The fixed size of a pointer is what makes the definition legal.
  • One link makes lists, two links make trees or doubly linked lists.
  • Follow links with -> and stop at NULL.
  • Initialise links and never dereference NULL.

Conclusion

Self referential structures look like a small trick, but they are the doorway to every dynamic data structure in C. Once you are comfortable with a structure pointing to its own kind, linked lists become a natural next step rather than a mystery. In the next lecture of this free C programming course we will give the idea a name and a shape: the linked list, with its start pointer and its chain of nodes, and we will compare it honestly with plain arrays for embedded C programming.

Frequently Asked Questions

What is a self referential structure in C?

It is a structure with at least one member that is a pointer to the same structure type, used to connect records into lists and trees.

Why can a structure not contain itself?

Its size would have to include itself, which is infinite. A pointer has a fixed size, so a pointer to the same type is allowed.

Where are self referential structures used in embedded systems?

In packet queues, timer lists, RTOS task lists, menu trees and driver data structures.

What is the difference between a list node and a tree node?

A list node usually has one link to the next node. A binary tree node has two links, left and right.

Does sizeof a self referential structure change between PC and microcontroller?

Yes. Pointer size is 8 bytes on a 64-bit PC and typically 4 bytes on a 32-bit Cortex-M, so the structure size can differ. Padding also depends on the compiler.

What does NULL mean in the next member?

It marks the end of the chain: there is no following node.

Continue the Free Embedded C Course

Next up: the linked list, built from the self referential nodes you just learned.

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →