¿Deben las listas enlazadas siempre tener un puntero de cola?

Mi entendimiento...

Ventajas:

• Insertar al final es O (1) en lugar de O (N).
• Si la lista es una Lista Doblemente Vinculada, entonces eliminar del final también es O (1) en lugar de O (N).

Desventaja:

• Ocupa una cantidad trivial de memoria adicional: 4-8 bytes .
• El implementador tiene que hacer un seguimiento de la cola.

Mirando estas ventajas y desventajas, no puedo ver por qué una Lista Vinculada evitaría usar un puntero de cola. ¿Se me escapa algo?

Tienes razón, un puntero de cola nunca está de más y solo puede ayudar. Sin embargo, hay una situación en la que uno no necesita un puntero de cola en absoluto.

Si se está utilizando una lista vinculada para implementar una pila, no hay necesidad de un puntero de cola porque se puede garantizar que todos los accesos, inserciones y eliminaciones ocurran en la cabeza. Dicho esto, uno podría usar una lista doblemente enlazada con un puntero de cola de todos modos porque esa es la implementación estándar en una biblioteca o plataforma y la memoria es barata, pero uno no la necesita .

Las listas enlazadas suelen ser persistentes e inmutables. De hecho, en lenguajes de programación funcionales, este uso es omnipresente. Los punteros de cola rompen ambas propiedades. Sin embargo, si no le importa la inmutabilidad o la persistencia, hay muy pocos inconvenientes en incluir un puntero de cola.

Raramente uso un puntero de cola para las listas enlazadas y tiendo a usar listas enlazadas individualmente con más frecuencia cuando es suficiente un patrón de inserción y extracción de tipo pila / inserción (o solo eliminación de tiempo lineal desde el medio). Es porque en mis casos de uso común, el puntero de la cola es realmente costoso, al igual que lo es convertir la lista unida en una lista doblemente unida.

A menudo, el uso de mi caso común para una lista vinculada individualmente puede almacenar cientos de miles de listas vinculadas que solo contienen unos pocos nodos de lista cada una. También generalmente no uso punteros para listas enlazadas. En su lugar, uso índices en una matriz, ya que los índices pueden ser de 32 bits, por ejemplo, ocupar la mitad del espacio de un puntero de 64 bits. Por lo general, tampoco asigno los nodos de la lista uno a la vez y, en cambio, solo uso una gran matriz para almacenar todos los nodos y luego uso índices de 32 bits para vincular los nodos.

Como ejemplo, imagine un videojuego que utiliza una cuadrícula de 400x400 para dividir un millón de partículas que se mueven y rebotan entre sí para acelerar la detección de colisiones. En ese caso, una manera bastante eficiente de almacenar es almacenar 160,000 listas enlazadas individualmente, lo que se traduce en 160,000 enteros de 32 bits en mi caso (~ 640 kilobytes) y una sobrecarga de enteros de 32 bits por partícula. Ahora, a medida que las partículas se mueven en la pantalla, todo lo que tenemos que hacer es actualizar algunos enteros de 32 bits para mover una partícula de una celda a otra, así:

... con el nextíndice ("puntero") de un nodo de partículas que sirve como índice para la siguiente partícula en la celda o la siguiente partícula libre para reclamar si la partícula ha muerto (básicamente, una implementación del asignador de lista libre usando índices):

La eliminación de tiempo lineal de una celda no es realmente una sobrecarga, ya que estamos procesando la lógica de partículas iterando a través de las partículas en una celda, por lo que una lista doblemente vinculada solo agregaría una sobrecarga de un tipo que no es beneficioso en todo en mi caso, así como una cola tampoco me beneficiaría en absoluto.

Un puntero de cola duplicaría el uso de memoria de la cuadrícula y aumentaría el número de errores de caché. También requiere inserción para requerir una rama para verificar si la lista está vacía en lugar de no tener ramas. Convertirlo en una lista doblemente vinculada duplicaría la sobrecarga de la lista de cada partícula. El 90% del tiempo utilizo listas vinculadas, es para casos como estos, por lo que un puntero de cola en realidad sería relativamente costoso de almacenar.

Entonces, 4-8 bytes en realidad no es trivial en la mayoría de los contextos en los que uso listas enlazadas en primer lugar. Solo quería ingresar allí, ya que si está utilizando una estructura de datos para almacenar una gran cantidad de elementos, entonces 4-8 bytes no siempre pueden ser tan insignificantes. De hecho, utilizo listas vinculadas para reducir la cantidad de asignaciones de memoria y la cantidad de memoria requerida en lugar de almacenar, por ejemplo, 160,000 arreglos dinámicos que crecen para la cuadrícula, lo que tendría un uso explosivo de la memoria (generalmente un puntero más dos enteros al menos por celda de cuadrícula) junto con las asignaciones de montón por celda de cuadrícula en lugar de solo un entero y cero asignaciones de montón por celda).

A menudo encuentro que muchas personas buscan listas vinculadas por su complejidad de tiempo constante asociada con la extracción frontal / media y la inserción frontal / media cuando los LL a menudo son una mala elección en esos casos debido a su falta general de contigüidad. Donde los LL son hermosos para mí desde el punto de vista del rendimiento es la capacidad de mover un elemento de una lista a otra simplemente manipulando unos pocos punteros y siendo capaz de lograr una estructura de datos de tamaño variable sin un asignador de memoria de tamaño variable (ya que cada nodo tiene un tamaño uniforme, podemos usar listas libres, por ejemplo). Si cada nodo de la lista se asigna individualmente contra un asignador de propósito general, generalmente es cuando las listas vinculadas tienen un rendimiento mucho peor en comparación con las alternativas, y '

En su lugar, sugeriría que para la mayoría de los casos en los que las listas vinculadas sirven como una optimización muy efectiva sobre alternativas directas, las formas más útiles generalmente están vinculadas individualmente, solo necesitan un puntero de cabeza y no requieren una asignación de memoria de propósito general por nodo y, en cambio, a menudo solo puede agrupar la memoria ya asignada por nodo (de una gran matriz ya asignada de antemano, por ejemplo). Además, cada SLL generalmente almacenaría una cantidad muy pequeña de elementos en esos casos, como bordes conectados a un nodo gráfico (muchas listas enlazadas pequeñas en lugar de una lista enlazada masiva).

También vale la pena tener en cuenta que tenemos una gran cantidad de DRAM en estos días, pero ese es el segundo tipo de memoria más lento disponible. Todavía estamos en algo así como 64 KB por núcleo cuando se trata de la caché L1 con líneas de caché de 64 bytes. Como resultado, esos pequeños ahorros de bytes realmente pueden importar en un área crítica de rendimiento como el simulador de partículas anterior cuando se multiplican millones de veces si significa la diferencia entre almacenar el doble de nodos en una línea de caché o no, por ejemplo