17 ene. 2014

Programación en C – Listas Enlazadas – Que son y cómo se usan

Hola a todos, en esta ocasión les presento las Listas Enlazadas, estaremos viendo que son, para que sirven y como se utilizan en el lenguaje de Programación C estructurado.

Antes de definir que es una Lista Enlazada, debemos definir que es una estructura en C. Una estructura es un conjunto de datos de diversos tipos agrupados bajo un mismo nombre. Para su creación utilizaremos typedef y struct de la siguiente manera


De esta forma habremos creado una estructura llamada Cliente, que contiene un ID, un Nombre y un Apellido. Para poder cargarle datos a nuestra estructura Cliente se puede hacer de la siguiente manera


Ahora que ya sabemos cómo funciona una estructura, pasemos a ver cómo funciona una Lista Enlazada

Cuando deseamos cargar en memoria un conjunto de valores utilizamos vectores, el problema de estos es que su tamaño se encuentra pre definido en el código del programa. Tomemos como ejemplo la estructura que definimos anteriormente para clientes (ID, Nombre y Apellido), si creamos un vector de esta estructura… ¿de que tamaño debería ser? Si por ejemplo creamos un vector de tamaño 1000, este podría ser muy grande ya que tal vez nuestro programa solamente necesite cargar algunos pocos clientes y un vector tan grande sería un desperdicio de memoria, o tal vez el vector sea muy chico, ya que nuestro programa debe cargar miles de clientes en memoria, por lo cual no funcionaria. Para solucionar esta problemática existen las Listas Enlazadas, una estructura dinámica que adapta su tamaño según se necesite en tiempo de ejecución.

La Lista Enlazada se forma por estructuras llamadas nodos, las cuales se enlazaran con otro nodo por a través del puntero a su misma estructura que posee el nodo. Esto puede resultar confuso, pero veamos cómo sería la estructura para nuestra Lista Enlazada


Como podemos ver, ahora dentro de la estructura tenemos un puntero llamado siguiente, el cual apuntara al siguiente nodo de la lista, así sucesivamente hasta formar la Lista Enlazada. En esta estructura podemos observar que sNodoCliente es el nombre de la estructura, por eso el puntero siguiente es sobre este mismo (utilizamos la S al comienzo del nombre para saber que es un struct o estructura). También observamos que tNodoCliente es un tipo de dato, con el cual podemos declarar este tipo de estructura como hicimos anteriormente con Cliente (utilizamos la T al comienzo del nombre para saber que es un typedef o tipo de dato).

Para poder mantener ubicado el último elemento agregado, utilizaremos un puntero que llamaremos cabeza, el cual ira cambiando a medida que se agreguen nodos indicando cual es la cabeza (el primer elemento) de la Lista Enlazada, y utilizando este nodo poder recorrer la lista.

Para crear una Lista Enlazada hay que enlazar ese puntero siguiente al último nodo existente en la lista. Veamos un ejemplo gráfico. Realizaremos 3 operaciones:
1) Dar de alta a: ID: 45, Nombre: Dario, Apellido: Argies
2) Dar de alta a: ID: 81, Nombre: Juan, Apellido: Pepe
3) Dar de alta a: ID: 90, Nombre: Laura, Apellido: Rosas


Como podemos ver, la lista se crea de atrás hacia adelante, moviendo la cabeza en cada inserción. Al acceder a la cabeza podremos acceder al primer nodo, y al ir avanzando a través del puntero siguiente podremos ir accediendo a otros nodos hasta llegar al final de la Lista Enlazada.

Bueno, suficiente explicación teórica, momento de pasar al código, en este ejemplo podemos cargar una lista enlazada de enteros, la cual luego podremos imprimir por pantalla.


De esta forma se vería la ejecución del programa


Esto es todo por hoy, cualquier duda/pregunta en los comentarios :)

Saludos!

-----
Argies_Dario


Compilado con: Dev-Cpp
Sistema Operativo: Windows 7

Fuentes:
Ninguna

No hay comentarios:

Publicar un comentario

Dejanos tu comentario sobre esta nota