Una lista enlazada XOR es un tipo de estructura de datos que se utiliza en programación informática . Aprovecha la operación XOR bit a bit para reducir los requisitos de almacenamiento de las listas doblemente enlazadas almacenando la composición de ambas direcciones en un campo. Si bien la dirección compuesta no es significativa por sí sola, durante el recorrido se puede combinar con el conocimiento de la dirección del último nodo visitado para deducir la dirección del siguiente nodo.
Una lista doblemente enlazada ordinaria almacena las direcciones de los elementos de la lista anterior y siguiente en cada nodo de la lista, lo que requiere dos campos de dirección:
...ABCDE... -> siguiente -> siguiente -> siguiente -> <– anterior <– anterior <– anterior <–
Una lista enlazada XOR comprime la misma información en un campo de dirección almacenando el XOR bit a bit (aquí indicado por ⊕) de la dirección anterior y la dirección siguiente en un campo:
...ABCDE... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌
Más formalmente:
enlace(B) = addr(A)⊕addr(C), enlace(C) = addr(B)⊕addr(D), ...
Al recorrer la lista de izquierda a derecha: suponiendo que el cursor está en C, el elemento anterior, B, puede ser objeto de una operación XOR con el valor en el campo de enlace (B⊕D). Se obtendrá entonces la dirección de D y se podrá reanudar el recorrido de la lista. El mismo patrón se aplica en la otra dirección.
es decir addr(D) = link(C) ⊕ addr(B)donde
enlace(C) = addr(B)⊕addr(D)
entonces
addr(D) = addr(B)⊕addr(D) ⊕ addr(B) addr(D) = addr(B)⊕addr(B) ⊕ addr(D)
desde
X⊕X = 0 => addr(D) = 0 ⊕ addr(D)
desde
X⊕0 = X => addr(D) = addr(D)
La operación XOR cancela addr(B)la aparición dos veces en la ecuación y lo único que nos queda es el addr(D).
Para comenzar a recorrer la lista en cualquier dirección desde algún punto, se requiere la dirección de dos elementos consecutivos. Si las direcciones de los dos elementos consecutivos están invertidas, el recorrido de la lista se realizará en la dirección opuesta. [1]
La clave es la primera operación y las propiedades de XOR:
El registro R2 siempre contiene la operación XOR de la dirección del elemento actual C con la dirección del elemento predecesor P: C⊕P. Los campos de enlace de los registros contienen la operación XOR de las direcciones izquierda y derecha del sucesor, es decir, L⊕R. La operación XOR de R2 (C⊕P) con el campo de enlace actual (L⊕R) da como resultado C⊕P⊕L⊕R.
En cada caso, el resultado es la operación XOR de la dirección actual con la siguiente dirección. La operación XOR de esta operación con la dirección actual en R1 deja la siguiente dirección. R2 queda con el par XOR requerido de la dirección actual (ahora) y la predecesora.
{…B C D…}y con R1 y R2 como registros que contienen, respectivamente, la dirección del elemento de lista actual (por ejemplo, C) y un registro de trabajo que contiene la operación XOR de la dirección actual con la dirección anterior (por ejemplo, C⊕D). Expresado como instrucciones del Sistema/360 :X R2, Enlace R2 <- C⊕D ⊕ B⊕D (es decir, B⊕C, siendo "Enlace" el campo de enlace en el registro actual, que contiene B⊕D)XR R1,R2 R1 <- C ⊕ B⊕C (es decir, B, voilá: el siguiente registro)
{0 A B C…}. El campo de enlace en A sería 0⊕B. Se necesita una instrucción adicional en la secuencia anterior después de las dos operaciones XOR para detectar un resultado cero al desarrollar la dirección del elemento actual.Los sistemas informáticos tienen una memoria cada vez más barata y abundante, por lo que la sobrecarga de almacenamiento no suele ser un problema primordial fuera de los sistemas integrados especializados . Cuando todavía es deseable reducir la sobrecarga de una lista enlazada, el desenrollado proporciona un enfoque más práctico (así como otras ventajas, como aumentar el rendimiento de la caché y acelerar el acceso aleatorio ).
El principio subyacente de la lista enlazada XOR se puede aplicar a cualquier operación binaria reversible. Reemplazar XOR por suma o resta da lugar a formulaciones ligeramente diferentes, pero en gran medida equivalentes:
...ABCDE... ⇌ A+C ⇌ B+D ⇌ C+E ⇌
Este tipo de lista tiene exactamente las mismas propiedades que la lista enlazada XOR, excepto que un campo de enlace cero no es un "espejo". La dirección del siguiente nodo de la lista se obtiene restando la dirección del nodo anterior del campo de enlace del nodo actual.
...ABCDE... ⇌ CA ⇌ BD ⇌ CE ⇌
Este tipo de lista se diferencia de la lista enlazada XOR "tradicional" estándar en que las secuencias de instrucciones necesarias para recorrer la lista hacia adelante son diferentes de las secuencias necesarias para recorrer la lista en sentido inverso. La dirección del siguiente nodo, en sentido hacia adelante, se obtiene sumando el campo de enlace a la dirección del nodo anterior; la dirección del nodo precedente se obtiene restando el campo de enlace de la dirección del siguiente nodo.
La lista enlazada por sustracción también es especial en el sentido de que toda la lista se puede reubicar en la memoria sin necesidad de parchear los valores de los punteros, ya que agregar un desplazamiento constante a cada dirección de la lista no requerirá ningún cambio en los valores almacenados en los campos de enlace. (Véase también serialización ). Esta es una ventaja sobre las listas enlazadas XOR y las listas enlazadas tradicionales.
El concepto de lista enlazada XOR se puede generalizar a árboles de búsqueda binaria XOR . [3]