Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Self Referential Structure in C?
2.1.
Syntax of Referential Structure in C is:-
3.
Why do we require a Self-referential structure?
4.
Types of Self Referential Structure in C
5.
Examples to understand each type of Self Referential Structure in C
5.1.
Example 1
5.2.
C
5.3.
Example 2
5.4.
C
6.
Applications of Self Referential Structure in C
7.
Frequently Asked Questions
7.1.
What is the need for implementing Self referential structure in C?
7.2.
What is the difference between a self referential structure in C and a recursive function in C?
7.3.
What are some of the most common errors to avoid while using self-referential structures in C?
7.4.
How to Deallocate the memory allocated to self referential structure in C?
7.5.
How self referential structures lead to infinite loops?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Self Referential Structure in C

Author Dhruv Rawat
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Hello, Ninja. Have you ever wondered how data structures like trees and linked lists are implemented in C? All this is done by using self referential structures. 

This article will show how self referential structure in C is defined and used with their practical applications. Whether you are a beginner in C or an expert, this article will help you understand the fundamentals of self-referential structure.

self referential structure in C

What is Self Referential Structure in C?

A Self referential structure is a structure that contains a member that points to the same type of structure. It is also called linked structure or recursive structure. Self referential structure in C is handy for creating complex data structures like linked lists, graphs and trees.

Syntax of Referential Structure in C is:-

The syntax of referential structure in C is:-

struct node{
	// any data variable  
    int data;
	// struct node pointer storing next node address
    struct node *link;
};

 

The struct contains two members in this above code, data and link. The link is a pointer pointing to the same struct node type. This makes the node a self referential structure.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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. 
linear self referential structure
  • 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.
non linear self referential structure

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);
}

Output:

output for linked list

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);
}

Output:

output for inorder traversal of binary tree

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

What is the need for implementing Self referential structure in C?

Self referential structure makes it easier to implement complex data structures that are present, like linked lists, graphs and trees. Also, they can represent the recursive and hierarchical nature of complex objects.

What is the difference between a self referential structure in C and a recursive function in C?

In self referential structures, the variable of the same structure type appears as its members. In a recursive function, the objective is that the function calls itself several times during the execution of a program. Recursive functions solve complex problems by breaking them into smaller sub-problems, while self referential structures define complex data types like linked lists and graphs.

What are some of the most common errors to avoid while using self-referential structures in C?

Most common would be not initially initialising the pointer to a NULL value and forgetting to dereference the NULL pointers. Circular references should be taken care of as they can lead to infinite loop errors. Managing memory allocation and deallocation while using self referential structure is necessary to avoid memory leaks.

How to Deallocate the memory allocated to self referential structure in C?

To deallocate memory from a self referential structure in C, we can do it by using the “free” function. The free function frees up any memory allotted by “malloc” or other similar function. To free up the memory, traverse the structure from the head node and then free each subsequent node.

How self referential structures lead to infinite loops?

When creating a self referential structure like a circular linked list with circular reference, the last node points to the first node itself. In that case, if you forget to check for the condition of the circular reference, you will iterate it infinite times, leading to an infinite loop condition.

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

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

Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test SeriesInterview 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. 

"Have fun coding!"

Live masterclass