Las listas simplemente ligadas son una estructura de datos que nos permite almacenar cualquier cantidad de datos. La ventaja principal es que la memoria que ocupa es solamente la necesaria a diferencia de un arreglo que puede desperdiciar memoria que no está en uso (como la memoria que se desperdicia con los arreglos: generalmente declaras un arreglo del tamaño máximo que se podría llegar a usar aunque muchas veces no se llena).
La lista simplemente ligada puede ser usada para crear estructuras de datos más complejos. Consiste en una secuencia de nodos, donde cada nodo contiene información y un apuntador al nodo que sigue. El último nodo apunta a un valor nulo (NULL) lo cual indica que es el final de la lista. De esta manera se puede recorrer la lista de forma secuencial siempre y cuando tengas un apuntador al primer elemento de la lista, como se ve la siguiente imagen (tomada del blog de xrom):
O, si quieres, puedes conceptualizarlo como un tren de vagones donde el tienes un apuntador a la locomotora y el apuntador al siguiente que hay en cada nodo es el mecanismo con el que se engancha al vagón que le sigue (Imagen cortesía de Medieducativos):
En este post me voy a enfocar en 3 cosas: agregar un nuevo nodo a la lista (al final), mostrar todos los nodos (recorrerlo) y eliminar un nodo de la lista. Antes de entrar a estos temas, hay que ver como se declara la estructura y la forma en que se usa. En este ejemplo, estoy haciendo una lista que guarda algunos datos de videojuegos. Aquí está la declaración de la estructura y una variable global que apunta al primer nodo de la lista:
La función principal del programa (main) no tiene mayor ciencia. Básicamente solo muestra un menú y pide una opción. En base a la opción deseada manda llamar funciones para dar de alta, consultar todos o eliminar alguno. Una nota antes de seguir: este programa lo hice usando el compilador Dev-C++ varsión 4.9.9.2. Este es el código (haz clic sobre la imagen para verlo más grande):
Voy a comenzar hablando de la función que da de alta un nodo al final de la lista. Primero declaro dos apuntadores a struct nodo: Temp y Temp2. Uso la función malloc para apartar RAM para almacenar la estructura de forma dinámica. Si necesitas saber más sobre el malloc, al final de este post hay ligas a páginas que son referencias para que despejes dudas sobre su sintaxis y función. Pero a grandes rasgos, el malloc sirve para asignarle memoria y devolver un apuntador hacia el espacio reservado. Una vez apartada la memoria, lleno el nuevo nodo con los datos (que son los parámetros nom, plat y pre) y al campo Sig le asigno el valor de NULL porque va a ser el último de la lista. Al final debo reorganizar los apuntadores: el apuntador Sig del elemento anterior debe apuntar a este nuevo nodo. El código que lo realiza es el siguiente:
Una vez resuelto el problema de dar de alta nodos, voy a explicar la forma en que se puede recorrer la lista y mostrar los elementos. Esto lo hice en la función llamada MuestraTodo. Declaro un apuntador llamado Temp (para no perder la costumbre, jeje) con el que voy a recorrer la lista. Uso la variable i para mostrar el número de nodo en el que voy. Al principio igualo Temp a Inicio para comenzar el recorrido. Y mientras no llego al final (o sea, Temp es diferente de NULL), muestro lo que contiene el nodo. Fíjate como se accesa un elemento por medio de un apuntador ya que difiere de la forma en que se hace cuando no usas apuntador. En lugar del punto (.), se usa una especie de flecha compuesta por el guión y el signo mayor que (->). Aquí está el código:
Ahora lo único que falta es mostrar la función que elimina un nodo de la lista. Esto es relativamente sencillo y creo que el código se explica por si solo (le puse un montón de comentarios). Básicamente es igual que la función MuestraTodo solo que esta vez, en lugar de mostrar el elemento, veo si es igual al que busco. En caso que sea igual, veo si es el primero de la lista. Si es el primero, solo cambio el valor de Inicio para que apunte al siguiente, y en caso contrario, modifico el apuntador Sig del elemento anterior (convenientemente apuntado por Anterior) para que apunte al que sigue. Una vez arreglado los apuntadores, libero la memoria usando la instrucción free. Al final viene más ayuda sobre free, pero básicamente libera la memoria que es apuntada por un apuntador (valga la redundancia). Al final devuelve un 1 si lo encontró y lo pudo borrar y un 0 si no lo encuentra. Este es el código de la función Eliminalo:
Estas son ligas donde puedes encontrar más información sobre malloc y free (y algunas otras funciones que te pueden resultar muy útiles). ¡Hasta la próxima!
- free – C con clase.
- Otros recursos sobre listas simplemente ligadas: todo tipo de listas en Wikipedia y este excelente recurso sobre listas del Cinvestav (ojo: allí hay ligas para ver agregar y eliminar nodos).
No hay comentarios.:
Publicar un comentario