collections - sistema - ¿Qué es un ejemplo práctico y real de la Lista Vinculada?
escrito de formulacion de acusacion (30)
¡El mejor y sencillo ejemplo de una lista doblemente enlazada es Train!
Aquí cada entrenador está conectado a su entrenador anterior y siguiente (excepto el primero y el último)
En términos de programación, considere el cuerpo del entrenador como nodo de datos (valor) y el conector como nodo de referencia.
Entiendo la definición de una lista vinculada, pero ¿cómo puede representarse y relacionarse con un concepto o elemento común?
Por ejemplo, la composición (EDIT: originalmente dijo ''herencia'') en OOP se puede relacionar con los automóviles. Todos los automóviles (la mayoría) en la vida real son esencialmente lo mismo; un automóvil tiene un motor, puede arrancarlo (), puede hacer que el automóvil entre (), pare () y así sucesivamente. Un automóvil típicamente tendría una capacidad máxima de pasajeros, pero diferiría entre un autobús y una SportsCar, que son ambos automóviles.
¿Hay algún ejemplo intuitivo de la vida real de la lista enlazada individualmente como la que tenemos con la herencia? El ejemplo típico de lista de enlaces de libros de texto muestra un nodo con un entero y un puntero al siguiente, y no parece muy útil.
Se agradece su entrada.
Considere 2 o más cajas que tienen 2 o más compartimentos. (en este ejemplo, cada caja tendrá 2 compartimentos) el primer compartimiento contendrá información. un número o una palabra el segundo compartimiento mantendrá una flecha que apunta al siguiente cuadro y así sucesivamente.
tenga en cuenta que cada caja puede contener compartimentos de varias escalas que contienen flechas (punteros) e información (datos).
Dar indicaciones de viaje: con cada paso en las direcciones como un nodo, y la instrucción de viaje entre cada nodo como su enlace.
Ejemplo:
Nodo 1: Comience en casa
Enlace: Camine 3 cuadras al sur de la casa de Bob
Nodo 2: la casa de Bob
Enlace: Camine 2 cuadras al norte de la casa de Alicia.
Nodo 3: la casa de Alicia.
Si desea ir de un lugar a otro, debe seguir los enlaces (instrucciones) de cada lugar intermedio (nodo), no puede saltar de la casa a la de Alice.
Dentro del programa make , a menudo encontrará que las listas de dependencias para un archivo en particular que debe construirse se definen como listas vinculadas de punteros a otros archivos que también deben construirse y, a su vez, tienen dependencias en las listas vinculadas.
Ejemplo de la vida real para:
** 1) Lista enlazada individualmente **
- Cerebro humano de un niño (para recordar algo, por ejemplo, un poema tiene que vincularlo, si le preguntas la última línea, tendrá que leer la primera línea)
- entrega de mensajes en la red (el mensaje se divide en paquetes y cada paquete tiene una clave del siguiente para que al final del receptor, sea fácil agruparlos)
2) Lista doblemente vinculada
- Moléculas de ADN
- Caché del navegador que permite utilizar el botón ATRÁS.
- Los entrenadores de trenes están conectados con los siguientes y los anteriores.
- Cadena de rodillos de bicicleta (lista enlazada doblemente circular)
3) lista enlazada circular
- Escalera mecánica
- Problema de tiempo compartido utilizado por el programador durante la programación de los procesos en el sistema operativo.
- Juego de mesa multijugador
En .NET BCL, la clase System.Exception tiene una propiedad llamada InnerException , que apunta a otra excepción o bien es null . Esto forma una lista enlazada.
En System.Type , la propiedad BaseType apunta a otro tipo de la misma manera.
En el caso general, las listas enlazadas son una de las cosas más diabólicamente útiles que encontrará.
Ejemplos del mundo real:
Un grupo de personas que esperan en la cola algo u otro: un tipo especial de LL llamado "cola".
La pila de platos en su vitrina - un tipo especial de LL llamado "pila".
Las líneas de "tomar un número" (donde los números tienen que comenzar de nuevo en "1" en algún momento) - un tipo especial de LL llamado "cola circular".
En general, la metáfora que me gusta usar para casi todas las estructuras de datos vinculadas es una baraja de cartas . Casi cualquier cosa que pueda hacer con las listas vinculadas, puede usar una baraja de cartas para visualizar. Esto es particularmente útil para mostrar lo que está pasando en algunos de los algoritmos de clasificación más esotéricos.
Mi favorito personal: Bogosort = jugar 52 cartas recogidas hasta que tu mazo esté ordenado. :-)
En los sistemas operativos ... uno puede usar una lista enlazada para realizar un seguimiento de qué procesos se están ejecutando y qué procesos están inactivos ... un proceso que se está ejecutando y quiere dormir ... se elimina de la Lista vinculada que realiza un seguimiento de la ejecución procesos y una vez que el tiempo de suspensión ha terminado lo agrega de nuevo al proceso activo LinkedList
Tal vez el sistema operativo más nuevo está usando algunas estructuras de datos funky ... las listas enlazadas se pueden usar allí
Línea de espera en un cajero / cajero, etc ...
Una serie de órdenes que deben ejecutarse en orden.
Cualquier estructura FIFO se puede implementar como una lista enlazada.
La forma en que Blame se mueve alrededor de un grupo de ingenieros de software que trabajan en diferentes módulos en un proyecto.
Primero, culpan al tipo de GUI por el producto que no funciona. Comprueba su código y ve que no es su culpa: la API se está arruinando. El tipo de API comprueba su código: no es su culpa, es un problema con el módulo de registrador. El chico del módulo de logger ahora culpa al chico de la base de datos, quien culpa al chico del instalador, quien culpa ...
Lo primero que hay que entender es que una lista enlazada es conceptualmente lo mismo que una matriz.
La única diferencia está en la eficiencia de varias operaciones. Más importante:
- Inserción en el medio: O (1) para la lista, O (n) para la matriz.
- Acceso directo a un elemento en el medio: O (n) para la lista, O (1) para la matriz.
Por lo tanto, cualquier analogía que se pueda usar para una matriz (todos los motores de un avión, todos los artículos en una lista de compras ...) también se aplica a una lista vinculada, pero la consideración de eficiencia podría hacer que sea apropiado hacer otra analogía:
Una matriz sería cajas en una estantería . Cuando quita la caja de la fila n, todas las cajas desde n + 1 hacia arriba deben moverse un estante hacia abajo (para que no tenga un estante vacío problemático).
Una lista enlazada, por el contrario, sería un collar . Cuando descubras que ya no te gusta esa joya azul, sácala de la secuencia y une los dos extremos resultantes. No es necesario recorrer cada perla y desplazarla para que puedas arreglar tu collar.
Me gusta pensar en una lista enlazada circular como un collar de perlas, con cada perla que contiene un poco de información. Simplemente siga la cadena hasta la siguiente perla de datos y, finalmente, terminará nuevamente al principio.
Mi primera reacción a esta pregunta fue: "¡Mira a tu alrededor! ¡Esto está en todas partes!" Pero después de pensarlo un poco, no pude pensar en ningún ejemplo que no haya sido ideado.
El concepto de una lista enlazada es un concepto compuesto, una doble referencia. Tienes la noción de una lista, que no es un problema. Una lista de la compra, por ejemplo. Luego llegas a la parte de enlace. Un artículo de comestibles no conoce el siguiente artículo de comestibles, por lo que el modelo se descompone.
Creo que la razón por la que está teniendo problemas para encontrar un ejemplo del mundo real es que la parte de enlace es un artefacto de programación, un detalle de implementación. Hay muchas formas de implementar listas de manera programática y una buena manera es que cada elemento de la lista sepa acerca de sus vecinos. Otra forma es tener un objeto de lista que realiza un seguimiento de los artículos y su orden. Así es como funcionan la mayoría de las listas en la vida real. En el ejemplo anterior, el objeto Lista para la lista de la compra sería el papel (o lo que sea) en el que esté escrito.
Tal vez sea más útil pensar en las listas en general y ver las listas enlazadas como una implementación específica de una lista.
Mira la lista enlazada como una estructura de datos. Es un mecanismo para representar la autoagregación en OOD. Y puedes considerarlo como un objeto del mundo real (para algunas personas es la realidad)
Mira una lista enlazada:
[A] => [B] => [C] => [D] =>
Es un ... ¡tren! Cada vagón de ferrocarril contiene algo y está unido a otro vagón de ferrocarril (o nada para el último). Solo puede agregar un vagón de ferrocarril al final y, si desea deshacerse de uno, debe adjuntar el anterior con el siguiente.
No creo que haya una buena analogía que pueda resaltar las dos características importantes a diferencia de una matriz: 1. eficiente para insertar después del elemento actual y 2. ineficiente para encontrar un elemento específico por índice.
No hay nada de eso porque normalmente la gente no trata con una gran cantidad de elementos en los que necesita insertar o localizar elementos específicos. Por ejemplo, si tiene una bolsa de arena, eso sería cientos de millones de granos, pero no necesita localizar un grano específico, y el orden de los granos no es importante.
Cuando trabaje con colecciones más pequeñas, puede ubicar visualmente el artículo que necesita o, en el caso de libros en una biblioteca, tendrá una organización similar a la de un dictador.
La analogía más cercana es tener un ciego que atraviesa elementos vinculados, como eslabones de cadenas, cuentas en un collar, vagones de tren, etc. Puede que esté buscando un artículo específico o que necesite insertar un artículo después del actual. Podría ser bueno agregar que el ciego puede atravesarlos muy rápidamente, por ejemplo, un millón de cuentas por segundo, pero solo puede sentir un enlace a la vez y no puede ver toda la cadena o parte de ella.
Tenga en cuenta que esta analogía es similar a una lista de doble enlace, no puedo pensar en una analogía similar con una única enlace, porque tener una conexión física implica la capacidad de dar marcha atrás.
Pidió un ejemplo práctico; así que voy a darle una oportunidad:
Digamos que estás escribiendo un cortafuegos; en este servidor de seguridad tiene una lista blanca de IP y una lista negra de IP.
Usted sabe que su IP, la IP de su trabajo y algunas IP de prueba deben estar en la lista blanca. Por lo tanto, agrega todas las direcciones IP a la lista blanca.
Ahora, también tiene una lista de IP conocidas que deben ser bloqueadas. Entonces, agregas esos IPs a la lista negra.
¿Por qué podría usar LinkedList para esto?
- La operación es rápida para agregar / eliminar un elemento de la lista.
- Usted no sabe cuántas IPs se van a bloquear / poner en lista blanca. Por lo tanto, revelar una de las principales ventajas de una lista enlazada (es de tamaño variable).
Recuerdo, hace muchos años, en una de mis primeras clases universitarias, preguntándome dónde alguna vez usaría una lista vinculada. Hoy, no creo que haya un solo proyecto en el que trabaje donde no lo haya usado, y en muchos lugares. Es una estructura de datos increíblemente fundamental, y créanme, se usa mucho en el mundo real.
Por ejemplo:
- Una lista de imágenes que deben grabarse en un CD en una aplicación de imágenes médicas
- Una lista de usuarios de un sitio web que necesitan ser enviados por correo electrónico alguna notificación
- Una lista de objetos en un juego 3D que se deben representar en la pantalla
Puede que te parezca un poco inútil ahora, pero dentro de unos años, pregúntate lo mismo, te sorprenderás de que alguna vez te hayas preguntado dónde se usaría.
Edit: Noté que en uno de tus comentarios preguntaste por qué es importante el puntero. Alguien respondió correctamente que el puntero realmente no le importa a un usuario de una lista vinculada. Un usuario solo quiere una lista que contenga una lista de cosas. Cómo esa lista "contiene" esa lista de cosas realmente no le importa al usuario. El puntero es parte de ese "cómo". Imagina una línea, dibujada en el suelo, que lleva a un cajero. La gente necesita estar parada en esa línea para poder llegar al cajero. Esa línea es una analogía (y lo admito, esto es un poco exagerado) para el puntero que usa una lista enlazada. La primera persona, en el cajero, en la línea, es el jefe de la lista. La persona directamente detrás de ellos en la línea es la siguiente en la lista. Y, finalmente, la última persona en la línea, en la línea, es la cola de la lista.
Se puede utilizar una lista enlazada para implementar una queue . El ejemplo de la vida real canónica sería una línea para un cajero.
Una lista enlazada también se puede utilizar para implementar una stack . El ejemplo cónico real es uno de esos dispensadores de platos en un restaurante buffet donde se saca la placa superior de la parte superior de la pila.
Si lo piensa, un "Enlace" es simplemente una forma de identificar una relación "Siguiente", "Anterior", "Niño" o "Padre" entre las instancias de datos . Por lo tanto, entre las aplicaciones del mundo real encontrará una gran variedad de aplicaciones. Piense en una lista simple (por ejemplo, lista de compras) para listas básicas vinculadas. Pero considere también los usos a los que podemos colocar Gráficos (trazar distancias entre ciudades en un mapa, interacciones entre especies en biología) o Árboles (jerarquías en una organización o datos en un índice de una base de datos para dos ejemplos muy diversos).
Supongo que desea una explicación más metafórica que la definición del libro, en lugar de ejemplos de cómo podría usar una lista enlazada.
Una lista enlazada es algo así como una búsqueda del tesoro. Tienes una pista, y esa pista tiene un puntero para colocar la siguiente pista. Así que vas al siguiente lugar y obtienes otro dato, y otro puntero. Para obtener algo en el medio, o al final, la única forma de llegar a él es seguir esta lista desde el principio (o hacer trampa;))
Sus moléculas de ADN son listas de doble enlace.
Un buen ejemplo de una lista enlazada es su mensaje de texto, en el que un paquete determinado de un mensaje puede dividirse en varios paquetes. Cada paquete contiene una clave que se conecta con la siguiente clave y con la n-ésima clave para que todo el mensaje de texto contenga la clave y los datos.
Una cadena telefónica se implementa directamente como una lista enlazada. Así es como funciona:
Un organizador de grupo recopila los números de teléfono de todos los miembros.
El organizador asigna a cada miembro el número de otro miembro para llamar. (A veces, asignan su propio número para que sepan que el mensaje llegó, pero esto es opcional).
Cuando es necesario enviar un mensaje, el organizador llama al jefe de la lista y entrega el mensaje.
El jefe llama al número que se les asignó y entrega el mensaje.
El paso 4 se repite hasta que todos hayan escuchado el mensaje.
Obviamente, se debe tener cuidado de configurar la lista en el paso 2 para que todos estén vinculados. Además, la lista suele ser pública, de modo que si alguien recibe un contestador automático o un tono de ocupado, puede llamar al siguiente número y mantener la cadena en movimiento.
Una lista enlazada es como una línea de conga . Todos sostienen las caderas de la persona frente a ellos y sus caderas son sostenidas por la persona que está en su parte posterior, excepto los que están adelante y atrás. La única forma de agregar personas a la línea es encontrar el lugar correcto y desacoplar esa conexión, luego insertar la nueva persona o personas.
Una lista enlazada es muy similar a una pila de papeles, cada uno con un elemento. (A diferencia de las matrices, que son como tableros de anuncios). Generalmente se usa para resolver un problema con estas características:
- Hay un número desconocido o cambiable de artículos
- Los artículos están en un orden, como una lista
- Los artículos pueden ser reorganizados, agregados en la mitad de la lista, eliminados en la mitad de la lista, etc.
Reorganizar una matriz simple es un dolor, agregar un elemento en algún lugar del medio mientras se asegura de que la matriz tenga suficiente memoria, etc. es una molestia. Con lista enlazada estas operaciones son simples. Digamos que desea mover el elemento # 10 para que esté entre el elemento # 2 y el elemento # 3. Con los papeles, puedes levantarlo y moverlo. Con una matriz, tendría que mover los elementos del 3 al 9 a través de una ranura, luego colocarlos. Con una lista enlazada, haga esto: le dice a 9 que el uno después de que es 11, que le dice a 2 el que está después de que es 10, diga 10 el uno después de que sea 3.
Estoy usando varios de ellos en este momento, debido a lo fácil que es agregar elementos y decir "hacer esta acción a cada elemento en la lista" mediante programación. Una de ellas es una lista de entradas, como en una hoja de cálculo. El otro, lo hago repasando esa primera lista y agregando una referencia a cada elemento que tenga un valor particular, para poder realizar operaciones por lotes en ellos. Ser capaz de arrancar elementos del medio, o agregarlos al medio, y no tener que preocuparse por la longitud de la matriz. Esas son las principales ventajas en mi experiencia.
bueno, si un maestro llevó a sus alumnos a una película de dibujos animados, pero ella no pudo conseguir los asientos juntos, les pedirá que recuerden la dirección (número de asiento) del próximo alumno y así sucesivamente ... para que no tuviera para hacer frente a los problemas al volver !!!
¿Qué es un ejemplo práctico y real de la Lista Vinculada?
El más simple y sencillo es un tren.
Los vagones de tren se enlazan en un orden específico para que puedan cargarse, descargarse, transferirse, dejarse y recogerse de la manera más eficiente posible.
Por ejemplo, la planta Jiffy Mix necesita azúcar, harina, harina de maíz, etc. A la vuelta de la curva podría haber una planta procesadora de papel que necesite cloro, ácido sulfúrico e hidrógeno.
Ahora, podemos detener el tren, descargar cada vagón de su contenido, luego dejar que el tren continúe, pero luego todo lo demás en el tren tiene que sentarse mientras se extrae la harina del cajón, luego el azúcar, etc.
En su lugar, los vagones se cargan en el tren para que se pueda desmontar una parte del mismo, y el resto del tren se mueva.
El final del tren es más fácil de desmontar que una parte en el medio, y mucho más fácil que desmontar unos pocos coches en un lugar, y unos pocos coches en otro lugar.
Sin embargo, si es necesario, puede insertar y eliminar elementos en cualquier punto del tren.
Al igual que una lista enlazada.
-Adán
El cerebro humano puede ser un buen ejemplo de lista enlazada individualmente . En las etapas iniciales de aprender algo de memoria , el proceso natural es vincular un elemento con el siguiente. Es un acto subconsciente. Tomemos un ejemplo de atracar 8 líneas de Solitario Segadora de Wordsworth:
Behold her, single in the field,
Yon solitary Highland Lass!
Reaping and singing by herself;
Stop here, or gently pass!
Alone she cuts and binds the grain,
And sings a melancholy strain;
O listen! for the Vale profound
Is overflowing with the sound.
Nuestra mente no funciona bien como una matriz que facilita el acceso aleatorio. Si le preguntas al chico cuál es la última línea , será más difícil para él decirlo. Tendrá que ir desde la línea uno para llegar allí. Es aún más difícil si le preguntas cuál es la quinta línea .
Al mismo tiempo, si le das un indicador, él seguirá adelante. Ok empezar de Reaping and singing by herself; ?. Se vuelve más fácil ahora. Es incluso más fácil si pudieras darle dos líneas, Alone she cuts and binds the grain, And sings a melancholy strain; porque él consigue el flujo mejor. De manera similar, si no le das nada en absoluto, tendrá que comenzar desde el principio para obtener las líneas . Esta es la lista clásica vinculada.
Debería haber pocas anomalías en la analogía que podrían no encajar bien, pero esto explica de alguna manera cómo funciona la lista enlazada. Una vez que adquiera cierta habilidad o conozca el poema de adentro hacia afuera, la lista enlazada se enrolla (cerebro) en una tabla o matriz hash que facilita la búsqueda de O (1) donde podrá seleccionar las líneas desde cualquier lugar.
