Self-referential structure in C
Self-referential structure in C
A self-referential structure is a structure that can have members which point to a structure variable of the same type. They can have one or more pointers pointing to the same type of structure as their member. The self-referential structure is widely used in dynamic data structures such as trees, linked lists, and so on. The next node of a node will be pointed in linked lists, which consists of the same struct type. It is a unique type of structure containing a member of its type. The member of its type is a pointer variable of the same structure in which it has been declared. In the context of blockchain, each block is linked to a previous node or a next node, similar to a linked list.
Syntax:
struct structure_name
{
datatype datatype_name;
structure_name * pointer_name;
}
E.g.:
struct node
{
int data;
struct node *next;
};
Where ‘next’ is a pointer to a struct node variable, it should be remembered that the pointer to the structure is similar to the pointer to any other variable. Hence, a self-referential data structure is generally a structure definition that includes at least one member that is a pointer to the structure of its kind.
The self-referential structures are beneficial in many applications that involves linked data members, such as trees and lists. Unlike a static data structure such as an array where the size of the array limits the number of elements that can be inserted into the array, the self- referential structure can dynamically be contracted or expanded. Operations such as insertion or deletion of nodes in a self-referential structure involve simple alteration of the pointers present within them.
E.g.:
typedef struct list
{
void *data;
struct list *next;
}linked_list;
Here, in the above example, the list is self-referential structure as the *next is the type struct list.
struct node
{
int data;
char value;
struct node * link;
};
int main()
{
struct node object;
return 0;
}
In this particular example, ‘link’ is a pointer to f type ‘node’ structure. Hence, the structure ‘node’ is a self-referential structure with ‘link’ as a referencing pointer. The pointer should be appropriately initialized before accessing, as by default, it contains a garbage value.
Types of self-referential structures
- Self-referential structure with a single link: these structures are allowed to have only one self-pointer as their member.
E.g.:
#include <stdio.h>
#include <conio.h>
struct ref
{
int data;
char val;
struct ref* link;
}
int main()
{
struct ref object1; //link1
object1.link = NULL;
object1.data = 10;
object1.val = 20;
struct ref object2; //
object2.link = NULL;
object2.data = 30;
object2.val = 40;
object1.link = &object2;
printf (“%d \n”, object1.link -> data);
printf (“%d \n”, object1.link -> val);
return 0;
}
Output:
30 40
- Self-referential structure with multiple links: these types of structures can have more than one self-pointers. Many complicated data structures can be easily constructed using these structures. Such structures can easily connect to more than one node at a time.
E.g.:
#include <stdio.h>
#include <conio.h>
struct ref
{
int data;
struct ref* previous;
struct ref* next;
};
int main()
{
struct node object1;
object1.previous = NULL;
object1.next = NULL;
object1.data = 10;
struct prev object2;
object2.previous = NULL;
object2.next = NULL;
object2.data = 20;
struct prev object3;
object3.previous = NULL;
object3.next = NULL;
object3.data = 30;
object1.next = &object2;//forward links
object2.next = &object3;
object2.next = &object1;//backward links
object3.next = &object2;
printf (“%d \t”, object1.data);
printf (“%d \t”, object1.next -> data);
printf (“%d \n”, object1.next -> next -> data);
printf (“%d \t”, object2.prev -> data);
printf (“%d \t”, object2.data);
printf (“%d \n”, object2.next -> data);
printf (“%d \t”, object3.prev -> prev -> data);
printf (“%d \t”, object3.prev -> data);
printf (“%d \n”, object3.data);
return 0;
}
Output:
10 20 30 10 20 30 10 20 30
Here object1, object2, and object3 are three objects of self-referential structure ‘node’. They are connected by links in a way any other object can access each other’s data. Connections can be manipulated by a developer according to their requirements. The self- referential structure has its applications in data structures such as stacks, queues, binary trees, lists, graphs, etc.