Lista enlazada XOR: una lista doblemente enlazada eficiente en memoria | Serie 1

Una lista doblemente enlazada ordinaria requiere espacio para dos campos de dirección para almacenar las direcciones de los Nodes anterior y siguiente. Se representa de la siguiente manera en la imagen de abajo. A partir de la imagen a continuación, se puede representar que la dirección del Node anterior se retiene y se transfiere para el cálculo del puntero anterior, mientras que la del siguiente Node está después de los punteros de manera similar. 

 Ahora hay una versión eficiente en memoria de la lista doblemente enlazada que se puede crear usando solo un espacio para el campo de dirección con cada Node. Esta lista doblemente enlazada eficiente en memoria se denomina lista enlazada XOR o memoria eficiente, ya que la lista utiliza la operación XOR bit a bit para ahorrar espacio para una dirección. En la lista enlazada XOR, en lugar de almacenar las direcciones de memoria reales, cada Node almacena el XOR de las direcciones de los Nodes anteriores y siguientes. 

Considere la lista doblemente enlazada anterior. Las siguientes son las representaciones ordinarias y XOR (o de memoria eficiente) de la lista doblemente enlazada. 
 

Ahora, aquí discutiremos ambas formas para ver cómo la representación XOR se comporta de manera diferente a la representación ordinaria.

1. Representación Ordinaria
2. Representación de lista XOR

Vía 1: Representación Ordinaria

Node A: 

prev = NULL, next = add(B) // el anterior es NULL y el siguiente es la dirección de B 

Node B: 

anterior = agregar (A), siguiente = agregar (C) // anterior es la dirección de A y la siguiente es la dirección de C 

Node C: 

anterior = agregar (B), siguiente = agregar (D) // anterior es la dirección de B y la siguiente es la dirección de D 

Node D: 

prev = add(C), next = NULL // la anterior es la dirección de C y la siguiente es NULL 

Vía 2: Representación de la lista XOR

Llamemos a la variable de dirección en representación XOR npx (XOR de siguiente y anterior) 

Mientras recorremos la lista enlazada XOR, podemos recorrer la lista XOR tanto en dirección hacia adelante como hacia atrás. Mientras recorremos la lista, debemos recordar la dirección del Node al que se accedió anteriormente para calcular la dirección del siguiente Node. 

Por ejemplo: Cuando estamos en el Node C, debemos tener la dirección de B. XOR de add(B) y npx de C nos da el add(D).

Ilustración:

Node A: 

npx = 0 XOR add(B) // XOR bit a bit de cero y dirección de B 

Node B: 

npx = agregar (A) XOR agregar (C) // XOR bit a bit de la dirección de A y la dirección de C 

Node C: 

npx = agregar (B) XOR agregar (D) // XOR bit a bit de la dirección de B y la dirección de D 

Node D: 

npx = add(C) XOR 0 // XOR bit a bit de la dirección de C y 0 

npx(C) XOR add(B) 
=> (add(B) XOR add(D)) XOR add(B) // npx(C) = add(B) XOR add(D)
=> add(B) XOR add(D) XOR add(B) // a^b = b^a and (a^b)^c = a^(b^c)
=> add(D) XOR 0  // a^a = 0
=> add(D)     // a^0 = a

De manera similar, podemos recorrer la lista en dirección hacia atrás. Ahora vamos directamente a la parte de implementación para averiguarlo mejor.

Implementación:

// C++ Implementation of Memory
// efficient Doubly Linked List
  
// Importing libraries
#include <bits/stdc++.h>
#include <cinttypes>
  
using namespace std;
  
// Class 1
// Helper class(Node structure)
class Node {
    public : int data;
    // Xor of next node and previous node
    Node* xnode;
};
  
// Method 1
// It returns Xored value of the node addresses
Node* Xor(Node* x, Node* y)
{
    return reinterpret_cast<Node*>(
        reinterpret_cast<uintptr_t>(x)
        ^ reinterpret_cast<uintptr_t>(y));
}
  
// Method 2
// Insert a node at the start of the Xored LinkedList and
// mark the newly inserted node as head
void insert(Node** head_ref, int data)
{
    // Allocate memory for new node
    Node* new_node = new Node();
    new_node -> data = data;
  
    // Since new node is inserted at the
    // start , xnode of new node will always be
    // Xor of current head and NULL
    new_node -> xnode = *head_ref;
  
    // If linkedlist is not empty, then xnode of
    // present head node will be Xor of new node
    // and node next to current head */
    if (*head_ref != NULL) {
        // *(head_ref)->xnode is Xor of (NULL and next).
        // If we Xor Null with next we get next
        (*head_ref)
            -> xnode = Xor(new_node, (*head_ref) -> xnode);
    }
  
    // Change head
    *head_ref = new_node;
}
  
// Method 3
// It simply prints contents of doubly linked
// list in forward direction
void printList(Node* head)
{
    Node* curr = head;
    Node* prev = NULL;
    Node* next;
  
    cout << "The nodes of Linked List are: \n";
  
    // Till condition holds true
    while (curr != NULL) {
        // print current node
        cout << curr -> data << " ";
  
        // get address of next node: curr->xnode is
        // next^prev, so curr->xnode^prev will be
        // next^prev^prev which is next
        next = Xor(prev, curr -> xnode);
  
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
  
// Method 4
// main driver method
int main()
{
    Node* head = NULL;
    insert(&head, 10);
    insert(&head, 100);
    insert(&head, 1000);
    insert(&head, 10000);
  
    // Printing the created list
    printList(head);
  
    return (0);
}

The nodes of Linked List are: 
10000 1000 100 10