Ventajas de las listas enlazadas en la representación de adyacencia de un grafo

El Manual de Diseño de Algoritmos de Skiena (3 edición, p. 204) se refiere a las “listas de adyacencia” en contraposición a las representaciones de adyacencia generales, definiéndolas como la asignación a cada vértice “a” de una lista simplemente enlazada “L_a” con un conjunto subyacente “set(L_a) = {b | (x, b) <- edges, x == a}”.

Me sorprende que Skiena presente la lista simplemente enlazada como la estructura de datos definitiva para implementar las colecciones “L_a”. Mi impresión es que las listas simplemente enlazadas están perdiendo popularidad en comparación con los arreglos y las tablas hash, porque:

• No son eficientes en términos de caché para recorrerlas (como los arreglos), y la brecha entre la velocidad del procesador y el acceso a la memoria principal se ha vuelto más importante. (Por ejemplo, este video (7m) de Stroustrup).

• No aportan mucho, especialmente cuando el orden no es importante. La ventaja de las listas simplemente enlazadas sobre los arreglos es que admiten agregar y eliminar en tiempo constante. Pero en el caso en el que no nos importa el orden, estas operaciones también pueden ser de tiempo constante en un arreglo utilizando “swap and pop” para eliminar. Una tabla hash tendría la ventaja adicional de una búsqueda en tiempo constante. Mi comprensión es que las tablas hash tienen un mayor costo de memoria que una lista simplemente enlazada o un arreglo, pero esta consideración se ha vuelto relativamente menos importante. (Quizás esta afirmación no sea significativa en ausencia de una aplicación específica).

Otras fuentes tratan las listas de adyacencia de manera diferente. Por ejemplo, Wikipedia presenta una implementación en la que “L_a” son arreglos. Y en “Algoritmos para Programación Funcional” de Stone, “L_a” son conjuntos no ordenados, implementados en última instancia como listas de Scheme (que a su vez me pareció extraño).

Mi pregunta: ¿Existe alguna consideración que me esté perdiendo y que brinde a las listas simplemente enlazadas una ventaja significativa en las representaciones de adyacencia?

Añado una solicitud sincera de que antes de votar para cerrar esta pregunta o publicar un comentario con un tono poco amable, se pregunten si realmente están ayudando a este sitio a alcanzar sus objetivos al hacerlo.