¿Cuáles son los ejemplos del mundo real de cuándo deben usarse las listas vinculadas?

Question

Otro programador mencionó que no han encontrado un caso de uso para usar una estructura de datos de lista vinculada en ningún software profesional en su carrera. No podía pensar en ningún buen ejemplo fuera de mi cabeza. Él es principalmente un C# y desarrollador Java

¿Alguien puede dar algunos ejemplos donde esta era la estructura de datos correcta para resolver un problema particular del mundo real?

relacionadas:What is a practical, real world example of the Linked List?

Answer 1

Un ejemplo del mundo real sería una cola FIFO. Una simple lista basada en arreglos es bastante mala porque tiene que agregar en un extremo y eliminar en el otro extremo, y una de esas operaciones será O (n) con una lista basada en arreglos (a menos que agregue lógica extra a trabajar con un índice de inicio y fin), mientras que ambos son O (1) con una lista vinculada sin esfuerzo adicional.

Answer 2

pilas y colas son ejemplos de listas enlazadas.

Answer 3

Para los problemas donde el número máximo de nodos está restringido a 100 o menos, las listas vinculadas son una solución razonable. Lo mismo puede ser cierto para cosas como sortear burbujas y otras cosas que se consideran subóptimas.

Answer 4

Las listas vinculadas ofrecen varias ventajas sobre las estructuras de datos comparables, como las matrices estáticas o dinámicamente en expansión.

1. LinkedLists no dosis requieren bloques contiguos de memoria y por lo tanto pueden ayudar a reducir la fragmentación de la memoria
2. LinkedLists apoyan la eliminación eficaz de los elementos (matrices dinámicas usualmente forzar un cambio en todos los elementos).
3. LinkedLists apoyan adición eficiente de los elementos (matrices dinámicas pueden causar una re-asignación + copiar si un add particular excede la capacidad actual)

Cualquier lugar donde estas ventajas serían significativamente valiosa para un programa (y el las desventajas de una LinkedList eran insignificantes) sería un lugar para usar LinkedList.

Answer 5

Como señala daustin777, las listas vinculadas están a su alrededor y puede que ni siquiera lo sepa. Pero lo práctico del asunto es que permiten realizar algunas operaciones bastante básicas con relativa facilidad y flexibilidad. Por ejemplo, para no ordenar, simplemente intercambie punteros. ¿Necesitas insertar o quitar en lugares arbitrarios? Inserta o elimina tus punteros dentro de la lista. Necesidad de iterar hacia adelante y hacia atrás ... lista vinculada. Si bien no es precisamente un ejemplo de negocio, espero que esto lo aclare lo suficiente como para que pueda aplicarlo a su propio caso comercial del mundo real.

Answer 6

inmutable lista vinculada es una estructura muy valiosa, ya que puede 'compartir estructura' con otras listas con la misma cola. La mayoría de los lenguajes funcionales incluyen un tipo de lista vinculada inmutable como una de sus estructuras de datos fundamentales, y estos tipos se utilizan en todas partes.

Answer 7

Vinculados pros lista:

• almacenamiento dinámico anula fragmentación
• inserción/retirada rápida
• Acceso rápido a primer elemento (y terminar si bidireccional implementado)
• uso eficiente de la memoria

Lista enlazada contras:

• desplazamiento lento

Fuera de mi cabeza, me gustaría implementar pilas, colas y messagepumps utilizando listas enlazadas. También implementaría un árbol de datos usando listas enlazadas de referencias múltiples para una inserción/eliminación rápida.

Answer 8

pilas y colas son ejemplos muy claros de las listas enlazadas, pero como otros ya los han mencionado que desea añadir algunos otros ejemplos: almacena

DOM nodos como listas enlazadas. Una muestra javascript simple que es realmente lo mismo en cualquier idioma:

for (var node = parent.firstChild; node != null; node = node.nextSibling) { 
    // .. 
} 

me imaginaría que un desarrollador de Java ha llegado a través de XML en algún momento.

Los árboles son otros buenos ejemplos de listas vinculadas, aunque no son simples de una dimensión. Alguien que ha hecho mucho desarrollo Java probablemente se haya topado con TreeMaps y TreeSets.

Toda la discusión me parece un poco tonta. Las listas vinculadas son una estructura de datos fundamental que se utiliza en todas partes. La única razón por la que uno podría pensar que no se ha encontrado con ellos es que realmente no tiene que preocuparse por la implementación de las estructuras de datos en los lenguajes de alto nivel de hoy en día, pero por supuesto todavía están allí.

Answer 9

Ocurren todo el tiempo, en cualquier lugar, un objeto tiene una propiedad que apunta a otro objeto del mismo tipo. En el CLR, las excepciones forman una lista vinculada, debido a la propiedad InnerException.

Answer 10

Como dije, las listas ya enlazadas son muy útiles cuando necesita insertar y eliminar elementos.

Por ejemplo, para ayudar a depurar la gestión de memoria en mi código recientemente implementé una lista de enlaces entre todos mis objetos contados de refrencia para que al final del programa (cuando todas las referencias llegaran a cero y eliminaran los objetos) pudiera veo exactamente lo que quedaba, lo que resulta en que pueda encontrar un solo objeto en la raíz del problema.

CPython implementa algo similir con una lista masiva vinculados entre casi todos cuando su construcción con la depuración.

Answer 11

Intrusive listas vinculadas son bestias interesantes para el desarrollo del juego.Por ejemplo, es una práctica común tanto para tener una intrusa o por enlaces sencillos doblemente ligado a "hacer" la lista:

 
class Renderable /* or class Object, whatever */ 
{ 
    // ... 
    Renderable * m_pNext; 
    Renderable * m_pPrev; // or not, if singly-linked 
    // ... 
} 

Como Renderables vienen dentro y fuera de la existencia pueden registrarse en esta lista - sin causar ningún recuerdo asignación. Si se modifican la profundidad o la profundidad de su renderizado, pueden eliminarse y reinsertarse, etc.

Cuando llega el momento de renderizar, todo lo que necesita hacer es encontrar el encabezado de la lista y abrirla, llamando al método apropiado.

(Hay, por supuesto, muchas variaciones en este tema, con múltiples listas separadas, etc. Y no necesita tener una lista intrusiva para hacer que esto funcione, solo encuentro intrusivas interesantes.)

Answer 12

Las listas vinculadas (paired with a hashtable) son realmente útiles para LRU Caches.

Cada Obtener necesita colocar un nodo al frente de la lista, una operación que es realmente barata con listas enlazadas.

Answer 13

Respondiendo a la etiqueta 'Estructuras de datos', a un nivel bajo, como el ensamblaje, las listas vinculadas son una forma ideal de almacenar listas de longitud variable de otras estructuras de datos. No hay gastos generales para mantener la longitud o el final de la lista, y no hay necesidad de elementos de lista de tamaño fijo. La última razón también se aplica a los idiomas de nivel superior.

Answer 14

Como quizás el mejor ejemplo del mundo real en .Net considere el MultiCastDelegate.

Las listas vinculadas implementadas de esta manera, donde el aspecto de encadenamiento de listas se respalda directamente en el tipo en lugar de como un contenedor separado, pueden ser extremadamente potentes y eficientes. Sin embargo, vienen con una variedad de compensaciones.
Uno obvio es la duplicación de código, debe hornear esta lógica en cada tipo. Las técnicas como extender una clase base que proporciona el puntero son complicadas (se pierde una escritura fuerte sin genéricos) y, a menudo, son inaceptables desde el punto de vista del rendimiento.
Otra es que está limitado a una implementación por tipo. No puede convertir una estructura enlazada individualmente en una estructura doblemente vinculada sin insertar un campo adicional en cada instancia y actualizar todo el código relevante.

Answer 15

Escribí una extensión de BIOS (básicamente un controlador de dispositivo para un BIOS, escrito en el ensamblaje) para un controlador de host USB. - La implementación de una estructura de datos aparentemente abstracta de alto nivel, como una lista vinculada en el ensamblaje, no es tan difícil como parece. - El controlador atendió las solicitudes de E/S para teclado y disco utilizando una lista vinculada de paquetes en la memoria principal. Mantuve un conjunto de paquetes gratuitos en otra lista vinculada. La ejecución de E/S básicamente implicaba tomar un paquete gratis desde el comienzo de la lista gratuita, configurar el paquete, agregar el paquete a la lista del dispositivo y volver a agregar el paquete al comienzo del grupo libre cuando finalizaba la E/S. Las listas vinculadas son muy rápidas para moverse por objetos como este, especialmente cuando los objetos son grandes, ya que los objetos en realidad no tienen que moverse. Solo sus punteros necesitan ser actualizados.

Una cola basada en arreglos habría requerido:

• utilizando un/puntero del índice final comenzará, que es rápido pero requiere fijar el tamaño de la cola para que el productor tiene que esperar cuando la cola del consumidor es completa y bloqueo de la cola mientras el paquete entero se llena si hay más de un productor
• cambiando todos los elementos en la cola siempre que insertar/eliminar, que es lento para grandes objetos

enumera lo tanto, vinculados son una buena manera de implementar un n cola de primeros en entrar, primero en salir, arbitrariamente larga, de objetos grandes.

Otra cosa a tener en cuenta es que para objetos pequeños o donde se asignan objetos desde un montón convencional en lugar de un grupo libre personalizado, las matrices pueden ser más rápidas porque la copia no es tan lenta si no se realiza con frecuencia. y la asignación repetida del montón que una lista vinculada requeriría cada vez que se agrega un nuevo elemento es lenta.

Por supuesto, es posible que desee simular y medir su situación particular con algún código de prueba desechable para encontrar la respuesta. Me gusta ejecutar bucles algunos millones de veces con listas y matrices vinculadas, con objetos pequeños y grandes, y el tiempo de cada uno en tiempo real. Algunas veces te sorprenderás.

Answer 16

lista vinculada es la estructura esencial de datos para Dancing Links, que es la técnica utilizada para aplicar eficazmente Algorithm X, que es un algoritmo de retroceso para encontrar todas las soluciones para el NP-completo exact cover problema, al que muchos problemas difíciles son naturalmente reducible a .

Answer 17

Si puedo responder a esta pregunta de una manera ligeramente diferente a la que otros tienen, últimamente he estado usando listas enlazadas para organizar listas de música. Las listas proporcionan una excelente manera de almacenar y ordenar música por artista, canción, álbum, incluso calificaciones o duración de la canción. La mía es una lista doblemente vinculada, pero podría ver que también es aplicable con una lista individualmente vinculada. Las listas de compras también encajarían, y si usted es TOC como mi mamá, ¡puede organizarlo fácilmente en el pasillo y congelar alimentos!

Si incluimos stacks y colas, lo más obvio para las colas es una cola de impresión o una lista de reproducción de música (las listas en cualquier sentido son buenas obviamente).

Answer 18

Algunos ejemplos de listas de enlaces individuales.

1. botón Deshacer de cualquier aplicación como Microsoft Word, Paint, etc: Una lista enlazada de estados.
2. Navegación GPS: una lista vinculada de datos de mapas. Viajar de origen a destino es un ejemplo de atravesar todos los nodos. El reencaminamiento por un GPS es un ejemplo de operaciones de Agregar y quitar datos del mapa.

Algunos ejemplos de lista de doble enlace.

1. del navegador Siguiente y el botón Anterior: una lista enlazada de URLs Microsoft
2. imagen del espectador al lado y el botón Anterior: una lista enlazada de imágenes
3. Deshacer y botón de Photoshop, una lista enlazada de estados Rehacer.