¿Qué es una lista vinculada en las estructuras de datos de programación?

Echemos algunas ilustraciones aquí para aquellos que no están bien versados ​​en informática.

Cuando necesita almacenar cosas en la memoria de una computadora, debe usar algo llamado matrices, que son cubos de almacenamiento preasignados, como pequeños contenedores físicos.

Piense en esto como una matriz de 2 por 6 para almacenar datos del tipo “huevo”, si lo desea. ¿Pero qué pasa si tienes 13 huevos? o 759? o tu aplicación se volvió viral y tienes huevos de todos en Internet?

Claramente, en algunos casos, no puede depender de saber cuántos artículos necesitará almacenar, por lo que necesita otra forma de hacerlo.

Ingrese la lista vinculada.

Ahora, imaginemos que creamos un elemento de almacenamiento que tiene dos componentes: un cubo para almacenar su “huevo” y una cadena que se une al siguiente cubo.

Entonces, cuando desea almacenar un nuevo “huevo”, asigna una nueva unidad de almacenamiento, coloca su “huevo” en él y luego lo conecta a la cadena de cubos que ya tiene.

En términos de computadora, lo hace más típicamente usando la dirección de la porción de memoria que asignó, y recuerda la dirección del primer depósito de la cadena, o el último, y pega su nuevo depósito como el nuevo primero, señalando el primero anterior, o pegándolo al final como el último último cubo, y recuerde dónde está para poder repetirlo cuando asigne un nuevo cubo.

Tenga en cuenta que encontrar un huevo en particular puede ser un desafío; potencialmente tienes que caminar por toda la cadena de cubos buscando el huevo en cuestión.

Tenga en cuenta también que eliminar un depósito también tiene su propio conjunto de problemas: debe encontrar el que desea eliminar y luego señalar el que está delante de él al que está detrás de él antes de eliminarlo.

Dependiendo de su caso de uso, puede optar por usar otras estructuras de datos, como una lista doblemente vinculada (cada segmento apunta al que está delante y detrás de él) o una estructura de árbol donde hay una jerarquía que sube -down versus linealmente.

Una lista vinculada es cómo se implementa una Lista en muchos lenguajes de programación. Una lista es lógicamente un conjunto de elementos con un orden específico.

Los “enlaces” en la lista describen cómo las entradas en la lista se conectan entre sí.

En C, puede crear una lista usando algo como esto:

typedef struct MyList {
int elem_value;
struct MyList * next;
} Mi lista;

Esta estructura de datos le permitiría crear una lista simple de enteros. Tenga en cuenta que puede tener elementos con el mismo elem_value, pero en realidad son elementos diferentes en la lista.

En lo anterior, el puntero “siguiente” es necesario para describir el “vínculo” entre los elementos de la lista. Una lista generalmente tendrá un elemento “head”, y la terminación se indicará al establecer el puntero “next” en NULL, “nil” o algún otro valor similar.

Recorrerías la lista haciendo algo como esto:

vacío
print_list (lista MyList *)
{
MyList * caminar;
int i;

for (i = 0, walk = list; walk! = NULL; walk = walk-> next, i ++) {
printf (“elemento de lista% d es% d \ n”, i, walk-> elem_value);
}
}

Las listas son útiles porque son estructuras fundamentalmente dinámicas que pueden crecer “sin límite” (dentro de los límites de la RAM disponible). En este sentido, son más útiles que las matrices en muchos idiomas, ya que generalmente debe saber qué tan grande será una matriz antes de completarla, mientras que las listas pueden ser dinámicas “verdaderamente”.

Como puede ver con print_list arriba, recorrer una lista es una operación O (), y encontrar el i-ésimo elemento en la lista requiere caminar elementos “i”.

Las listas se pueden usar para crear fácilmente muchas estructuras de datos derivadas, como Colas, Pilas y FIFO. Una lista es el tipo más simple de estructura de datos de árbol.

Al revés de las listas:

• Son dinámicos.
• Son más fáciles de “editar” que las matrices, ya que puede agregar y eliminar elementos al principio de una lista, al medio de una lista o al final de una lista fácilmente sin molestar mucho a los otros elementos de la lista. Agregar a una lista y eliminar de una lista (una vez que sepa dónde está colocando el elemento) es una operación O (1), frente a O (N) como lo es con las matrices.
• Las listas se pueden “dividir” y manipular de otra manera fácilmente, sin necesidad de hacer copias completas de ellas.

Desventajas de las listas:

• Acceder al i-ésimo elemento de una lista es la operación O (N), no una operación O (1) como lo es con las matrices.
• Como estructuras de datos dinámicas, las listas deben asignarse y liberarse cuidadosamente.

Linked List es una estructura de datos lineal y es una estructura de datos muy común que consiste en un grupo de nodos en una secuencia que se divide en dos partes. Cada nodo consta de sus propios datos y la dirección del siguiente nodo y forma una cadena. Las listas enlazadas se utilizan para crear árboles y gráficos.

Ventajas:

• Son de naturaleza dinámica que asigna la memoria cuando es necesario.
• Las operaciones de inserción y eliminación se pueden implementar fácilmente.
• Las pilas y las colas se pueden ejecutar fácilmente.
• Lista enlazada reduce el tiempo de acceso.

Desventajas

• La memoria se desperdicia ya que los punteros requieren memoria adicional para el almacenamiento.
• No se puede acceder a ningún elemento al azar; Tiene que acceder a cada nodo secuencialmente.
• El recorrido inverso es difícil en la lista vinculada.

Tipos:

Lista enlazada individual: las listas enlazadas individualmente contienen nodos que tienen una parte de datos y una parte de dirección, es decir, la siguiente, que apunta al siguiente nodo en secuencia de nodos. Las operaciones que podemos realizar en listas enlazadas individualmente son inserción, eliminación y recorrido.

Lista doblemente vinculada : una lista doblemente vinculada es una lista que tiene dos referencias, una al siguiente nodo y otra al nodo anterior.

Lista enlazada circular: en la lista enlazada circular, el último nodo de la lista contiene la dirección del primer nodo y forma una cadena circular.

Aplicaciones de listas enlazadas

• Las listas vinculadas se utilizan para implementar pilas, colas, gráficos, etc.
• Las listas vinculadas le permiten insertar elementos al principio y al final de la lista.
• En las listas enlazadas no necesitamos saber el tamaño de antemano.

Del mismo modo que una matriz es la colección de ubicaciones de memoria continua de cualquier tipo determinado, como int, float, char o incluso un puntero.

Por ej. En lenguaje C ++, declaramos una matriz como la siguiente

sintaxis: identificador de tipo [tamaño];

int arr [5];

Aquí, arr es la matriz de tipo entero y tamaño 5. Se almacenará en las ubicaciones de memoria continua. Se utiliza principalmente cuando conocemos el tamaño de antemano. Podemos recuperar un elemento de la matriz con solo mencionar la posición del elemento entre corchetes, es decir, el subíndice.

Del mismo modo, la lista vinculada es la colección de nodos. El nodo tiene 2 partes:

1. Elemento que debe ser almacenado
2. Puntero al siguiente nodo (dirección del siguiente nodo)

Los nodos no se almacenan en ubicaciones de memoria continua a diferencia de la matriz, pero se almacenan en cualquier lugar de la memoria donde esté disponible el espacio. Entonces, para vincular un nodo al otro, tenemos la parte del puntero del nodo que apunta o contiene la dirección del siguiente nodo. De esta manera podemos recuperar los elementos de la lista vinculada secuencialmente. La parte del puntero del nodo generalmente se denota como la siguiente como se muestra en el diagrama, ya que apunta al siguiente nodo. El último nodo de la lista vinculada siempre tiene NULL en su parte de puntero, ya que apunta a nada y es el final de la lista vinculada. También podemos agregar o eliminar enlaces a / de la lista de enlaces y también hacer que un nodo apunte a otro nodo.

Podemos tener múltiples operaciones en la matriz, así como en una lista vinculada, como la recuperación de elementos, inserción, eliminación, etc.

La lista enlazada tiene múltiples ventajas, como el desperdicio de memoria, pero en el mismo lado, también tiene desventajas como colgar referencias y basura.

Buena suerte ! 🙂

Consulte los enlaces a continuación para obtener detalles completos sobre las listas vinculadas,

Lista vinculada en C

https://www.log2base2.com/data-s …

insertar un nodo al final de una lista vinculada

buscando un nodo en una lista individualmente vinculada

https://www.log2base2.com/data-s …

¡Gracias!

Voy a dar una respuesta completamente no técnica, con el objetivo de contribuir a la “programación para tontos”. Yo también soy un tonto y tengo programación autodidacta y autodidacta. ¡Espero poder entenderlo!

¿Alguna vez has jugado Treasure Hunt (juego) – Wikipedia? Digamos que le pido que construya una oración, y cada palabra en la oración se almacena en una ubicación diferente. Cuando encuentre una palabra en particular, también encontrará una pista sobre dónde encontrar la siguiente palabra. El juego comienza cuando te entrego la primera pista (o la pista principal).

1. Primera pista: ve, busca en tu habitación, debajo de la cama.
2. Vas al dormitorio, miras debajo de la cama y descubres la primera palabra escrita en un papel. Esta palabra es “tesoro”. Detrás del papel, en letra minúscula, se encuentra la siguiente pista: ve y mira debajo del sofá de tu sala de estar.
3. Ve, mira debajo del sofá de tu sala de estar y encuentra la siguiente palabra en otro papel. Esta palabra es “caza”. Detrás del papel, en letra minúscula, se encuentra la siguiente pista: ve y mira debajo de tu tocador.
4. Ve y mira debajo del tocador, y encuentra la siguiente palabra en otro papel. Esta palabra es “es”. Detrás del papel, en letra minúscula, se encuentra la siguiente pista: ve y mira el asiento de tu auto.
5. Vas al auto y miras en el asiento de tu auto, encuentras otra palabra en otro papel. Esta palabra es “diversión”. Miras detrás del periódico y no hay una pista más. Esto implica que ya terminaste, y tu oración es “La búsqueda del tesoro es divertida”.

Esto es esencialmente lo que es una lista vinculada. Almacena una pieza de información (una palabra en el ejemplo anterior) y junto con ella, también almacena la dirección de la siguiente información. La última información no tendrá una dirección asociada. La dirección de la primera información es suficiente para ir y recolectar toda la información y, por lo tanto, la dirección de la primera información se conoce como “cabeza” (debajo de la cama, en el ejemplo anterior).

En una matriz típica, es fácil agregar una información al final de la matriz. En una lista vinculada, para agregar información al final, debe revisar todas las pistas. Llegas al último trozo de papel (que originalmente no tenía la siguiente pista) y agregas una nueva dirección para el siguiente trozo de información. Este recorrido a través de todas las piezas hace que agregar información al final sea muy ineficiente para las listas vinculadas.

Por otro lado, es muy fácil agregar algo al principio. Digamos que creo una nueva palabra “Jugar” y coloco esta palabra detrás de mi televisor. Mi pista principal ahora se modificará a: “Mira detrás del televisor”. Allí, colocaré un papel con la palabra “Jugar”, y detrás de esa palabra, escribiré la dirección de la siguiente pista que era la pista original, es decir, “Ve, busca en tu habitación, debajo de la cama . ”

(Otra diferencia importante entre una matriz y una lista vinculada está relacionada con el almacenamiento de memoria contigua. Una matriz es una pieza contigua de memoria dentro del almacenamiento de la computadora. Sin embargo, una lista vinculada no lo es; cada pieza de información puede almacenarse en múltiples ubicaciones disjuntas )

Ahora, con la nueva pista de “Mira detrás del televisor”, puedo revisar todos los elementos y construir una nueva oración “¡Jugar a Treasure Hunt is Fun!”

Una “lista vinculada” es una estructura de datos capaz de almacenar una colección ordenada arbitrariamente grande de artículos con un mínimo de sobrecarga. Cada elemento de datos está representado por una tupla que consiste en el elemento mismo y un puntero (un valor almacenado que se puede usar para encontrar la próxima tupla) a la siguiente tupla de la colección. Un puntero vacío indica que el elemento actual es el último elemento de la colección. La colección en sí suele estar representada por un puntero a la primera tupla; hecho de esta manera, un puntero vacío representa una colección vacía.

Las listas enlazadas son muy simples: solo requieren agregar un campo a una estructura de datos (el siguiente puntero). Debido a esto, las listas vinculadas suelen ser la segunda estructura de datos para almacenar colecciones que encontrará un programador principiante, siendo la primera una “matriz” de longitud fija. La mayoría de las operaciones en las listas vinculadas son lentas: mientras que agregar un elemento al encabezado de la lista y eliminar un elemento de la lista es rápido, cuenta el número de elementos en la lista, encuentra un elemento específico en la lista y agrega o elimina elementos. desde el final de la lista son todos lentos, en relación con otras estructuras de datos para almacenar colecciones y, por lo tanto, las listas vinculadas a menudo no son una buena opción, en términos de rendimiento, como una estructura de datos de “propósito general”.

Muchos idiomas tienen listas vinculadas, o al menos listas que se comportan como listas vinculadas, como un tipo de datos intrínsecos. Por ejemplo, en LISP y en prácticamente todos los idiomas derivados de LISP (de los cuales hay cientos, si no miles), las listas vinculadas son uno de los tipos de datos fundamentales en el lenguaje.

Hola,

Una lista vinculada es una estructura de datos lineal dinámica, donde cada elemento de datos es un objeto separado con su propia asignación de memoria conectada a los otros objetos mediante punteros.
Estos elementos (llamados nodos) forman parte de los datos y la referencia que apunta al siguiente nodo. El primer nodo se llama cabeza y el último nodo tiene una referencia nula. El número de nodos que componen la lista no es fijo y se puede cambiar a pedido.

Siéntase libre de echar un vistazo a mi publicación de blog completa sobre el tema: Lista vinculada | Por qué aprendemos esta estructura de datos – Blog (@xnorcode)

Saludos,

Andreas

Imagine que quiere mantener conectada su creciente colección de libros. Algunos de los libros en el estante no son tuyos. Entonces encuentra un lugar libre en su primer libro [digamos la última página] y escribe el ISBN del libro # 2. Repita con el libro N y ISBN N + 1 hasta que se quede sin libros.

Insertar es bastante simple. Tome un nuevo libro y agregue el ISBN del libro anterior # 1. Siempre querrá almacenar el ISBN del primer libro en algún lugar especial para que sepa dónde comienza la lista.

La búsqueda es algo lenta. En el caso de los libros N, obtendrá un promedio de N / 2 búsquedas a partir del libro n. ° 1 y finalmente llegará al libro sin el siguiente ISBN.

Eliminar un libro antiguo significa que debe volver a escribir el ISBN en el libro anterior con el ISBN del libro después.

Si alguien escribe el ISBN de un libro anterior por error, ahora tiene un bucle que “colgará” cualquier recorrido ingenuo de la lista de libros.

Para una pequeña cantidad de libros esto no es tan malo. Para alguien con una gran biblioteca, esta estructura de datos mostrará sus limitaciones de escala.

Lea esta publicación: Estructuras de datos para la codificación de entrevistas: informática en inglés simple | Pastel de entrevista

Sin duda, el desglose mejor y más fácil de entender de las estructuras de datos fundamentales, incluidas las listas vinculadas.

Hola, este tutorial puede ayudarlo a comprender las listas vinculadas: Lista ordenada [vinculada] autoorganizada en C ++ – Vardan Grigoryan (vardanator) – Medio

La lista vinculada es básicamente un grupo de estructuras. Cada elemento de estructura se divide en un nodo y una parte vinculada. El nodo contiene los datos que incluyen variables de diferentes tipos de datos y la parte de enlace es un puntero de estructura que apunta al otro nodo.

por ex

nodo de estructura

{
datos int;

estructura nodo * enlace;

}

Voy a responder su pregunta exacta primero y luego voy a responder una pregunta un poco diferente “¿Qué es una lista en las estructuras de datos de programación”? En primer lugar, si va a admitir eliminaciones y adiciones, elegirá una lista doblemente vinculada sobre una lista individualmente vinculada. La clase completa para una lista de doble enlace en C # se muestra en el siguiente enlace Cálculo – Lista. Sin embargo, este tipo de clase ahora está desactualizado. Ahora es la norma que una lista tenga acceso directo usando un indexador, como una matriz. La clase .Net integrada en la clase admite la indexación. Originalmente, Calculus tenía una clase List, que en última instancia era un Diccionario. Sin embargo, la clase List también tenía todas las características de una matriz, por lo que List cambió su nombre a Array. Es decir, List desapareció por completo a favor de las matrices dinámicas. Las matrices siguen siendo como diccionarios (es decir, Array es como Dictionary ). La matriz en su nuevo formato se puede convertir en una base de datos.

La diferencia entre un Array y un Dictionary es que los arrays tienen la noción de la entrada ‘siguiente’ (solo agregue uno al índice). Esto da lugar al método Agregar, que se agrega al final de la matriz. Esta es fundamentalmente la razón por la cual las matrices dinámicas se pueden usar para reemplazar listas (porque normalmente se agrega al final de una lista). Para ver ejemplos de listas / matrices, consulte Cálculo – Guía – Matrices.

Linked List es una de las formas eficientes de almacenar datos, la estructura de datos significa cómo se pueden almacenar los datos para que sea fácil de buscar y operar. Entonces, la lista vinculada es una de las formas de hacerlo en la estructura de datos.

Fuente: Introducción a la lista vinculada

Linked List es una estructura de datos lineal y es una estructura de datos muy común que consiste en un grupo de nodos en una secuencia que se divide en dos partes. Cada nodo consta de sus propios datos y la dirección del siguiente nodo y forma una cadena. Las listas enlazadas se utilizan para crear árboles y gráficos.

Primero usamos la matriz, pero en el caso de la matriz tenemos que definir el tamaño en el momento de la declaración o podemos tocar la matriz dinámica, pero luego la lista de enlaces está allí, hacemos un nodo y luego adjuntamos otro al que le dimos la dirección del nodo anterior. este nodo usando este punto o podemos acceder a todos los nodos de una lista vinculada. En esto solo necesitamos la dirección de un nodo si es una lista enlazada única, entonces queremos el primer nodo si podemos acceder doblemente a anterior y siguiente. En la lista vinculada no nos quedaremos sin espacio como si cada vez que quisiéramos agregar creáramos un nodo y lo adjuntamos a la lista vinculada que es la principal característica poderosa de una lista vinculada. Espero que lo entiendas bien. Avíseme si tiene alguna otra duda con respecto a la lista vinculada.

Una lista vinculada es muy parecida, una lista de cosas que están vinculadas entre sí. Sé que no suena útil, pero lo es.

Me gusta pensar en ellos como un collar de perlas. Tome un collar de perlas y desabroche el broche para que se pueda colocar en una línea. Ahora agarra el broche con tus dedos. El cierre es donde comienza la lista y la cadena es cómo se pasa de un elemento al siguiente. No puedes saltarte, solo puedes pasar de uno a otro.

En términos más informáticos, el cierre es una referencia al encabezado de la lista. Cada perla son los datos contenidos en cada nodo. Y cada bit de cadena es la referencia al siguiente nodo. Es importante comprender que no hay forma de encontrar un nodo en particular sin recorrer la lista. No hay referencia directa a ellos. Si pierde la referencia principal, ha perdido toda la lista.

Una lista vinculada es cuando tiene una lista de elementos de datos y almacena cada uno de ellos por separado, pero cada uno con una referencia al siguiente elemento.

Entonces, para encontrar algo, debe comenzar con el primero, luego siga las referencias de la cadena hasta que lo encuentre.

Para insertar algo, es posible que deba redirigir algunas de las referencias adecuadamente.