¿Qué es una lista enlazada?

Unas de las primeras estructuras de datos que se estudian a la hora de aprender programación son los arrays. Los arrays otorgan una gran eficiencia al código al poder acceder a todos los elementos de la lista de forma inmediata mediante el uso de un índice. No obstante, presenta grandes problemas a la hora de trabajar cuando el tamaño de este se vuelve dinámico. Para solucionar este problema, en el que el tamaño de nuestra lista no va a ser fijo, utilizamos listas enlazadas.

Una lista enlazada es una estructura de datos muy similar al array, con la diferencia de que una lista enlazada no almacena los elementos en zonas contiguas de la memoria. Es decir, los datos no se van a almacenar de forma lineal en memoria, sino que se van a almacenar en diferentes zonas de la memoria sin tener en cuenta la localización del resto de elementos.

Cada elemento de una lista enlazada es un nodo. Cada nodo va a almacenar dos valores. Uno de estos valores será el dato que queramos almacenar en la lista, del mismo modo que almacenábamos datos en un array. El dato restante será una referencia al siguiente nodo de la lista. Esta referencia será la que nos permitirá acceder a los diferentes elementos que conforman la lista, ya que al no estar almacenados de forma contigua, no se permite el uso de un índice como sucede con los arrays.

Por tanto, vemos que las listas enlazadas tienen la ventaja de que podemos añadir elementos a las mismas sin tenernos que preocupar porque haya espacio contiguo disponible. Esto hace que la adición sea inmediata y que solo se reserve memoria que sí o sí va a ser utilizada. En contraposición, es necesario recorrer toda la lista para poder acceder a una posición determinada. Es decir, para poder acceder al cuarto elemento necesitamos acceder primero al tercer elemento, dado que es este el único que sabe dónde está almacenado el cuarto elemento. Para acceder al tercer elemento primero tenemos que acceder al segundo, y así sucesivamente hasta llegar al primero. Así, con el uso de listas enlazadas no podemos acceder inmediatamente a cada elemento.

Para seguir aprendiendo…

Cartagena999: Listas enlazadas

PedroGonzálezRuiz: Listas enlazadas en C

CCM: La lista enlazada simple

Anuncio publicitario