¿En qué circunstancias son útiles las listas enlazadas?

La mayoría de las veces que veo que la gente intenta usar listas enlazadas, me parece una mala elección (o muy mala). Quizás sería útil explorar las circunstancias bajo las cuales una lista enlazada es o no una buena elección de estructura de datos.

Idealmente, las respuestas expondrían los criterios que se utilizarán para seleccionar una estructura de datos y qué estructuras de datos probablemente funcionarán mejor en circunstancias específicas.

Editar: Debo decir que estoy bastante impresionado no solo por el número, sino también por la calidad de las respuestas. Solo puedo aceptar uno, pero hay dos o tres más que diría que hubiera valido la pena aceptar si no hubiera habido algo un poco mejor. Solo un par (especialmente el que terminé aceptando) señalaron situaciones en las que una lista enlazada proporcionaba una ventaja real. Creo que Steve Jessop merece algún tipo de mención de honor por haber dado no solo una, sino tres respuestas diferentes, todas las cuales me parecieron bastante impresionantes. Por supuesto, aunque se publicó solo como un comentario, no como una respuesta, creo que vale la pena leer la entrada del blog de Neil, no solo informativa, sino también bastante entretenida.

Pueden ser útiles para estructuras de datos concurrentes. (Ahora hay una muestra de uso no concurrente en el mundo real a continuación, que no estaría allí si @Neil no hubiera mencionado a FORTRAN. ;-)

Por ejemplo, ConcurrentDictionary<TKey, TValue>en .NET 4.0 RC use listas vinculadas para encadenar elementos que tengan hash en el mismo depósito.

La estructura de datos subyacente para ConcurrentStack<T>también es una lista vinculada.

ConcurrentStack<T>es una de las estructuras de datos que sirven como base para el nuevo Thread Pool , (con las "colas" locales implementadas como pilas, esencialmente). (La otra estructura de soporte principal es ConcurrentQueue<T>).

El nuevo Thread Pool, a su vez, proporciona la base para la programación del trabajo de la nueva Task Parallel Library .

Por lo tanto, ciertamente pueden ser útiles: una lista vinculada actualmente sirve como una de las principales estructuras de soporte de al menos una gran tecnología nueva.

(Una lista enlazada individualmente hace una elección convincente libre de bloqueos , pero no libre de espera, en estos casos, porque las operaciones principales se pueden llevar a cabo con un solo CAS (+ reintentos). En un entorno GC-d moderno, como Java y .NET: el problema de ABA se puede evitar fácilmente. Simplemente envuelva los elementos que agregue en nodos recién creados y no reutilice esos nodos; deje que el GC haga su trabajo. La página sobre el problema de ABA también proporciona la implementación de un bloqueo. pila gratuita: eso realmente funciona en .Net (y Java) con un nodo (GC-ed) que contiene los elementos).

Editar : @Neil: en realidad, lo que mencionaste sobre FORTRAN me recordó que el mismo tipo de listas enlazadas se puede encontrar en probablemente la estructura de datos más utilizada y abusada en .NET: el genérico .NET simple Dictionary<TKey, TValue>.

No una, sino muchas listas vinculadas se almacenan en una matriz.

• Evita hacer muchas (des) asignaciones pequeñas en inserciones / eliminaciones.
• La carga inicial de la tabla hash es bastante rápida, porque la matriz se llena secuencialmente (funciona muy bien con el caché de la CPU).
• Sin mencionar que una tabla hash de encadenamiento es cara en términos de memoria, y este "truco" reduce el "tamaño de los punteros" a la mitad en x64.

Esencialmente, muchas listas enlazadas se almacenan en una matriz. (uno para cada depósito utilizado). Una lista libre de nodos reutilizables está "entretejida" entre ellos (si hubiera borrados). Una matriz se asigna al inicio / en el refrito y los nodos de las cadenas se mantienen en ella. También hay un puntero libre , un índice en la matriz, que sigue a las eliminaciones. ;-) Entonces, lo creas o no, la técnica FORTRAN sigue viva. (... y en ningún otro lugar, que en una de las estructuras de datos .NET más utilizadas ;-).

Las listas vinculadas son muy útiles cuando necesita hacer muchas inserciones y eliminaciones, pero no demasiadas búsquedas, en una lista de longitud arbitraria (desconocida en tiempo de compilación).

Dividir y unir listas (enlazadas bidireccionalmente) es muy eficaz.

También puede combinar listas vinculadas, por ejemplo, las estructuras de árbol se pueden implementar como listas vinculadas "verticales" (relaciones padre / hijo) que conectan listas vinculadas horizontales (hermanos).

El uso de una lista basada en matrices para estos fines tiene graves limitaciones:

• Agregar un nuevo elemento significa que la matriz debe reasignarse (o debe asignar más espacio del necesario para permitir el crecimiento futuro y reducir la cantidad de reasignaciones)
• Eliminar elementos deja espacio desperdiciado o requiere una reasignación
• insertar elementos en cualquier lugar excepto al final implica (posiblemente reasignar y) copiar muchos datos en una posición

Las listas enlazadas son muy flexibles: con la modificación de un puntero, puede hacer un cambio masivo, donde la misma operación sería muy ineficiente en una lista de arreglos.

Las matrices son las estructuras de datos con las que se suelen comparar las listas vinculadas.

Las listas normalmente vinculadas son útiles cuando tiene que hacer muchas modificaciones a la lista en sí, mientras que las matrices funcionan mejor que las listas en el acceso directo a elementos.

Aquí hay una lista de operaciones que se pueden realizar en listas y matrices, en comparación con el costo de operación relativo (n = longitud de lista / matriz):

• Agregar un elemento:
  • en las listas, solo necesita asignar memoria para el nuevo elemento y redireccionar punteros. O (1)
  • en matrices, debe reubicar la matriz. En)
• Eliminar un elemento
  • en las listas, simplemente redirige los punteros. O (1).
  • en matrices, pasa O (n) tiempo para reubicar la matriz si el elemento a eliminar no es el primero o el último elemento de la matriz; de lo contrario, simplemente puede reubicar el puntero al inicio de la matriz o disminuir la longitud de la matriz
• Obtener un elemento en una posición conocida:
  • en las listas, debe recorrer la lista desde el primer elemento hasta el elemento en la posición específica. Peor caso: O (n)
  • en matrices puede acceder al elemento inmediatamente. O (1)

Esta es una comparación de muy bajo nivel de estas dos estructuras de datos básicas y populares y puede ver que las listas funcionan mejor en situaciones en las que tiene que hacer muchas modificaciones a la lista en sí (eliminar o agregar elementos). Por otro lado, las matrices funcionan mejor que las listas cuando tienes que acceder directamente a los elementos de la matriz.

Desde el punto de vista de la asignación de memoria, las listas son mejores porque no es necesario tener todos los elementos uno al lado del otro. Por otro lado, existe la (pequeña) sobrecarga de almacenar los punteros al siguiente (o incluso al anterior) elemento.

Conocer estas diferencias es importante para que los desarrolladores elijan entre listas y matrices en sus implementaciones.

Tenga en cuenta que esta es una comparación de listas y matrices. Hay buenas soluciones a los problemas aquí reportados (por ejemplo: SkipLists, Dynamic Arrays, etc.). En esta respuesta, he tenido en cuenta la estructura de datos básica que todo programador debe conocer.

La lista enlazada individualmente es una buena opción para la lista libre en un asignador de células o grupo de objetos:

1. Solo necesita una pila, por lo que una lista con un solo enlace es suficiente.
2. Todo ya está dividido en nodos. No hay sobrecarga de asignación para un nodo de lista intrusivo, siempre que las celdas sean lo suficientemente grandes para contener un puntero.
3. Un vector o deque impondría una sobrecarga de un puntero por bloque. Esto es significativo dado que cuando crea el montón por primera vez, todas las celdas son gratuitas, por lo que es un costo inicial. En el peor de los casos, duplica el requisito de memoria por celda.

La lista doblemente enlazada es una buena opción para definir el orden de un mapa hash que también define un orden en los elementos (LinkedHashMap en Java), especialmente cuando se ordena por último acceso:

1. Más sobrecarga de memoria que un vector o deque asociado (2 punteros en lugar de 1), pero mejor rendimiento de inserción / eliminación.
2. Sin gastos generales de asignación, ya que de todos modos necesita un nodo para una entrada hash.
3. La localidad de referencia no es un problema adicional en comparación con un vector o deque de punteros, ya que tendría que extraer cada objeto en la memoria de cualquier manera.

Claro, puede discutir si un caché LRU es una buena idea en primer lugar, en comparación con algo más sofisticado y sintonizable, pero si va a tener uno, esta es una implementación bastante decente. No desea realizar una eliminación desde el medio y agregar hasta el final en un vector o deque en cada acceso de lectura, pero mover un nodo a la cola suele estar bien.

Las listas vinculadas son una de las opciones naturales cuando no puede controlar dónde se almacenan sus datos, pero aún necesita pasar de un objeto al siguiente.

Por ejemplo, al implementar el seguimiento de memoria en C ++ (reemplazo nuevo / eliminar), necesita alguna estructura de datos de control que realice un seguimiento de los punteros que se han liberado, que debe implementar usted mismo. La alternativa es sobreasignar y agregar una lista vinculada al comienzo de cada fragmento de datos.

Debido a que siempre sabe inmediatamente dónde se encuentra en la lista cuando se llama a eliminar, puede ceder fácilmente la memoria en O (1). También se agrega un nuevo fragmento que se acaba de colocar mal en O (1). En este caso, raramente se necesita caminar por la lista, por lo que el costo O (n) no es un problema aquí (caminar una estructura es O (n) de todos modos).

Son útiles cuando necesita empujar, saltar y girar a alta velocidad, y no le importa la indexación O (n).

Las listas unidas son la implementación obvia del tipo de datos de "lista" común en los lenguajes de programación funcionales:

1. Agregar a la cabeza es rápido (append (list x) (L))y (append (list y) (L))puede compartir casi todos sus datos. No es necesario copiar sobre escritura en un idioma sin escritura. Los programadores funcionales saben cómo aprovechar esto.
2. Desafortunadamente, agregar al final es lento, pero también lo sería cualquier otra implementación.

En comparación, un vector o deque normalmente sería lento para agregar en cualquier extremo, requiriendo (al menos en mi ejemplo de dos anexos distintos) que se tome una copia de la lista completa (vector), o el bloque de índice y el bloque de datos siendo añadido a (deque). En realidad, puede haber algo que decir para deque en listas grandes que necesitan agregar al final por alguna razón, no estoy lo suficientemente informado sobre programación funcional para juzgar.

Un ejemplo de buen uso de una lista enlazada es cuando los elementos de la lista son muy grandes, es decir. lo suficientemente grande como para que solo uno o dos puedan caber en la memoria caché de la CPU al mismo tiempo. En este punto, la ventaja que tienen los contenedores de bloques contiguos como vectores o matrices para iteración se anula más o menos, y puede ser posible una ventaja de rendimiento si se producen muchas inserciones y eliminaciones en tiempo real.

Desde mi experiencia, implementando matrices dispersas y montones de fibonacci. Las listas vinculadas le brindan más control sobre la estructura general de dichas estructuras de datos. Aunque no estoy seguro de si las matrices dispersas se implementan mejor usando listas vinculadas, probablemente haya una mejor manera, pero realmente ayudó a aprender los entresijos de las matrices dispersas usando listas vinculadas en pregrado CS :)

Hay dos operaciones complementarias que son trivialmente O (1) en las listas y muy difíciles de implementar en O (1) en otras estructuras de datos: eliminar e insertar un elemento desde una posición arbitraria, asumiendo que necesita mantener el orden de los elementos.

Los mapas hash obviamente pueden hacer inserción y eliminación en O (1) pero luego no puede iterar sobre los elementos en orden.

Dado el hecho anterior, el mapa hash se puede combinar con una lista vinculada para crear un caché LRU ingenioso: un mapa que almacena un número fijo de pares clave-valor y suelta la clave a la que se accedió menos recientemente para dejar espacio para otras nuevas.

Las entradas en el mapa hash deben tener punteros a los nodos de la lista vinculada. Al acceder al mapa hash, el nodo de la lista vinculada se desvincula de su posición actual y se mueve al encabezado de la lista (O (1), ¡yay para listas vinculadas!). Cuando sea necesario eliminar el elemento utilizado menos recientemente, el de la cola de la lista debe eliminarse (nuevamente O (1) asumiendo que mantiene el puntero en el nodo de cola) junto con la entrada del mapa hash asociado (por lo tanto, los backlinks de la lista del mapa hash son necesarias).

Tenga en cuenta que una lista vinculada puede ser muy útil en una implementación de estilo de diseño dirigido por dominio de un sistema que incluye partes que se entrelazan con la repetición.

Un ejemplo que me viene a la mente podría ser si estuviera modelando una cadena colgante. Si desea saber cuál es la tensión en un enlace en particular, su interfaz podría incluir un captador de peso "aparente". La implementación de lo cual incluiría un enlace preguntando a su siguiente enlace por su peso aparente, luego agregando su propio peso al resultado. De esta forma, toda la longitud hasta el fondo se evaluaría con una sola llamada del cliente de la cadena.

Siendo un defensor del código que se lee como lenguaje natural, me gusta cómo esto permitiría al programador preguntarle a un eslabón de la cadena cuánto peso lleva. También mantiene la preocupación de calcular estos hijos de propiedades dentro de los límites de la implementación del enlace, eliminando la necesidad de un servicio de cálculo del peso de la cadena ".

Uno de los casos más útiles que encuentro para las listas vinculadas que trabajan en campos críticos para el rendimiento como el procesamiento de imágenes y mallas, motores de física y trazado de rayos es cuando el uso de listas vinculadas en realidad mejora la localidad de referencia y reduce las asignaciones de montón y, a veces, incluso reduce el uso de memoria en comparación con las alternativas sencillas.

Ahora, eso puede parecer un completo oxímoron de que las listas enlazadas podrían hacer todo eso, ya que son conocidas por hacer a menudo lo contrario, pero tienen una propiedad única en el sentido de que cada nodo de lista tiene un tamaño fijo y requisitos de alineación que podemos aprovechar para permitir. para que se almacenen de forma contigua y se eliminen en tiempo constante de formas que las cosas de tamaño variable no pueden.

Como resultado, tomemos un caso en el que queremos hacer el equivalente analógico de almacenar una secuencia de longitud variable que contiene un millón de subsecuencias de longitud variable anidadas. Un ejemplo concreto es una malla indexada que almacena un millón de polígonos (algunos triángulos, algunos quads, algunos pentágonos, algunos hexágonos, etc.) y, a veces, los polígonos se eliminan de cualquier lugar de la malla y, a veces, los polígonos se reconstruyen para insertar un vértice en un polígono existente o quitar uno. En ese caso, si almacenamos un millón de pequeños std::vectors, terminamos enfrentando una asignación de montón para cada vector, así como un uso de memoria potencialmente explosivo. Un millón de minúsculos SmallVectorspodría no sufrir este problema tanto en los casos comunes, pero entonces su búfer preasignado que no está asignado al montón por separado podría causar un uso explosivo de la memoria.

El problema aquí es que un millón de std::vectorinstancias intentarían almacenar un millón de cosas de longitud variable. Las cosas de longitud variable tienden a querer una asignación de montón, ya que no se pueden almacenar de manera muy efectiva de forma contigua y eliminar en tiempo constante (al menos de una manera sencilla sin un asignador muy complejo) si no almacenaron su contenido en otra parte del montón.

Si, en cambio, hacemos esto:

struct FaceVertex
{
    // Points to next vertex in polygon or -1
    // if we're at the end of the polygon.
    int next;
    ...
};

struct Polygon
{
     // Points to first vertex in polygon.
    int first_vertex;
    ...
};

struct Mesh
{
    // Stores all the face vertices for all polygons.
    std::vector<FaceVertex> fvs;

    // Stores all the polygons.
    std::vector<Polygon> polys;
};

... luego hemos reducido drásticamente el número de asignaciones de montón y fallas de caché. En lugar de requerir una asignación de almacenamiento dinámico y pérdidas de caché potencialmente obligatorias para cada polígono al que accedemos, ahora solo requerimos esa asignación de almacenamiento dinámico cuando uno de los dos vectores almacenados en toda la malla excede su capacidad (un costo amortizado). Y aunque la zancada para ir de un vértice al siguiente todavía puede causar su parte de fallas de caché, a menudo es menor que si cada polígono almacenara una matriz dinámica separada, ya que los nodos se almacenan contiguamente y existe la probabilidad de que un vértice vecino pueda ser accedido antes del desalojo (especialmente considerando que muchos polígonos agregarán sus vértices todos a la vez, lo que hace que la mayor parte de los vértices de los polígonos sean perfectamente contiguos).

Aquí hay otro ejemplo:

... donde las celdas de la cuadrícula se utilizan para acelerar la colisión entre partículas para, digamos, 16 millones de partículas que se mueven en cada cuadro. En ese ejemplo de cuadrícula de partículas, usando listas vinculadas podemos mover una partícula de una celda de cuadrícula a otra simplemente cambiando 3 índices. Borrar de un vector y regresar a otro puede ser considerablemente más caro e introducir más asignaciones de montón. Las listas enlazadas también reducen la memoria de una celda a 32 bits. Un vector, dependiendo de la implementación, puede preasignar su matriz dinámica hasta el punto en que puede tomar 32 bytes para un vector vacío. Si tenemos alrededor de un millón de celdas de cuadrícula, eso es una gran diferencia.

... y aquí es donde encuentro que las listas vinculadas son más útiles en estos días, y específicamente encuentro útil la variedad de "listas vinculadas indexadas" ya que los índices de 32 bits reducen a la mitad los requisitos de memoria de los vínculos en máquinas de 64 bits e implican que el los nodos se almacenan de forma contigua en una matriz.

A menudo, también los combino con listas gratuitas indexadas para permitir eliminaciones e inserciones en tiempo constante en cualquier lugar:

En ese caso, el nextíndice apunta al siguiente índice libre si el nodo se ha eliminado o al siguiente índice utilizado si el nodo no se ha eliminado.

Y este es el caso de uso número uno que encuentro para las listas enlazadas en estos días. Cuando queremos almacenar, digamos, un millón de subsecuencias de longitud variable promediando, digamos, 4 elementos cada una (pero a veces con elementos que se eliminan y se agregan a una de estas subsecuencias), la lista enlazada nos permite almacenar 4 millones nodos de lista enlazados de forma contigua en lugar de 1 millón de contenedores, cada uno de los cuales se asigna individualmente al montón: un vector gigante, es decir, no un millón de pequeños.

He usado listas enlazadas (incluso listas doblemente enlazadas) en el pasado en una aplicación C / C ++. Esto fue antes de .NET e incluso stl.

Probablemente no usaría una lista vinculada ahora en un lenguaje .NET porque todo el código transversal que necesita se le proporciona a través de los métodos de extensión Linq.