¿Por qué necesito una lista vinculada y por qué es importante?

Answer 1

La utilidad de una lista vinculada es su inserción y eliminación en tiempo constante para cualquier nodo arbitrario.

Fuera de mi cabeza, las colas se benefician enormemente de esta función, ya que no están buscando un elemento, y solo insertan / eliminan al final de la lista.

Puede salirse con la suya, pero las matrices solo tienen tiempo constante para agregar y eliminar el último objeto. Comprenda que con la memoria y la sobrecarga de operación al eliminar el primer elemento y las matrices comienzan a verse bastante agrias. Las matrices pueden imponer un costo adicional al agregar un artículo si la matriz necesita ser redimensionada. La eliminación del último elemento es la única operación de tiempo constante garantizada †.

Además, las listas vinculadas hacen algunas compensaciones favorables en la memoria. Para el costo de memoria adicional del puntero por nodo, agregar y eliminar elementos no necesita memoria adicional que requeriría el cambio de tamaño de la matriz, lo que hace que la asignación de memoria sea más predecible para una entrada determinada.

† Es decir, a menos que la biblioteca que maneja su memoria de matriz dinámica no cambie de tamaño a una matriz más pequeña para minimizar el espacio.

Answer 2

El mejor uso que he encontrado para las listas vinculadas: suponga que desea leer en una lista de elementos (cadenas, números, etc.) de un archivo u otra fuente, pero no sabe de antemano cuántos elementos hay ser – estar. Con una lista vinculada, puede agregar o eliminar elementos según sea necesario.

Los vectores son de acceso aleatorio ya que cada uno de los elementos se almacena de forma contigua: es muy rápido calcular la dirección de cualquier elemento dado. Debido a esto, el espacio debe asignarse por adelantado. Los tipos de vectores abstractos (como los de la biblioteca STL) que encapsulan una matriz normal usan un simple truco para expandirse al tamaño deseado cada vez que intentas usar un subíndice mayor que el tamaño nominal de la matriz. Primero, la matriz real utilizada para almacenar los datos suele ser mayor que el tamaño del vector visto desde fuera de la abstracción. Entonces, si el subíndice no queda fuera de esta área de almacenamiento, simplemente se agrega y se actualiza el tamaño del vector. Por otro lado, si el subíndice queda fuera del área de almacenamiento interno, se asigna una nueva matriz que es dos veces el tamaño del antiguo y todos los elementos copiados.

Esquema de un vector estilo STL de tamaño 5:
————————————————
El | v_1 | v_2 | v_3 | v_4 | v_5 | xxx | xxx | xxx |
————————————————

Esto significa que agregar nuevos elementos normalmente es tan rápido como cambiar un elemento en una matriz regular, pero ocasionalmente toda la matriz debe copiarse en una nueva ubicación. Creo que la velocidad para agregar nuevos elementos se amortiza a O (1) (velocidad constante), que es lo mismo que para una lista vinculada pero con la ventaja de que es un acceso aleatorio, por lo que O (1) también es un tiempo de acceso mientras que un La lista vinculada es O (n) para el acceso. Mientras tanto, los requisitos de almacenamiento serán aproximadamente los mismos (aproximadamente el doble de lo que ocupan los datos), por lo que en cierto sentido tiene razón: ¿por qué querría usar una lista vinculada cuando no parece tener ninguna ventaja sobre el STL? clase de vector (o un tipo de vector abstracto similar)?

Esquema de una lista vinculada que contiene 5 elementos:

v_5 -> v_4 -> v_3 -> v_2 -> v_1

Pero para completar la pregunta: cada elemento en una lista vinculada tiene dos componentes: el valor y un puntero al siguiente elemento. Cada vez que agrega un nuevo elemento a la lista vinculada, se debe reservar una nueva memoria y configurar el puntero para que apunte al elemento anterior. Mientras tanto, para encontrar un elemento, debe comenzar en el último elemento agregado y luego atravesarlo hasta llegar a la ubicación deseada. Esto tomará n / 2 pasos en promedio. (Alternativamente, los elementos se pueden encadenar en la dirección opuesta, lo que significa que debe realizar un seguimiento de dos elementos en todo momento. La primera versión se comporta como una pila, primero en entrar, último en salir, mientras que el segundo es más como una cola, primero en entrar primero en salir.)

Finalmente, para responder la pregunta que hice anteriormente: una ventaja de una lista vinculada sobre una clase de vector extensible es que puede insertar (o eliminar) elementos sin ninguna copia, aunque todavía tiene que recorrer la lista para llegar allí en primer lugar . Además, concatinar dos listas vinculadas es mucho más rápido.

Answer 3

Desde el desbordamiento de la pila (LInked List vs Vector):

Vector es otro nombre para matrices dinámicas. Es el nombre utilizado para la estructura de datos de matriz dinámica en C ++. Si tiene experiencia en Java, puede conocerlos con el nombre ArrayList. (Java también tiene una antigua clase de colección llamada Vector que no se usa hoy en día debido a problemas en su diseño).
Los vectores son buenos para el acceso de lectura aleatorio y la inserción y eliminación en la parte posterior (toma tiempo constante amortizado), pero son malos para las inserciones y eliminaciones en el frente o en cualquier otra posición (tiempo lineal, ya que los elementos deben moverse). Los vectores generalmente se presentan de forma contigua en la memoria, por lo que atravesar uno es eficiente porque la memoria caché de la CPU se usa de manera efectiva.
Las listas vinculadas, por otro lado, son buenas para insertar y eliminar elementos en el frente o en la parte posterior (tiempo constante), pero no son particularmente buenos para mucho más: por ejemplo, eliminar un elemento en un índice arbitrario en el medio de la lista toma tiempo lineal porque primero debes encontrar el nodo. Por otro lado, una vez que haya encontrado un nodo en particular, puede eliminarlo o insertar un nuevo elemento después de él en tiempo constante, algo que no puede hacer con un vector. Las listas enlazadas también son muy simples de implementar, lo que las convierte en una estructura de datos popular.

Answer 4

Las listas vinculadas son útiles para lecturas, inserciones y eliminaciones concurrentes.

Los vectores en C ++ y Java son matrices realmente redimensionables.

Las listas enlazadas son más naturales en lenguajes funcionales como LISP y F #.

Answer 5

C ++ contiene un contenedor que no significa que el concepto de lista vinculada no sea importante. El vector C ++ funciona como matrices dinámicas y no como una lista vinculada (que yo sepa).

Es tan simple como eso…. tenemos la función sort () incluida en el algoritmo para ordenar en el tiempo O (n log n), entonces, ¿por qué seguimos estudiando el algoritmo de clasificación? Si puede responder “por qué” a esta pregunta, preguntas como esta nunca quedarían sin respuesta.

¡Hazme saber en los comentarios si aún no tiene respuesta …!

Answer 6

Lista enlazada es un concepto de estructuras de datos.
La Lista vinculada funciona como un puntero y también como una variable.
Puede almacenar los datos y almacenar la dirección de otro elemento de datos.
Es como una lista en la que puedes almacenar cadenas, números, etc.
Es fácil de usar y con los métodos proporcionados fáciles de manejar y acceder a los datos.
Por lo tanto, se usa ampliamente y se considera importante.

Answer 7

Ignorando los problemas de “¿dónde las personas realmente usan esto” y dado que otras personas han manejado el vector C ++, una lista vinculada es la estructura de datos dinámicos más fácil disponible. Si no puede hacer que uno funcione, las probabilidades de que se pueda confiar en usted para hacer cualquier otra cosa con datos estructurados son bastante bajas, y no tomará casi tanto tiempo descubrir si conoce sus cosas que un problema del mundo real. .

Answer 8

La lista vinculada es una estructura de datos lineal que es fácil de aprender y puede ayudar mucho a comprender las estructuras de datos no lineales como los árboles, también ayuda a identificar las complejidades. La mayoría de los lenguajes de programación de alto nivel ocultan muchos detalles, como cómo se implementó internamente, pero tener una comprensión clara de las listas vinculadas es esencial para diseñar nuevas estructuras de datos de manera eficiente por nuestra cuenta.

Answer 9

Suponga que su programa espera alguna entrada del usuario. Ahora hay 3 escenarios posibles: 1. Tanto usted como su usuario conocen el tamaño de la entrada, en este caso, opte por la matriz, ya que tiene los tiempos de búsqueda e inserción más rápidos. En segundo lugar, puede que no, pero el usuario puede saber el tamaño de la entrada. Luego puede solicitar el tamaño y luego declarar la matriz de ese tamaño dinámicamente.
¿Pero si su usuario tampoco conoce el tamaño de entrada (puede suceder, cree que está escribiendo un editor de texto)?
Puede declarar una gran variedad, pero aún existe la posibilidad de desbordamiento o gran desperdicio de espacio.
Linkedlist aquí entra en juego, asigna una unidad de espacio a la vez y la vincula con una nueva cuando sea necesario. Esto te ayuda a optimizar el espacio.
Linkedlist tiene otra ventaja, ya que el espacio no necesita ser contiguo, las posibilidades de falta de disponibilidad de espacio son bastante menores, lo que sucede en caso de una gran asignación de matriz dinámica.
el tiempo y las ventajas algorítmicas también están ahí, como se menciona brillantemente en las otras respuestas.

Answer 10

Hay cierta cantidad de vocabulario en las entrevistas. Probablemente debería saber qué es una lista vinculada y cómo funciona. Debería poder codificar lo suficientemente bien como para poder escribir una función Insertar para una lista vinculada.

Del mismo modo para otras cosas. No es importante que sepa cómo escribir su propio tipo para el uso diario, pero debería poder escribir un tipo que funcione. Debe saber qué son las matrices y poder comparar cómo agregar un elemento a algo almacenado con un respaldo de matriz para agregar un elemento a una lista vinculada.

Hay una serie de herramientas en la caja de herramientas de codificación que son importantes, pero ninguna es más importante que ser capaz de tomar sus pensamientos y expresarlos como código.