Una lista enlazada XOR es un tipo de estructura de datos utilizada en programación informática . Aprovecha la operación XOR bit a bit para disminuir los requisitos de almacenamiento para listas doblemente vinculadas al almacenar 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:
... A B C D E ... –> 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:
... A B C D E ... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌
Más formalmente:
enlace(B) = dirección(A)⊕dirección(C), enlace(C) = dirección(B)⊕dirección(D), ...
Al recorrer la lista de izquierda a derecha: suponiendo que el cursor está en C, el elemento anterior, B, se puede aplicar XOR con el valor en el campo de enlace (B⊕D). Luego se obtendrá 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) = dirección(B)⊕dirección(D)
entonces
dirección(D) = dirección(B)⊕dirección(D) ⊕ dirección(B) dirección(D) = dirección(B)⊕dirección(B) ⊕ dirección(D)
desde
X⊕X = 0 => dirección(D) = 0 ⊕ dirección(D)
desde
X⊕0 = X => dirección(D) = dirección(D)
La operación XOR cancela addr(B)aparecer 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 se invierten las direcciones de dos elementos consecutivos, el recorrido de la lista se producirá en la dirección opuesta. [1]
La clave es la primera operación y las propiedades de XOR:
El registro R2 siempre contiene el XOR de la dirección del elemento C actual con la dirección del elemento predecesor P: C⊕P. Los campos Enlace en los registros contienen el XOR de las direcciones sucesoras izquierda y derecha, digamos L⊕R. XOR de R2 (C⊕P) con el campo de enlace actual (L⊕R) produce C⊕P⊕L⊕R.
En cada caso, el resultado es el XOR de la dirección actual con la siguiente dirección. XOR de esto con la dirección actual en R1 deja la siguiente dirección. A R2 le queda el par XOR requerido de la dirección actual (ahora) y el predecesor.
{…B C D…}y con R1 y R2 como registros que contienen, respectivamente, la dirección del elemento de la lista actual (digamos C) y un registro de trabajo que contiene el XOR de la dirección actual con la dirección anterior (digamos C⊕D). Transmitir como instrucciones de System/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 vinculada, 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 formulaciones ligeramente diferentes, pero en gran medida equivalentes:
... A B C D E ... ⇌ 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 en la lista se obtiene restando la dirección del nodo anterior del campo de enlace del nodo actual.
... A B C D E ... ⇌ CA ⇌ DB ⇌ CE ⇌
Este tipo de lista difiere de la lista enlazada XOR "tradicional" estándar en que las secuencias de instrucciones necesarias para recorrer la lista hacia adelante son diferentes de la secuencia necesaria para recorrer la lista hacia atrás. La dirección del siguiente nodo, en adelante, se obtiene agregando el campo de enlace a la dirección del nodo anterior; la dirección del nodo anterior se obtiene restando el campo de enlace de la dirección del siguiente nodo.
La lista vinculada de resta también es especial porque toda la lista se puede reubicar en la memoria sin necesidad de parchear los valores del puntero, ya que agregar un desplazamiento constante a cada dirección en la lista no requerirá ningún cambio en los valores almacenados en los campos de vínculo. (Ver también serialización ). Esta es una ventaja sobre las listas vinculadas XOR y las listas vinculadas tradicionales.
El concepto de lista enlazada XOR se puede generalizar a árboles de búsqueda binarios XOR . [3]