Self Refrential Data Structures


A self-referential data structure, also known as a recursive data structure, is a data structure in which each instance of the structure contains a reference to another instance of the same type. This self-referential property allows for the creation of complex and hierarchical structures. Common examples of self-referential data structures include linked lists, trees, and graphs.

Let's look at some common examples:

1. Linked List:

In a linked list, each node contains data and a reference (or a pointer) to the next node in the sequence. The last node typically has a reference set to NULL to indicate the end of the list.

struct Node {
    int data;
    struct Node* next;
};
The next field is a self-reference to another Node structure.

2. Binary Tree:

In a binary tree, each node has at most two children, each of which is a node in the same type. Nodes are connected through left and right pointers.
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

Here, left and right are self-references to other TreeNode structures.

3. Graph:

In a graph, vertices are connected by edges. An adjacency list representation uses self-referential structures to represent each vertex and its connections.

struct Vertex {
    int data;
    struct Edge* edges;
};

struct Edge {
    struct Vertex* destination;
    struct Edge* next;
};

Here, edges in the Vertex structure is a self-reference to the linked list of edges, and next in the Edge structure is a self-reference to the next edge.

4. Doubly Linked List

You can create a structure that refers to itself, allowing you to build more complex structures.

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

In this example, the structure Node has both next and prev pointers, creating a doubly-linked list.

Using self-referential structures allows for the creation of dynamic and flexible data structures that can represent hierarchical relationships between elements. However, it's crucial to manage memory properly, especially in languages like C where manual memory management is required, to avoid memory leaks and other issues.

Example:

Here's an example of a self-referential structure representing a node in a singly linked list:
struct Node {
    int data;           // Data of the node
    struct Node *next;  // Pointer to the next node in the list
};
here each node contains an integer data and a pointer which can store the address of a structure.The beginning of the list can be identified using a head pointer which stores the address of the starting node and the end of the list can be identified by a null pointer.



Example program
#include <stdio.h>

// Define a self-referential structure for a linked list node
struct Node {
    int data;           // Data of the node
    struct Node *next;  // Pointer to the next node in the list
};

int main() {
    // Create three nodes
    struct Node node1, node2, node3;

    // Assign data to each node
    node1.data = 10;
    node2.data = 20;
    node3.data = 30;

    // Link the nodes to form a linked list
    node1.next = &node2;
    node2.next = &node3;
    node3.next = NULL;  // The last node's next is NULL, indicating the end of the list

    // Traverse the linked list and print the data
    struct Node *current = &node1;  // Start from the first node

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;  // Move to the next node
    }

    printf("NULL\n");

    return 0;
}



Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more