Self Referential Structure in C

What is a Self-Referential Structure?

A self-referential structure is a struct that includes a pointer to an instance of the same structure type. This design allows structures to reference other structures of the same kind, forming chains or hierarchical relationships.​

Syntax:

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

In this example, next is a pointer to another Node, enabling the creation of linked structures.​

Why Use Self-Referential Structures?

Self-referential structures are important in programming for the following reasons:

• Flexible Memory Use: They help create structures that can change size while the program is running.
• Building Blocks for Complex Structures: These structures are the foundation for linked lists, trees, graphs, and other dynamic models.
• Efficient Memory Management: Memory is used only when needed, which helps avoid unnecessary waste.

Types of Self-Referential Structures in C

1. Singly Linked Structure

Each node contains data and a pointer to the next node.​

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

2. Doubly Linked Structure

Each node contains data and pointers to both the previous and next nodes.​

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

3. Tree Structure

Each node contains data and pointers to its child nodes.​

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

Practical Example: Creating a Singly Linked List

#include <stdio.h>
#include <stdlib.h>
 
struct SFNode {
    int topicID;
    struct SFNode* nextTopic;
};
 
int main() {
    // Allocate memory for nodes
    struct SFNode* intro = (struct SFNode*)malloc(sizeof(struct SFNode));
    struct SFNode* arrays = (struct SFNode*)malloc(sizeof(struct SFNode));
    struct SFNode* pointers = (struct SFNode*)malloc(sizeof(struct SFNode));
 
    // Assign values and link nodes
    intro->topicID = 101;
    intro->nextTopic = arrays;
 
    arrays->topicID = 102;
    arrays->nextTopic = pointers;
 
    pointers->topicID = 103;
    pointers->nextTopic = NULL;
 
    // Traverse and print the list
    struct SFNode* current = intro;
    while (current != NULL) {
        printf("Sanfoundry Topic ID: %d\n", current->topicID);
        current = current->nextTopic;
    }
 
    // Free memory
    free(intro);
    free(arrays);
    free(pointers);
 
    return 0;
}

Output:

Sanfoundry Topic ID: 101
Sanfoundry Topic ID: 102
Sanfoundry Topic ID: 103

This program uses self-referential structures in C to create a linked list. The SFNode structure has two fields: topicID and nextTopic (a pointer to the next node). Three nodes are created: intro, arrays, and pointers, each linked to the next. The program prints the topic IDs and frees the memory after use.

Common Mistakes to Avoid

1. Declaring a Pointer Inside a Structure Without the struct Keyword:

Incorrect:

struct Node {
    int data;
    Node *next; // Error: 'Node' is not defined
};

Fix: Use the struct keyword when declaring a pointer to the structure:

struct Node {
    int data;
    struct Node *next; // Correct
};

2. Including the Structure Inside Itself:

Incorrect:

struct Node {
    int data;
    struct Node next; // Error: Infinite recursion
};

Fix: Use a pointer to the structure instead to avoid infinite memory allocation:

struct Node {
    int data;
    struct Node *next; // Correct
};

3. Not Initializing Pointers:

Always initialize pointers to NULL or a valid memory address before use to avoid undefined behavior. Uninitialized pointers can lead to serious bugs, such as accessing invalid memory.

Fix:

int *ptr = NULL; // Always initialize

4. Memory Leaks:

If you allocate memory dynamically using malloc() or similar functions, make sure to free the memory when you’re done to prevent memory leaks. Failing to free memory leads to wastage and can crash your program.

Fix:

free(ptr); // Always free dynamically allocated memory

Applications of Self-Referential Structures

• Linked Lists: Self-referential structures are the backbone of singly, doubly, and circular linked lists, where each node points to the next (and/or previous) node.
• Trees: Used in binary trees, BSTs, heaps, and other hierarchical structures, where each node contains pointers to child nodes.
• Graphs: Help in creating adjacency lists where nodes store pointers to other connected nodes, making traversal efficient.
• Stacks and Queues: Dynamic implementations of stacks (LIFO) and queues (FIFO) are commonly built using self-referential structures for flexible memory usage.
• Memory Management Systems: Custom memory allocators or garbage collectors often use self-referential structs to keep track of free memory blocks in a linked list format.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.