Hispanopedia WikiUna 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 reducir los requisitos de almacenamiento de las listas doblemente enlazadas , almacenando la composición de ambas direcciones en un solo campo. Si bien la dirección compuesta no tiene significado por sí sola, durante el recorrido se puede combinar con la dirección del último nodo visitado para deducir la dirección del siguiente nodo.
Descripción
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 (denotado aquí por ⊕) de la dirección anterior y la dirección siguiente en un solo campo:
... ABCDE ... ⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌
De forma más formal:
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 se encuentra en C, se puede aplicar la operación XOR al elemento anterior, B, con el valor del campo de enlace (B⊕D). De esta forma, se obtendrá la dirección de D y se podrá continuar recorriendo la lista. El mismo procedimiento se aplica en sentido contrario.
es decir, addr(D) = link(C) ⊕ addr(B) dónde
enlace(C) = dirección(B)⊕dirección(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)su aparición duplicada 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 producirá en la dirección opuesta. [ 1 ]
Teoría de funcionamiento
La clave está en la primera operación y en las propiedades de XOR:
- X⊕X = 0
- X⊕0 = X
- X⊕Y = Y⊕X
- (X⊕Y)⊕Z = X⊕(Y⊕Z)
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 en los registros contienen la operación XOR de las direcciones sucesoras izquierda y derecha, por ejemplo, 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.
- Si el predecesor era L, P(=L) y L se cancelan dejando C⊕R.
- Si el predecesor hubiera sido R, P(=R) y R se cancelan, quedando C⊕L.
En cada caso, el resultado es la operación XOR entre la dirección actual y la siguiente. Al realizar la operación XOR entre esta dirección y la actual en R1, se obtiene la siguiente dirección. R2 se queda con el par XOR necesario formado por la dirección actual y la anterior.
Características
- Dos operaciones XOR son suficientes para recorrer un elemento a otro, y las mismas instrucciones bastan en ambos casos. Consideremos una lista con elementos
{…B C D…}y donde R1 y R2 son registros que contienen, respectivamente, la dirección del elemento actual (por ejemplo, C) y un registro de trabajo que contiene el resultado de la operación XOR entre la dirección actual y la anterior (por ejemplo, C⊕D). Expresado como instrucciones de System/360 :
X R2, Enlace R2 <- C⊕D ⊕ B⊕D (es decir, B⊕C, donde "Enlace" es el campo de enlace) en el registro actual, que contiene B⊕D) XR R1,R2 R1 <- C ⊕ B⊕C (es decir, B, : el siguiente registro)
- El final de la lista se indica imaginando un elemento de la lista en la dirección cero colocado junto a un punto final, como en
{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, - Un punto final de lista puede hacerse reflectante estableciendo el puntero de enlace en cero. Un puntero cero es un espejo . (La operación XOR entre las direcciones de los vecinos izquierdo y derecho, al ser iguales, da como resultado cero).
Desventajas
- Las herramientas de depuración de propósito general no pueden seguir la cadena XOR, lo que dificulta la depuración; [ 2 ]
- El precio de la disminución en el uso de memoria es un aumento en la complejidad del código, lo que encarece el mantenimiento;
- La mayoría de los sistemas de recolección de basura no funcionan con estructuras de datos que no contienen punteros literales ;
- No todos los lenguajes admiten la conversión de tipos entre punteros y enteros; la operación XOR en punteros no está definida en algunos contextos.
- Al recorrer la lista, se necesita la dirección del nodo al que se accedió previamente para calcular la dirección del siguiente nodo, y los punteros serán ilegibles si no se está recorriendo la lista ; por ejemplo, si el puntero a un elemento de la lista estaba contenido en otra estructura de datos;
- Las listas enlazadas XOR no ofrecen algunas de las ventajas importantes de las listas doblemente enlazadas, como la posibilidad de eliminar un nodo de la lista conociendo solo su dirección o la posibilidad de insertar un nuevo nodo antes o después de un nodo existente conociendo solo la dirección del nodo existente.
Los sistemas informáticos disponen de memoria cada vez más barata y abundante, por lo que la sobrecarga de almacenamiento no suele ser un problema importante fuera de los sistemas embebidos especializados . Cuando aún se desea reducir la sobrecarga de una lista enlazada, el desenrollado proporciona un enfoque más práctico (además de otras ventajas, como aumentar el rendimiento de la caché y acelerar el acceso aleatorio ).
Variaciones
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:
Lista enlazada adicional
... ABCDE ... ⇌ A+C ⇌ B+D ⇌ C+E ⇌
Este tipo de lista tiene exactamente las mismas propiedades que la lista enlazada XOR, con la excepción de 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 al campo de enlace del nodo actual.
lista enlazada de resta
... ABCDE ... ⇌ CA ⇌ DB ⇌ EC ⇌
Este tipo de lista se diferencia de la lista enlazada XOR "tradicional" estándar en que la secuencia de instrucciones necesaria para recorrerla hacia adelante es distinta de la necesaria para recorrerla en sentido inverso. La dirección del siguiente nodo, avanzando, 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 a la dirección del siguiente nodo.
La lista enlazada de resta también es especial porque puede reubicarse en memoria sin necesidad de modificar los valores de los punteros, ya que añadir un desplazamiento constante a cada dirección de la lista no requiere cambios en los valores almacenados en los campos de enlace. (Véase también serialización ). Esto supone una ventaja tanto sobre las listas enlazadas XOR como sobre las listas enlazadas tradicionales.
Véase también
Referencias
Enlaces externos
- Prokash Sinha (1 de diciembre de 2004). "Una lista doblemente enlazada eficiente en memoria" . Linux Journal .
- XORList: Lista enlazada eficiente en C++ (Licencia MIT)
- Implementación de la lista XOR en C++ en la biblioteca Listes.
- Aritmética binaria
- Listas enlazadas