Lista enlazada desenrollada

En programación informática, una lista enlazada desenrollada es una variación de la lista enlazada que almacena múltiples elementos en cada nodo. Puede aumentar drásticamente el rendimiento de la memoria caché , al tiempo que reduce la sobrecarga de memoria asociada con el almacenamiento de metadatos de la lista, como las referencias . Está relacionada con el árbol B.

Un nodo de lista enlazada desenrollada típico se ve así:

 nodo de registro {
      nodo siguiente        // referencia al siguiente nodo en la lista 
     int numElements // número de elementos en este nodo, hasta maxElements 
     array elements   // una matriz de numElements elementos, 
                     // con espacio asignado para maxElements elementos
 }

Cada nodo admite hasta un número máximo de elementos determinado, normalmente lo suficientemente grande como para que el nodo llene una sola línea de caché o un pequeño múltiplo de la misma. Una posición en la lista se indica mediante una referencia al nodo y una posición en la matriz de elementos. También es posible incluir un puntero anterior para una lista doblemente enlazada desenrollada .

Para insertar un nuevo elemento, buscamos el nodo en el que debería estar el elemento e insertamos el elemento en la elementsmatriz, incrementando numElements. Si la matriz ya está llena, primero insertamos un nuevo nodo que precede o sigue al actual y movemos la mitad de los elementos del nodo actual hacia él.

Para eliminar un elemento, buscamos el nodo en el que se encuentra y lo eliminamos de la elementsmatriz, disminuyendo numElements. Si esto reduce el nodo a menos de la mitad, entonces movemos elementos del siguiente nodo para llenarlo nuevamente por encima de la mitad. Si esto deja el siguiente nodo a menos de la mitad, entonces movemos todos sus elementos restantes al nodo actual, luego lo omitimos y lo eliminamos.

Una de las principales ventajas de las listas enlazadas desenrolladas es la reducción de los requisitos de almacenamiento. Todos los nodos (excepto uno como máximo) están al menos medio llenos. Si se realizan muchas inserciones y eliminaciones aleatorias, el nodo promedio estará lleno aproximadamente en tres cuartas partes, y si las inserciones y eliminaciones solo se realizan al principio y al final, casi todos los nodos estarán llenos. Supongamos que:

• m = maxElements, el número máximo de elementos en cada elementsmatriz;
• v = la sobrecarga por nodo para referencias y recuentos de elementos;
• s = el tamaño de un solo elemento.

Entonces, el espacio utilizado para n elementos varía entre y . A modo de comparación, las listas enlazadas ordinarias requieren espacio, aunque v puede ser menor, y las matrices , una de las estructuras de datos más compactas, requieren espacio. Las listas enlazadas desenrolladas distribuyen eficazmente la sobrecarga v entre varios elementos de la lista. Por lo tanto, vemos la ganancia de espacio más significativa cuando la sobrecarga es grande, es grande o los elementos son pequeños. ${\displaystyle (v/m+s)n}$${\displaystyle (2v/m+s)n}$${\displaystyle (v+s)n}$${\estilo de visualización sn}$maxElements

Si los elementos son particularmente pequeños, como bits, la sobrecarga puede ser hasta 64 veces mayor que los datos en muchas máquinas. Además, muchos asignadores de memoria populares mantendrán una pequeña cantidad de metadatos para cada nodo asignado, lo que aumenta la sobrecarga efectiva v . Ambos factores hacen que las listas enlazadas desenrolladas sean más atractivas.

Debido a que cada nodo de una lista enlazada desenrollada almacena un recuento junto al siguiente campo, la recuperación del elemento k de una lista enlazada desenrollada (indexación) se puede realizar en n / m + 1 errores de caché, hasta un factor de m mejor que las listas enlazadas comunes. Además, si el tamaño de cada elemento es pequeño en comparación con el tamaño de la línea de caché, la lista se puede recorrer en orden con menos errores de caché que las listas enlazadas comunes. En cualquier caso, el tiempo de operación aún aumenta linealmente con el tamaño de la lista.

• Codificación CDR
• Saltar lista
• árbol T
• Lista enlazada XOR
• Árbol de matriz hash

• Shao, Z.; Reppy, JH; Appel, AW (1994), "Listas de desenrollado", Actas de la conferencia ACM de 1994 sobre LISP y programación funcional - LFP '94 , págs. 185-191, doi : 10.1145/182409.182453 , ISBN 978-0897916431, Número de identificación del sujeto  3192876

• Implementación escrita en C
• Otra implementación escrita en Java
• Implementación escrita en Golang
• Estructuras de datos abiertas: sección 3.3: SEList: una lista enlazada que hace un uso eficiente del espacio, Pat Morin