Self Referential Structure in C

Why do we require a Self-referential structure?

Self-referential structures, typically implemented using pointers, are essential in C for several reasons. They enable the creation of dynamic data structures like linked lists and trees, accommodating changing data sizes during program execution. These structures are vital for representing complex data with nested or recursive elements, such as binary trees. 

Self-referential structures also optimize memory usage by allowing efficient representation of interconnected data, as each element points to others of the same type. Moreover, they provide flexibility in designing data structures that can adapt to different requirements, making them a fundamental concept in C programming.

Types of Self Referential Structure in C

There are two types of self referential structure in C

• Linear Self Referential Structure: These structures create a linear data structure such as stacks, queues and linked lists. In this, each member points to the next member sequentially. 

• Non Linear Self Referential Structure: These structures create a non linear data structure, such as trees and graphs. In this, each member can point to many members.

Examples to understand each type of Self Referential Structure in C

In this section, we will understand the self referential structure in C with the help of examples

Example 1

Here is an example of a linked list, a linear self referential structure implemented using a self-referential structure.

• C

C

#include <stdio.h>
#include <stdlib.h>

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

void display(struct Node* temp)
{
	while (temp) {
	printf(" %d ", temp->data);
	temp= temp->next;
	}
}

void main()
{
	// assign each node a null value to avoid any refrence error
	struct Node* head =NULL;
	struct Node* second_node = NULL;
	struct Node* third_node = NULL;

    // defining three nodes
	head = (struct Node*)malloc(sizeof(struct Node));
	second_node = (struct Node*)malloc(sizeof(struct Node));
	third_node = (struct Node*)malloc(sizeof(struct Node));

	head->data = 10; // assign data in first node
	head->next = second_node; // Link first node with second

	second_node->data = 200; // assign data to second node
	second_node->next = third_node;

	third_node->data = 3000; // assign data to third node
	third_node->next = NULL;

	// calling the function to display value 
	display(head);
}

You can also try this code with Online C Compiler

Run Code

Output:

In the above code, we have created a struct node that contains data and a pointer named next to store next node address. We define 3 nodes here, assign them values, and use the display() to print the value of each node. In display(), the while condition will run till we encounter a null node.

Example 2

Here is an example of a binary tree, a non-linear self-referential structure implemented using a self referential structure.

• C

C

#include<stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};
struct node* createNode(int data) {
    struct node *newNode= (struct node *)malloc(sizeof(struct node));
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
void inorder(struct node *temp) {
	// traverse untill root is NULL
    if(temp)
    {
        inorder(temp->left);
        printf("%d ", temp->data);
        inorder(temp->right);
    }
    else
    return;
}
void main() {
     // create root node
    struct node *root= createNode(10);  

    //making links to child nodes 
    root->left= createNode(100);
    root->right= createNode(200);

    // making further connections
    root->left->left= createNode(300);
    root->left->right= createNode(400);
    root->right->left= createNode(500);
    root->right->right= createNode(600);
    
    printf("In Order Traversal of Binary Tree \n");
   // calling inorder traversal function
    inorder(root);
}

You can also try this code with Online C Compiler

Run Code

Output:

In the above code, we have made a binary tree using createNode function which is used to create a new node and then we performs a inorder traversal of the tree. In the inorder function, the while condition will run until we get a null node.

Also read,  Short int in C Programming

Applications of Self Referential Structure in C

So now, we shall discuss some important features of the Self Referential Structure in C.

• Defining dynamic data structures: Self referential structures define dynamic data structures such as linked lists, trees, and graphs, where the structures can be modified at runtime.
   
• Connecting nodes/structures: Self referential structures can also connect nodes in various data structures. In a linked list, we have a pointer variable next that stores the following node address or links consecutive nodes, and tree's parent root is connected to its children.
   
• Representing relationships: Self-referential structures can also show relationships among different elements in a data structure. For example, in a binary tree, each node represents a parent-child relationship between nodes, while in graphs, we have adjacent node relationships with each other.
   
• Iterating through a data structure: Self-referential structures can be used to iterate through data structures as we have the pointer which stores the address of the next node so we can iterate by following the pointers from one element to another. It is instrumental in searching and sorting algorithms and can also be used to traverse data structures like a linked list. 
  Also read - Bit stuffing program in c

Frequently Asked Questions

Q1. What is an example of a self-referential statement?

"This statement is false" is a self-referential statement because it refers to and describes itself.

Q2. What is an example of a self-referential relationship?

In databases, a self-referential relationship occurs when a table has a foreign key that references its own primary key.

Q3. What is an example of self-referential literature?

"Miguel de Unamuno's 'Mist' where the author interacts with his characters, acknowledging the fictional nature of the narrative."

Q4. What is the self-referential structure?

In programming, a self-referential structure is a data structure like a linked list where each node contains a reference to another node of the same type.

Conclusion

This article has explained the fundamentals of self referential structure in C. It has also given examples of self referential structure implemented in code and discussed its applications.

We hope this blog has helped you. We recommend you visit our articles on different topics of C, such as

• Bubble Sort Program in C
• Ternary Operator in C
• Difference between structures in C and C++
• Structure of C program
• structure and functions
   

Check out The Interview Guide for Product Based Companies and some famous Interview Problems from Top Companies, like Amazon, Adobe, Google, etc., on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

We hope you found this blog helpful in expanding your knowledge. Please give this article a thumbs up if you enjoyed it.