Self Referential Structure
Explain structure.
A structure is a user defined data type, which groups a set
of data types. It is a collection of variables of different type
under single name. A structure provides a convenience to
group of related data types. A structure can contain
variables, pointers, other structures, arrays or pointers. A
structure is defined with the keyword ‘struct’
Ex:
struct employee
{
int empid;
char name[20];
float salary;
};
..
..
struct employee Ram;
Structures:
Structures provide a convenient method for handling
related group of data of various data types.
Structure definition:
struct tag_name
{
data type member1;
data type member2;
…
…
}
Example:
struct library_books
{
char title[20];
char author[15];
int pages;
float price;
};
The keyword struct informs the compiler for holding fields (
title, author, pages and price in the above example). All
these are the members of the structure. Each member can
be of same or different data type.
The tag name followed by the keyword struct defines the
data type of struct. The tag name library_books in the
above example is not the variable but can be visualized as
template for the structure. The tag name is used to
declare struct variables.
Ex: struct library_books book1,book2,book3;
The memory space is not occupied soon after declaring
the structure, being it a template. Memory is allocated only
at the time of declaring struct variables, like book1 in the
above example. The members of the structure are
referred as - [Link], [Link], [Link],
[Link].
Self Referential Structures
Self Referential structures are those structures that have one or
more pointers which point to the same type of structure, as their
member.
In other words, structures pointing to the same type of
structures are self-referential in nature.
struct node {
int data1;
char data2;
struct node* link;
};
int main()
{
struct node ob;
return 0;
}
• In the above example ‘link’ is a pointer to a structure of type
‘node’. Hence, the structure ‘node’ is a self-referential
structure with ‘link’ as the referencing pointer.
• An important point to consider is that the pointer should be
initialized properly before accessing, as by default it contains
garbage value.
Types of Self Referential Structures
[Link] Referential Structure with Single Link
[Link] Referential Structure with Multiple Links
Self Referential Structure with Single Link:
These structures can have only one self-pointer as their
member. The following example will show us how to connect
the objects of a self-referential structure with the single link and
access the corresponding data members.
#include <stdio.h>
struct node {
int data1;
int data2;
struct node* link;
};
int main()
{
struct node ob1; // Node1
// Initialization
[Link] = NULL;
ob1.data1 = 10;
ob1.data2 = 20;
struct node ob2; // Node2
// Initialization
[Link] = NULL;
ob2.data1 = 30;
ob2.data2 = 40;
// Linking ob1 and ob2
[Link] = &ob2;
// Accessing data members of ob2 using ob1
printf("%d", [Link]->data1);
printf("\n%d", [Link]->data2);
return 0;
}
Output:30
40
Self Referential Structure with Multiple Links:
Self referential structures with multiple links 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 nodes at a time. The following
example shows one such structure with more than one links.
The connections made in the above example can be understood
using the following figure.
#include <stdio.h>
struct node {
int data;
struct node* prev_link;
struct node* next_link;
};
int main()
{
struct node ob1; // Node1
// Initialization
ob1.prev_link = NULL;
ob1.next_link = NULL;
[Link] = 10;
struct node ob2; // Node2
// Initialization
ob2.prev_link = NULL;
ob2.next_link = NULL;
[Link] = 20;
struct node ob3; // Node3
// Initialization
ob3.prev_link = NULL;
ob3.next_link = NULL;
[Link] = 30;
// Forward links
ob1.next_link = &ob2;
ob2.next_link = &ob3;
// Backward links
ob2.prev_link = &ob1;
ob3.prev_link = &ob2;
// Accessing data of ob1, ob2 and ob3 by ob1
printf("%d\t", [Link]);
printf("%d\t", ob1.next_link->data);
printf("%d\n",ob1.next_link->next_link->data);
// Accessing data of ob1, ob2 and ob3 by ob2
printf("%d\t", ob2.prev_link->data);
printf("%d\t", [Link]);
printf("%d\n", ob2.next_link->data);
// Accessing data of ob1, ob2 and ob3 by ob3
printf("%d\t", ob3.prev_link->prev_link->data);
printf("%d\t", ob3.prev_link->data);
printf("%d", [Link]);
return 0;
}
Output:
10 20 30
10 20 30
10 20 30
In the above example we can see that ‘ob1’, ‘ob2’ and ‘ob3’
are three objects of the self referential structure ‘node’. And
they are connected using their links in such a way that any
of them can easily access each other’s data. This is the
beauty of the self referential structures. The connections can
be manipulated according to the requirements of the
programmer.
Applications:
Self referential structures are very useful in creation of other
complex data structures like:
•Linked Lists
•Stacks
•Queues
•Trees
•Graphs etc
Thanks