¿Cuáles son las reglas concretas para usar una lista vinculada en lugar de una matriz?

18

Se puede usar una lista vinculada cuando desee insertar y eliminar elementos de forma económica y cuando no importa que los elementos no estén uno al lado del otro en la memoria.

Esto es muy abstracto y me gustaría una explicación concreta de por qué debería usarse una lista vinculada en lugar de una matriz. No tengo mucha experiencia en programación, por lo que no tengo mucha (si alguna) experiencia en el mundo real.

data-structures linked-list pliegue derecho
fuente
3
Honestamente, no creo que los ejemplos signifiquen mucho para usted hasta que tenga alguna experiencia de escribir algo y luego ver el efecto que tienen las estructuras de datos cambiantes en su código. Intente escribir algo que le interese y descubra qué estructuras de datos y contenedores son los más adecuados, o mire algún código existente y piense por qué se seleccionó cada contenedor y qué efecto tendría cambiarlo.
Inútil
Simplemente no creo que sea posible comunicar de manera útil las compensaciones y los efectos secundarios de la selección de la estructura de datos al OP (sin experiencia) sin un ejemplo trabajado de forma mucho más larga de lo que es razonable aquí. Los ejemplos dados como respuestas están bien, y responden la pregunta como se le preguntó, pero no (lo que leí como) una solicitud implícita de comprensión real.
Inútil

Respuestas:

37

Aquí hay algo a medio camino entre un ejemplo y una analogía. Tienes que hacer algunos recados, así que agarras un pedazo de papel y escribes:

  • banco
  • comestibles
  • dejar la limpieza en seco

Entonces recuerdas que también necesitas comprar sellos. Debido a la geografía de tu ciudad, debes hacerlo después del banco. Puede copiar su lista completa en una nueva hoja de papel:

  • banco
  • sellos
  • comestibles
  • dejar la limpieza en seco

o podrías garabatear en el que tenías:

  • banco ....... SELLOS
  • comestibles
  • dejar la limpieza en seco

Al pensar en otros recados, puede escribirlos al final de la lista, pero con flechas que le recuerdan en qué orden hacerlos. Esta es una lista vinculada. Es más rápido y fácil que copiar toda la lista cada vez que agrega algo.

Entonces su teléfono celular suena mientras está en el banco "oye, tengo las estampillas, no recojas más". Simplemente eliminas los SELLOS de la lista, no reescribes uno nuevo sin SELLOS.

Ahora podría implementar una lista de recados en el código (tal vez una aplicación que ordene sus recados en función de su geografía) y existe una posibilidad razonable de que realmente use una lista vinculada para eso en el código. Desea agregar y eliminar muchos elementos, el orden importa, pero no desea volver a copiar toda la lista después de cada inserción o eliminación.

Kate Gregory
fuente
3
Según Bjarne Stroustrup, los LL pueden no ser tan rápidos y fáciles para copiar la lista completa como cree .
Dennis
@ Dennis sí, lo sé, gracias a mover semántica. Sin embargo, esto no es cierto para todos los idiomas, por lo que el ejemplo se mantiene.
Kate Gregory
1
@KateGregory es bastante justo, pero aún así es bueno señalar que las estructuras de datos "básicos" a menudo son mejores que las estructuras de datos interesantes que aprendemos en la escuela (o en otros lugares). No quiero que los nuevos graduados usen LLs en todas partes porque es teóricamente apropiado y posiblemente sea una mala elección de manera realista. Usar la estructura de datos correcta es importante, y a veces las personas lo complican demasiado. Ligeramente relacionado está esta charla de Jonathan Blow (creador de "Braid") sobre estructuras de datos .
Dennis
1
@Ray: una lista vinculada puede superar la estructura de un árbol si espera que haya 4 elementos y las comparaciones son relativamente baratas. No sé exactamente dónde está el límite donde este no es el caso. Además, una estructura de árbol requiere que sus datos se puedan ordenar, mientras que una estructura de lista le permite mantener el orden de inserción (o cualquier orden arbitrario).
David Stone
2
No creo que esta analogía sea muy precisa. Como humanos, podemos (al menos para una lista tan corta) encontrar un elemento en O (1). Pero si desea hacer una inserción aleatoria en una lista vinculada, tendrá que recorrer la mitad de los elementos en promedio, lo que le cuesta O (n) solo para encontrar la posición donde desea insertar. La inserción real solo cuesta O (1) pero con una matriz, su costo también es "solo" O (n). Entonces, la razón no solo se debe a la semántica del movimiento, sino también a la algorítmica. Sin embargo, el factor constante oculto por el big-O es mucho mayor para la lista de Me gusta, debido al acceso no contiguo a la memoria.
5gon12eder
18
  • Las tablas de hash que utilizan el encadenamiento para resolver las colisiones de hash suelen tener una lista vinculada por depósito para los elementos en ese depósito.
  • Los asignadores de memoria simples usan una lista libre de regiones de memoria no utilizadas, básicamente una lista vinculada con el puntero de la lista dentro de la memoria libre
  • En un sistema de archivos FAT , los metadatos de un archivo grande se organizan como una lista vinculada de entradas FAT.
Michael Borgwardt
fuente
12

La "pila de llamadas" en lenguaje C se implementa como una lista vinculada en las API binarias x86 (y la mayoría de las otras).

Es decir, la llamada al procedimiento en lenguaje C sigue una disciplina de primero en entrar, último en salir. El resultado de ejecutar llamadas de función (posiblemente recursivas) se denomina "pila de llamadas" o, a veces, incluso "la pila".

La CALLinstrucción x86 termina implicando una lista vinculada usando la "pila de llamadas". Una CALLinstrucción empuja el contenido del registro% EIP, la dirección de la instrucción después de la CALLmemoria de la pila. El prólogo de función llamada empuja los contenidos del registro% EBP, la dirección más baja de las variables locales en la función de llamada, a la memoria de la pila. Luego, el prólogo de la función llamada establece% EBP en la base de la pila de la función actual.

Eso significa que% EBP es un puntero a una ubicación de memoria que contiene la dirección del valor% EBP de la función que realiza la llamada. Eso no es más que una lista vinculada, implementada parcialmente en hardware a través de CALL.

En cuanto a lo que es bueno para esto, es cómo las CPU x86 implementan llamadas a funciones, particularmente llamadas a funciones donde la función tiene su propia copia de argumentos y variables locales a la función. Cada llamada a la función introduce cierta información en la "pila de llamadas" que permite que la CPU retome donde se quedó en la función de llamada, sin interferencia de la función llamada o la función de llamada.

Bruce Ediger
fuente
3

Se puede usar una lista vinculada para implementar una cola de mensajes.

Una cola de mensajes es una estructura en la que almacenamos información sobre eventos para su posterior procesamiento. Por ejemplo, cuando el usuario presiona una tecla o mueve el mouse, este es un evento. Una aplicación puede estar ocupada en el momento en que ocurre el evento, por lo que no se puede esperar que procese el evento en el momento preciso en que ocurre. Entonces, el evento se coloca en una cola de mensajes (información sobre qué tecla se presionó o dónde se movió el mouse), y cuando la aplicación tiene tiempo de sobra, verifica su cola de mensajes, recupera eventos de ella y procesa ellos. (Esto sucede dentro de un marco de tiempo de milisegundos, por lo que no se nota).

Del escenario de uso que acabo de describir, debería ser obvio que nunca nos importa tener acceso aleatorio a los eventos almacenados en la cola de mensajes; solo nos importa poder almacenar mensajes en él y recuperarlos. Por lo tanto, tiene sentido utilizar una lista vinculada, que proporciona un tiempo óptimo de inserción / eliminación.

(No ingrese para señalar que una cola de mensajes es probable, o más probable, o casi tan probable, que se implementará utilizando una lista de matriz circular; eso es un detalle técnico y tiene una limitación: solo puede almacenar un número limitado de mensajes en él)

Mike Nakis
fuente