Estructuras autorreferenciales

Las estructuras autorreferenciales son aquellas estructuras que tienen uno o más punteros que apuntan al mismo tipo de estructura que su miembro.
 

En otras palabras, las estructuras que apuntan al mismo tipo de estructuras son de naturaleza autorreferencial.
Ejemplo: 
 

struct node {
    int data1;
    char data2;
    struct node* link;
};
 
int main()
{
    struct node ob;
    return 0;
}

class node:
    def __init__(self):
        self.data1=0
        self.data2=''
        self.link=None
 
if __name__ == '__main__':
    ob=node()

En el ejemplo anterior, ‘enlace’ es un puntero a una estructura de tipo ‘Node’. Por lo tanto, la estructura ‘Node’ es una estructura autorreferencial con ‘enlace’ como puntero de referencia. 
Un punto importante a considerar es que el puntero debe inicializarse correctamente antes de acceder, ya que por defecto contiene valor basura.
Tipos de estructuras autorreferenciales 
 

1. Estructura autorreferencial con enlace único
2. Estructura autorreferencial con múltiples enlaces

Estructura autorreferencial con enlace único: estas estructuras solo pueden tener un puntero propio como miembro. El siguiente ejemplo nos mostrará cómo conectar los objetos de una estructura autorreferencial con el enlace único y acceder a los miembros de datos correspondientes. La conexión formada se muestra en la siguiente figura. 
 

#include <stdio.h>
 
struct node {
    int data1;
    char data2;
    struct node* link;
};
 
int main()
{
    struct node ob1; // Node1
 
    // Initialization
    ob1.link = NULL;
    ob1.data1 = 10;
    ob1.data2 = 20;
 
    struct node ob2; // Node2
 
    // Initialization
    ob2.link = NULL;
    ob2.data1 = 30;
    ob2.data2 = 40;
 
    // Linking ob1 and ob2
    ob1.link = &ob2;
 
    // Accessing data members of  ob2 using ob1
    printf("%d", ob1.link->data1);
    printf("\n%d", ob1.link->data2);
    return 0;
}

class node:
    def __init__(self):
        self.data1=0
        self.data2=0
        self.link=None
 
if __name__ == '__main__':
    ob1=node() # Node1
 
    # Initialization
    ob1.link = None
    ob1.data1 = 10
    ob1.data2 = 20
 
    ob2=node() # Node2
 
    # Initialization
    ob2.link = None
    ob2.data1 = 30
    ob2.data2 = 40
 
    # Linking ob1 and ob2
    ob1.link = ob2
 
    # Accessing data members of  ob2 using ob1
    print(ob1.link.data1)
    print(ob1.link.data2)

30
40

Estructura autorreferencial con múltiples enlaces: las estructuras autorreferenciales con múltiples enlaces pueden tener más de un autopuntero. Muchas estructuras de datos complicadas se pueden construir fácilmente utilizando estas estructuras. Tales estructuras pueden conectarse fácilmente a más de un Node a la vez. El siguiente ejemplo muestra una estructura de este tipo con más de un enlace.
Las conexiones realizadas en el ejemplo anterior se pueden entender utilizando la siguiente figura. 
 

#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;
    ob1.data = 10;
 
    struct node ob2; // Node2
 
    // Initialization
    ob2.prev_link = NULL;
    ob2.next_link = NULL;
    ob2.data = 20;
 
    struct node ob3; // Node3
 
    // Initialization
    ob3.prev_link = NULL;
    ob3.next_link = NULL;
    ob3.data = 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", ob1.data);
    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", ob2.data);
    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", ob3.data);
    return 0;
}

class node:
    def __init__(self):
        self.data=0
        self.prev_link=None
        self.next_link=None
 
if __name__ == '__main__':
    ob1=node() #Node1
 
    # Initialization
    ob1.prev_link = None
    ob1.next_link = None
    ob1.data = 10
 
    ob2=node() #Node2
 
    # Initialization
    ob2.prev_link = None
    ob2.next_link = None
    ob2.data = 20
 
    ob3=node() # Node3
 
    # Initialization
    ob3.prev_link = None
    ob3.next_link = None
    ob3.data = 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
    print(ob1.data,end='\t')
    print(ob1.next_link.data,end='\t')
    print(ob1.next_link.next_link.data)
 
    # Accessing data of ob1, ob2 and ob3 by ob2
    print(ob2.prev_link.data,end='\t')
    print(ob2.data,end='\t')
    print(ob2.next_link.data)
 
    # Accessing data of ob1, ob2 and ob3 by ob3
    print(ob3.prev_link.prev_link.data,end='\t')
    print(ob3.prev_link.data,end='\t')
    print(ob3.data)

10    20    30
10    20    30
10    20    30

En el ejemplo anterior podemos ver que ‘ob1’, ‘ob2’ y ‘ob3’ son tres objetos de la estructura autorreferencial ‘Node’. Y están conectados usando sus enlaces de tal manera que cualquiera de ellos puede acceder fácilmente a los datos de los demás. Esta es la belleza de las estructuras autorreferenciales. Las conexiones se pueden manipular según los requisitos del programador.
Aplicaciones: 
Las estructuras autorreferenciales son muy útiles en la creación de otras estructuras de datos complejas como: 
 

• Listas vinculadas
• pilas
• colas
• Árboles
• Gráficos, etc.