language agnostic - linked - ¿En qué circunstancias son útiles las listas vinculadas?

linked list javascript

Question

La mayoría de las veces que veo que las personas intentan usar listas vinculadas, me parece una opción pobre (o muy pobre). Tal vez sería útil explorar las circunstancias bajo las cuales una lista vinculada es o no una buena opción de estructura de datos.

Idealmente, las respuestas expondrían los criterios a utilizar para seleccionar una estructura de datos, y qué estructuras de datos probablemente funcionen mejor bajo circunstancias específicas.

Editar: Debo decir que estoy impresionado no solo por el número, sino por la calidad de las respuestas. Solo puedo aceptar uno, pero hay dos o tres más que diría que hubieran valido la pena aceptar si algo mejor no hubiera estado allí. Solo una pareja (especialmente la que terminé aceptando) señaló situaciones en las que una lista vinculada proporcionaba una ventaja real. Creo que Steve Jessop merece una mención honorífica por haber presentado no solo una, sino tres respuestas diferentes, todas las cuales encontré bastante impresionantes. Por supuesto, a pesar de que se publicó solo como un comentario, no como una respuesta, creo que la entrada al blog de Neil también vale la pena leerla, no solo informativa, sino también bastante entretenida.

Answer 1

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

Answer 2

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

Los mapas hash obviamente pueden insertar y borrar 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 descarta la clave accedida menos recientemente para dejar espacio para los nuevos.

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 las listas enlazadas!). Cuando hay necesidad de eliminar el elemento utilizado menos recientemente, el que está en la cola de la lista debe soltarse (O (1) suponiendo que mantiene el puntero al nodo de cola) junto con la entrada de mapa hash asociada (por lo que los vínculos de retroceso de la lista al mapa hash es necesaria).

Answer 3

He utilizado listas vinculadas (incluso listas doblemente vinculadas) 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 de Linq.

Answer 4

La lista Singly-linked es una buena opción para la lista gratuita en un asignador de celda o conjunto de objetos:

1. Solo necesitas una pila, por lo que una lista con un solo enlace es suficiente.
2. Todo está dividido en nodos ya. No hay sobrecarga de asignación para un nodo de lista intrusiva, siempre que las celdas sean lo suficientemente grandes como para contener un puntero.
3. Un vector o deque impondría una sobrecarga de un puntero por bloque. Esto es importante 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.

Answer 5

La lista doblemente enlazada es una buena opción para definir el orden de un hashmap 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 asociado o deque (2 punteros en lugar de 1), pero es mejor insertar / eliminar el rendimiento.
2. Sin sobrecarga de asignación, ya que necesita un nodo para una entrada de hash de todos modos.
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 tirar cada objeto a la memoria de cualquier manera.

Claro, puedes discutir si un caché LRU es una buena idea en primer lugar, en comparación con algo más sofisticado y sintonizable, pero si vas a tener uno, esta es una implementación bastante decente. No desea realizar un delete-from-middle-and-add-to-the-end en un vector o deque en cada acceso de lectura, pero mover un nodo a la cola normalmente es correcto.

Answer 6

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

1. Agregar a la cabecera es rápido, y (append (list x) (L)) y (append (list y) (L)) pueden compartir casi todos sus datos. No es necesario copiar y escribir en un idioma sin escrituras. Los programadores funcionales saben cómo aprovechar esto.
2. Agregar a la cola desafortunadamente es lento, pero también lo sería cualquier otra implementación.

En comparación, un vector o deque normalmente sería lento de agregar en cada extremo, requiriendo (al menos en mi ejemplo de dos adjuntos distintos) que se tome una copia de la lista completa (vector), o del bloque de índice y el bloque de datos siendo anexado a (deque). En realidad, puede que haya algo que decir allí para deque en las listas grandes que es necesario agregar en la cola por alguna razón, no estoy lo suficientemente informado sobre la programación funcional para juzgar.

Answer 7

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).

La división y unión (listas bidireccionales) es muy eficiente.

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

Usar una lista basada en arreglos para estos propósitos tiene severas limitaciones:

• Agregar un nuevo elemento significa que la matriz debe ser reasignada (o debe asignar más espacio del que necesita para permitir el crecimiento futuro y reducir el número de reasignaciones)
• La eliminación de elementos deja espacio desperdiciado o requiere una reasignación
• insertar elementos en cualquier lugar excepto el final implica (posiblemente reasignar y) copiar muchos de los datos en una posición

Answer 8

Las listas vinculadas 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 matriz.

Answer 9

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

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

Como siempre sabe de manera inmediata, donde se encuentra en la lista cuando se llama a delete, puede renunciar fácilmente a la memoria en O (1). Además, agregar un nuevo trozo que acaba de ser mallar está en O (1). En este caso, rara vez se necesita recorrer la lista, por lo que el costo de O (n) no es un problema (caminar de todos modos con una estructura es O (n)).

Answer 10

Las matrices son las estructuras de datos con las que habitualmente se comparan las listas vinculadas.

Normalmente, las listas vinculadas son útiles cuando tiene que realizar muchas modificaciones en la lista, mientras que las matrices rinden mejor que las listas en el acceso directo a los 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 = list / array length):

• Agregar un elemento:
  • en listas solo necesita asignar memoria para el nuevo elemento y redirigir punteros. O (1)
  • en las matrices debes reubicar la matriz. En)
• Eliminar un elemento
  • en las listas que acaba de redirigir punteros. O (1).
  • en matrices, gasta O (n) tiempo para reubicar la matriz si el elemento para eliminar no es el primero ni el último elemento de la matriz; de lo contrario, puede simplemente 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 de inmediato. O (1)

Esta es una comparación de bajo nivel de estas dos estructuras de datos populares y básicas, y puede ver que las listas funcionan mejor en situaciones en las que tiene que hacer muchas modificaciones en la lista (eliminando o agregando elementos). Por otro lado, las matrices rinden mejor que las listas cuando tiene 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, está la (pequeña) sobrecarga de almacenar los punteros al elemento siguiente (o incluso al anterior).

Conocer estas diferencias es importante para los desarrolladores para elegir 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, tomé en cuenta la estructura básica de datos que todo programador debería conocer.

Answer 11

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

Por ejemplo, ConcurrentDictionary<TKey, TValue> en .NET 4.0 RC utiliza listas vinculadas para encadenar elementos que tienen hash en el mismo segmento.

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 de base para el nuevo conjunto de subprocesos (con las "colas" locales implementadas como stacks, en esencia). (La otra estructura de soporte principal es ConcurrentQueue<T> .)

El nuevo grupo de subprocesos, a su vez, proporciona la base para la programación de trabajo de la nueva biblioteca de tareas paralelas .

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

(En estos casos, una lista enlazada individualmente hace una elección convincente, sin lock-free , pero no de espera, 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 ABA se puede evitar fácilmente. Simplemente ajuste los elementos que agregue en los nodos recién creados y no reutilice esos nodos, deje que el GC haga su trabajo. La página sobre el problema ABA también proporciona la implementación de un bloqueo. pila libre - que realmente funciona en .Net (y Java) con un nodo (GC-ed) que contiene los elementos).

Edit : @Neil: de hecho, lo que mencionaste sobre FORTRAN me recordó que el mismo tipo de listas enlazadas se puede encontrar en la estructura de datos probablemente más usada y abusada en .NET: el .NET generic Dictionary<TKey, TValue> .

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

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

Esencialmente, muchas listas vinculadas se almacenan en una matriz. (uno para cada cubo utilizado.) Una lista libre de nodos reutilizables está "entretejida" entre ellos (si hubo eliminaciones). Una matriz se asigna al principio / al repetición y los nodos de cadenas se mantienen en ella. También hay un puntero libre , un índice en la matriz, que sigue elimina. ;-) Entonces, créalo o no, la técnica de FORTRAN aún vive. (... y en ninguna otra parte, que en una de las estructuras de datos .NET más comúnmente utilizadas ;-).

Answer 12

Son útiles cuando necesita alta velocidad, pop y rotación, y no le importa la indexación O (n).

Answer 13

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 viene a la mente podría ser si estuvieras modelando una cadena colgante. Si quería saber cuál era la tensión en un enlace en particular, su interfaz podría incluir un captador de peso "aparente". La implementación de la cual incluiría un enlace en el siguiente enlace para su peso aparente, y luego agregaría su propio peso al resultado. De esta forma, toda la longitud hasta la parte inferior se evaluaría con una sola llamada del cliente de la cadena.

Al ser un defensor del código que se lee como lenguaje natural, me gusta cómo esto le permite al programador preguntarle a un enlace de cadena cuánto peso está cargando. También mantiene la preocupación de calcular estos hijos de propiedades dentro del límite de la implementación del enlace, eliminando la necesidad de un servicio de cálculo de peso de la cadena ".

Answer 14

Un ejemplo de buen uso para una lista vinculada 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 es más o menos anulada, y una ventaja de rendimiento puede ser posible si se realizan muchas inserciones y eliminaciones en tiempo real.

Answer 15

Uno de los casos más útiles que encuentro para listas vinculadas que trabajan en campos de rendimiento crítico como malla y procesamiento de imágenes, motores de física y trazado de rayos es cuando el uso de listas enlazadas realmente mejora la ubicación de referencia y reduce las asignaciones de montón e incluso reduce el uso de memoria comparado con las alternativas directas.

Ahora puede parecer un oxímoron completo que las listas vinculadas podrían hacer todo eso, ya que son notorias porque a menudo hacen 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 contiguamente y se eliminen en tiempo constante de forma que las cosas de tamaño variable no puedan.

Como resultado, consideremos 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 anidadas de longitud variable. 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 parte de la malla y, a veces, se reconstruyen polígonos para insertar un vértice en un polígono o eliminar uno En ese caso, si almacenamos un millón de pequeños std::vectors , entonces terminaremos enfrentando una asignación de montón para cada vector, así como el uso potencialmente explosivo de la memoria. Un millón de pequeños SmallVectors podrían no sufrir este problema tanto en casos comunes, pero luego su buffer preasignado que no está asignado por separado puede seguir causando un uso explosivo de memoria.

El problema aquí es que un millón de instancias std::vector 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 contigua y se eliminan en tiempo constante (al menos de forma directa sin un asignador muy complejo) si no almacenan sus contenidos en otro lugar en el 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;
};

... entonces hemos reducido drásticamente la cantidad de asignaciones de heap y errores de caché. En lugar de requerir una asignación de pila y fallas de caché potencialmente obligatorias para cada polígono al que accedemos, ahora solo requerimos esa asignación de pila cuando uno de los dos vectores almacenados en la malla completa excede su capacidad (un costo amortizado). Y aunque el paso para llegar de un vértice al próximo puede causar su cuota 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 hay una probabilidad de que un vértice vecino pueda se debe acceder antes del desalojo (especialmente teniendo en cuenta que muchos polígonos agregarán sus vértices de una vez, lo que hace que la mayor parte de los vértices de los polígonos estén perfectamente contiguos).

Aquí hay otro ejemplo:

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

... y aquí es donde encuentro que las listas vinculadas son más útiles actualmente, y específicamente encuentro útil la variedad de "listas enlazadas indexadas" ya que los índices de 32 bits reducen a la mitad los requisitos de memoria de los enlaces en máquinas de 64 bits e implican que los nodos se almacenan contiguamente en una matriz.

A menudo también los combino con listas libres indexadas para permitir remociones e inserciones de 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 vinculadas 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 enlazó los nodos de la lista de forma contigua en lugar de 1 millón de contenedores, cada uno asignado de forma individual: un vector gigante, es decir, no un millón de pequeños.