Lista Enlazadas Simples

Ok, empecemos por esta que es la más sencilla, aquí la definición: «Es un grupo de elementos en forma de secuencia»

Y antes de que me lo digas, si se que parece que estoy diciendo array de manera fancy y si, son casi iguales.

La lista enlazada nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber «a priori» los elementos que puede contener.

¿Cómo creamos una lista como concepto?

Antes que programar ni nada así, vamos a hablar de ideas, imagina que tienes una información que quieres guardar:

Como por ejemplo un número o una letra:

Ahora vamos por la clave, los nodos.

Nodos

Vamos a meter cada información que queramos guardar en la lista en un nodo, esto es un nodo:

Partes de un Nodo

El nodo tiene dos partes:

Dato: Representa el dato a almacenar.Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.
Enlace: Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Lista

Ahora podemos dar hasta una mejor definición de lista: Un montón de nodos.

Diagrama

Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero. La asignación de memoria es hecha durante la ejecución.

En una lista los elementos son contiguos en lo que concierne al enlazado. En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos. El enlace entre los elementos se hace mediante un puntero. En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento tiene que apuntar hacia NULL (el fin de la lista).

Partes de la Lista

Claro que no pudieron parar ahí así que les pusieron nombres raros a sus partes:

Cabeza

Es el nodo principal y es el único que necesitamos para acceder a la lista y empezar a trabajar, pues simplemente vamos accediendo de enlace a enlace hasta llegar a donde queramos.

Y a todo lo que no es cabeza le llamamos cola:

Y así podemos irnos al infinito porque las colas son listas, que tienen una cabeza y así:

Ventajas

Una vez que ya aprendimos que son las listas, nos preguntamos ¿porque usarlas?

Los nodos no tienen porque estar contiguos en memoria, gracias a esto evitar problemas al trabajar con gran cantidad de datos.
Pueden tener longitud variable
Podemos agregar o quitar elementos en tiempo de ejecucción.

Pero como en la vida también tienen cosas negativas:

No tienen un indice, por lo que no podemos entrar a cualquier nodo así como así
Necesitan más espacio en memoria, pues guardo el dato y el enlace.