What is Self Referential Structure in C++?

What is Self Referential Structure in C++?

Self-referential structure in C++ are those structure that contains one or more than one pointer as their member which will be pointing to the structure of the same type. In simple words, a structure that points to the structure of the same type is known as a self-referential structure.

Self-referential structures are mainly used for the implementation of dynamic data structures like tree, linked list, etc.

Structures are non-primitive data type which is used to hold different pre-defined or primitive data types like int, float, double, etc. Structures in C++ are initialized by using the struct keyword followed by the name of the structure. The structure reduces the overall complexity of the C++ program.

In C++, the struct keyword is not mandatory before the declaration of a variable. In C, it is mandatory to use the struct keyword.

Declaration

Let's see how we can declare a self-referential structure in C++:

In the above declaration, *next is the pointer of the node type pointing to the same type of structure.

Example

Let's take a simple example to understand the concept of self-referential structure more clearly:

Code

Example Explanation

In the above example, we have defined a structure node having a variable of int type and a pointer of the node type, that's why the structure is a self-referential structure. Inside the main method the object of the node i.e, obj is accessing the members of the structure. The value of the pointer is initialized by NULL so that the pointer should not contain any garbage value.

Types of Self-Referential Structures

There are two types of self-referential structure which are as follows:

1. Self Referential Structure with Single Link
2. Self-Referential Structure with Multiple Links

Now, Let's discuss them in detail with simple examples.

Self-Referential Structure with Single Link

A structure is said to be a self-referential structure with a single link if it contains only one pointer link as a member, pointing to the same structure. This structure contains only one link.

Let's take an example to understand the concept of a single link in self-referential structure:

Code:

Output

Example Explanation:

In the above program, we have defined a self-referential structure having next pointer and a variable data of int type. Inside the main method, we have declared two objects named obj1 and obj2. The value of data members inside the structure is initialized with the use of objects. At first, the value of the pointer has been initialized as NULL and then the reference of obj2 is passed to the next pointer of obj1. Now, the members of obj2 can be accessed by obj1 using which we are printing the value of data related to obj2 using obj1.

Self-Referential Structure with Multiple Links

A structure is said to be a self-referential structure with multiple links if the structure contains more than one pointer link as a member, pointing to the same structure. They are used in the implementation of many complicated data structures.

Let's take a look at an example to understand the concept of self-referential structure with multiple links:

Code:

Output

Example Explanation

In the above program, we have created three objects of the self-referential structure node. These objects are connected by multiple links using pointers of the same type so that they can access each other's data values. The above links can be handled according to the needs of the programmer.

Why Do We Require a Self-Referential Structure?

Self-referential structures are used to implement dynamic data structures like linked lists, trees, graphs, etc. These structures play an important role in efficiently implementing them.

In data structures like a linked list, it is used to store data of the same type where the address at which the data will be stored is not continuous.

The self-referential structure has an important role in defining the nodes of a linked list. It holds the data part which is of integer type and a pointer that contains the address of the next node or next data location and therefore forming a link between the current node and the next node.

Unlike static data structures like arrays where the size should be declared at the time of initialization to allocate the memory at compile time, the memory of self-referential structure can be allocated dynamically at the run time.

Let's understand a bit more about the requirement of self-referential structure with the help of a linked list:

Linked-List

A linked list is a linear data structure that is used to store data elements of similar types at different address locations. Mainly, there are three types of linked lists:-

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Implementation of each linked list is possible with help of the self-referential structure as they form a link between consecutive nodes.

Let's understand the concept of self-referential structure with more clarity using the implementation of a doubly linked list:

Code:

Output:

Explanation:

Here, we have implemented a doubly linked list where we have defined a self-referential structure of the node type.

Inside the structure, we have an integer variable data and two single pointers of the same type i.e, prev and next which is carrying the address of the previous node and next node respectively.

Using the data members, we have defined a function GetNewNode() which creates a new node dynamically. Then we have defined two functions InsertAtHead() and InsertAtTail to insert the data in the first node and last node respectively.

We can connect all of them together by storing one node's address in the other using different links.

Application

The following are the data structures in which self-referential structure is used for its implementation:

• Stack:- Stack is a linear data structure that is used to store and remove data in a particular order. It follows the principle of LIFO (Last In First Out) or FILO (First In Last Out). To learn more about the Stack data structure, visit Stack.
• Queue:- A queue is a linear data structure that allows the addition of elements from one end which is the rear end and the deletion of elements from another end which is the front end. It follows the FIFO (First In First Out) or LILO(Last In Last Out) order. To learn more about the implementation of the Queue data structure, visit Queue.
• Linked List:- A Linked list is a linear data structure used to store a collection of similar data types. To learn more about the Linked List data structure, visit Linked List.
• Binary Trees:- A Binary Tree is a hierarchical data structure that consists of nodes. A node contains three parts i.e, two pointers and a data part. The two-pointer points to the left and right child of the tree. The last node that does not have any left and right child is known as the leaf node. To learn more about Binary Trees, visit Binary Trees.

Learn More

• To gain in-depth knowledge of C++ programming language, visit C++ Tutorial.