- The main benefit of creating structure is that it can hold the different predefined data types.
- It is initialized with the struct keyword and the structure's name followed by this struct keyword.
- We can easily take the different data types like integer value, float, char, and others within the same structure.
- It reduces the complexity of the program.
- Using a single structure can hold the values and data set in a single place.
- In the C++ programming language, placing struct keywords is optional or not mandatory, but it is mandatory in the C programming language.
- Self-referential structure plays a very important role in creating other data structures like Linked list.
- In this type of structure, the object of the same structure points to the same data structure and refers to the data types of the same structure.
- It 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, etc.
Why do we require a Self-referential structure?
Self-referential design is crucial in various data structures like linked lists, trees, and graphs. This design enables the efficient implementation of these structures. The structure is particularly significant in defining individual nodes. In the context of a linked list, this structure is utilized to hold both the data and the reference to the next node in the list. Typically, the data component is of integer type, while the link address component is of pointer type. The pointer stores the address of the subsequent node, facilitating the formation of the overall linked structure.
As it's commonly understood, a linked list serves the purpose of storing elements of identical types, where the addresses are not in consecutive order. Within this linear linked list, each node contains the address of the subsequent node, thereby establishing a connection between the current node and the following one.
Here within the linked list, we establish a standard format that includes both the data and a pointer to store the address of the subsequent node. This enables the creation of multiple nodes by utilizing the defined node structure for each node.
Unlike a fixed data structure like an array, which has a set size restricting the number of elements that can be efficiently added, a self-referential structure is capable of dynamically growing or shrinking as needed.
Modifying a self-referential structure by adding or removing nodes typically requires adjusting pointers in a direct manner.
Linked list
- A linked list is a useful data storage method, and it is very easy to implement it in C programming Language.
- Several kinds of linked lists, including single linked lists, double linked lists, and binary trees.
- Each type is suited for certain types of data storage.
- The one thing that these lists have in common is that the links between data items are defined by the information contained in the items themselves, in the form of pointers.
- The linked list is distinctly different from arrays, in which the links between data items result from the layout and storage of the array.
Here, we will discuss the self-referential structure in more detail using the linked list concepts.
Let's understand the concept of self-referential structure in more detail using the example mentioned below:
Example 1: Creating a random self-referential structure in the C programming language.
// Dummy Self-referential structure in C language
struct node // Creating a node of structure type contains data
// part of integer type and a pointer of structure type to
// hold the address of the next node
{
int d1 ; // data 1 of integer type
int d2 ; // data 2 of integer type
struct node * link ; // Self referential structure link is pointing the same
// structure of the type node
} ;
Int main()
{
Struct node obj; // Creating an object of the node type, this object is // consists of three parts one is data 1 and
// second is of data 2, and third is of link type pointer
// carries the address of the next node.
Return 0 ;
}
Example 2: Creating a random self-referential structure in a python programming language.
# Dummy Self-referential structure in python language
class node: # Creating a node that contains data
# part of and a pointer of node type to
# hold the address of the next node
def __init__(self):
self.data1=0
self.data2=' '
self.link=None # Self-referential structure link is pointing the same
# structure of the type node
if __name__ == '__main__':
ob=node()
# Creating a object of node type, this object is
# consists of three parts one is data 1 and
# second is of data 2 and third is of link type pointer
# carries the address of the next node
Types of self-referential structure
- Single Link self-referential structure
- Multiple Link self-referential structures
Single Link self-referential structure
As the name suggests, we can easily predict that these structures consist of a single Link, mainly the only one pointer link of structure type pointing to the same structure. To better understand it, we can connect this concept with the singly linked list.
In a singly linked list, there is only a single pointer that carries the address of the next node, and thaLogic Practiceer variable is of the structure node type itself. It is mainly used when we want to store the different data items by fetching out them from various addresses and connecting all of them by storing the address of one data item into the linked part of the other node. In this way, we can easily connect all the data items by using these connecting links.
Examine the functionality of a solitary link self-referential structure through an illustration:
// Single link self-referential structure implementation in C language
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info ;
struct node *link ; // Self-referential structure link is pointing the same
// structure of the type node
};
struct node *START = NULL ; // starLogic Practiceer to control the linked list //
struct node* createnode() ;
void insertatlast() ; // insert node at last //
void deleteatfirst() ; // delete node at first //
void viewlist() ;
void insertatfirst() ;
int getlength() ;
int menu() ;
void insertafteranynode() ;
void deleteatlast() ;
void deleteatposition() ;
struct node* createnode() // create node dynamically //
{
struct node *n ;
n = malloc( sizeof(struct node) ) ;
return ( n ) ;
}
void insertatlast()
{
struct node *temp ,*t ;
temp = createnode() ;
printf( "Enter the data in node \n " ) ;
scanf( " %d" , &temp->info ) ;
temp->link = NULL ;
if ( START == NULL )
START = temp ;
else
{
t = START ;
while ( t->link != NULL )
{
t = t->link ;
}
t->link = temp ;
}
}
void deleteatfirst() // delete node at first //
{
if ( START == NULL )
printf ( "List is empty \n " ) ;
else
{
struct node *q ;
q = START ;
START = START->link ;
free( q ) ;
}
}
void viewlist()
{ struct node* t ;
if ( START == NULL )
{
printf ( "No List \n " ) ;
}
else
{
t = START ;
while ( t != NULL )
{
printf ( " %d" , t->info ) ;
t = t->link ;
}
}
}
void insertatfirst()
{ struct node*New ;
New = createnode() ;
printf ( "Enter the data in node \n " ) ;
scanf ( " %d" , &New->info ) ;
if ( START == NULL )
START = New ;
else
{
New->link = START ;
START = New ;
}
}
int getlength()
{
int count = 0 ;
struct node* t ;
if ( START == NULL )
printf ( "List is empty \n " ) ;
else
{
t =START ;
while ( t != NULL )
{
count = count + 1 ;
t = t->link ;
}
}
return count ;
}
void insertafteranynode()
{
int position ;
struct node* newnode ,*t ;
if ( START == NULL )
printf ( "List is empty \n " ) ;
else
{
printf ( "Enter position after which you want to add: \n " ) ;
scanf ( " %d" , &position ) ;
if ( position > getlength() )
{
printf ( "Wrong position \n " ) ;
insertafteranynode() ; // recursion //
}
else
{
int i = 1 ;
newnode = createnode() ;
printf ( "Enter Data \n " ) ;
scanf ( " %d" , &newnode->info ) ;
newnode->link = NULL ;
if ( START == NULL )
START = newnode ;
else
{
t = START ;
while ( i < position )
{
t = t->link ;
i++ ;
}
newnode->link = t->link ;
t->link = newnode ;
}
}
}
}
void deleteatlast()
{
struct node* t , *q ;
if ( START == NULL )
{
printf ( "List is empty \n " ) ;
}
else
{
t = START ;
q = START ;
while ( t->link != NULL )
{
q = t ;
t = t->link ;
}
if ( t == START )
{
START == NULL ;
}
else
{
q->link = NULL ;
free( t ) ;
}
}
}
void deleteatposition()
{
struct node *t , *q ;
int position , i = 1 ;
t = START ;
if ( START == NULL)
{
printf ( "List is empty \n " ) ;
}
else
{
printf ( "Enter position after which you want to delete: \n " ) ;
scanf ( " %d" , &position ) ;
if ( position > getlength() )
{
printf ( "Wrong position \n " ) ;
deleteatposition() ; // recursion //
}
else
{
while ( i < position )
{
q = t ;
t = t->link ;
i++ ;
}
if ( t == START )
{
START == NULL ;
}
else
{
q->link = t->link ;
free( t ) ;
}
}
}
}
int menu()
{
int ch ;
printf ( " \t \t \t 1.ADD NODE LAST IN LINK \n " ) ;
printf ( " \t \t \t 2.ADD NODE AT FIRST IN LINK \n " ) ;
printf ( " \t \t \t 3.VIEW LIST IN LINK \n " ) ;
printf ( " \t \t \t 4.DELETE NODE AT FIRST IN LINK \n " ) ;
printf( " \t \t \t 5. TO SEE THE LENGTH OF LIST \n " ) ;
printf ( " \t \t \t 6. INSERT NODE IN BETWEEN \n " ) ;
printf ( " \t \t \t 7.DELETE NODE AT LAST IN LINK \n " ) ;
printf ( " \t \t \t 8.DELETE NODE AT SPECIFIC POSITION IN LINK \n " ) ;
printf ( " \t \t \t 9.EXIT \n " ) ;
printf ( "ENTER THE CHOICE \n " ) ;
scanf ( " %d" , &ch ) ;
return( ch ) ;
}
void main()
{ int k ;
while ( 1 )
{
switch ( menu() )
{
case 1 :
insertatlast() ;
break ;
case 2 :
insertatfirst() ;
break ;
case 3 :
viewlist() ;
break ;
case 4 :
deleteatfirst() ;
break ;
case 5 :
k = getlength() ;
printf ( "THE LENGTH OF THE LIST IS %d \n " , k ) ;
break ;
case 6 :
insertafteranynode() ;
break ;
case 7 :
deleteatlast() ;
break ;
case 8 :
deleteatposition() ;
break ;
case 9 :
exit( 0 ) ;
break ;
default :
printf ( " Not available \n " ) ;
}
}
}
The output of the above program is:
[Program Output]
[Program Output]
# Single link self-referential structure implementation in Python language
class node:
def __init__(self):
self.d1=0
self.d2=0
self.link=None
if __name__ == '__main__':
obj1=node() # Node1
# Initialization
obj1.link = None
obj1.d1 = 17
obj1.d2 = 14
obj2=node() # Node2
# Initialization
obj2.link = None
obj2.d1 = 36
obj2.d2 = 24
# Linking obj1 and obj2
obj1.link = obj2
# Accessing data members of obj2 using obj1
print(obj1.link.d1)
print(obj1.link.d2)
The output of the above program is:
36
24
Multiple Link self-referential structures
As implied by its name, these particular structures are composed of numerous links. In this scenario, we will employ a pair of pointer links of the structure type, both pointing to the identical structure. To grasp this concept more effectively, we can draw parallels with a doubly-linked list.
In a doubly-linked list, a pair of single pointers hold the memory location of the next node and the previous node, and the pointer variable is of the node structure type. This is particularly beneficial when organizing diverse data elements from different locations and linking them by storing one data item's address in another node's linked section. Through this method, it becomes effortless to establish connections between all data items using these linking references.
Let's examine how a self-referential structure with multiple links functions through an illustrative example:
// Multiple link self-referential structure implementation in C language
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info ;
struct node *prev ; // Self-referential structure link is pointing the same
// structure of the type node but to the previous node
struct node *next; // Self-referential structure link is pointing the same
// structure of the type node but to the next node
} ;
struct node * START = NULL ; // StarLogic Practiceer of the list and initially it must be null, // represents that no node is present
void insertnodeatfirst() ;
void deleteatfirst() ;
void viewlist() ;
int menu() ;
void insertnodeatfirst() // Inserting the node at first
{
struct node * newnode ;
newnode = malloc( sizeof( struct node ) ) ;
printf ( "Enter Data: \n " ) ;
scanf ( " %d" , &newnode->info ) ;
newnode->prev = NULL ;
newnode->next = NULL ;
if ( START == NULL )
START = newnode ;
else
{
START->prev = newnode ;
newnode->next = START ;
START = newnode ;
}
}
void deleteatfirst() // deleting the first node
{
struct node * temp ;
if ( START == NULL )
printf ( "List is empty \n " ) ;
else
{
temp = START ;
START = START->next ;
START->prev = NULL ;
free( temp ) ;
}
}
void viewlist() // displaying all the nodes in the list
{
struct node * t ;
if ( START == NULL )
printf ( "List is empty \n " ) ;
else
{
t = START ;
while ( t != NULL )
{
printf ( " %d \n " , t->info ) ;
t = t->next ;
}
}
}
int menu()
{ int n ;
printf ( " \t \t \t 1. VIEW LIST \n " ) ;
printf ( " \t \t \t 2. INSERT AT FIRST IN LIST \n " ) ;
printf ( " \t \t \t 3. DELETE AT FIRST IN LIST \n " ) ;
printf ( " \t \t \t 4. EXIT \n " ) ;
printf ( "ENTER YOUR CHOICE \n " ) ;
scanf ( " %d" , &n ) ;
return ( n ) ;
}
int main()
{
while ( 1 )
{
switch ( menu() )
{
case 1 :
viewlist() ;
break ;
case 2 :
insertnodeatfirst() ;
break ;
case 3 :
deleteatfirst() ;
break ;
case 4 :
exit ( 1 ) ;
break ;
default :
printf ( " NOT AVAILABLE \n " ) ;
}
}
}
The output of the above program is:
[Program Output]
# Multiple link self-referential structure implementation in Python language
class node:
def __init__(self):
self.data = 0
self.prev = None
self.next = None
if __name__ == '__main__':
obj1=node() # Node1
# Initialization
obj1.prev = None
obj1.next = None
obj1.data = 15
obj2=node() # Node2
# Initialization
obj2.prev = None
obj2.next = None
obj2.data = 20
obj3 = node() # Node3
# Initialization
obj3.prev = None
obj3.next = None
obj3.data = 25
# Forward links
obj1.next = obj2
obj2.next = obj3
# Backward links
obj2.prev = obj1
obj3.prev = obj2
# Accessing data of obj1, obj2 and obj3 by obj1
print(obj1.data , end='\t')
print(obj1.next.data , end='\t')
print(obj1.next.next.data)
# Accessing data of obj1, obj2 and obj3 by obj2
print(obj2.prev.data , end='\t')
print(obj2.data , end='\t')
print(obj2.next.data)
# Accessing data of obj1, obj2 and obj3 by obj3
print(obj3.prev.prev.data , end='\t')
print(obj3.prev.data , end='\t')
print(obj3.data)
The output of the above program is:
15 20 25
15 20 25
15 20 25
