Fecha de publicación: 26-abr-2013 18:27:03
Hasta el momento hemos estructurado nuestros datos en la memoria utilizando registros (Struct) y vectores. También, hemos vinculado algún registro con otro usando punteros, (Por ejemplo, cuando hacemos un registro con los datos básicos de la persona y le agregamos un puntero a datos opcionales). Sin embargo la capacidad de enlazar registros nos permite realizar estructuras más complejas, enlazando nodos entre ellos. La primer estructura que vemos siguiendo esta idea es la de una lista enlazada.
Una lista enlazada compite en cierta forma con un array dinámico (de esos que redimensionamos con realloc), ya que tanto con listas enlazadas o con vectores dinámicos podemos implementar un TDA al que denominamos Lista.
En un breve análisis descubrimos que una implementación basada en array nos conviene en caso de tener un problema que requiera muchas búsquedas sobre los elementos, ya que puedo acceder directamente por el índice. Mientras que en una lista enlazada conviene en aquellos casos en que tenemos muchas modificaciones sobre la lista (se agregan o eliminan elementos bastante frecuéntemente)
Definimos una primer interfaz de nuestro TDA, en el cual agregamos y borramos elementos por el final de la lista.
TDA:Lista crearLista() -> Lista agregarAlFinal(Lista, Elemento) eliminarUltimo(Lista) liberarLista(Lista)y le agregamos un método para imprimir todos los elementos (sólo para probar como funciona, ya que no le agregamos los métodos para consultar por un elemento).
imprimir(Lista)
imprimirLista(Lista)Implementación: Structs
Los elementos que queremos agregar y borrar a la lista son registros que corresponden a Personas (tienen nombre y edad). Aclaramos que Persona podría tener su propio TDA, pero como nos enfocamos en la Lista, dejamos el struct a la vista del usuario en el encabezado.
Detectamos que necesitamos 3 structs para cumplir el objetivo.
En lista.h tenemos:
struct ListaStruct;typedef struct ListaStruct Lista;struct DataStruct { char nombre[30]; int edad;};typedef struct DataStruct Data;Y en lista.c
struct NodoStruct { Data data; struct NodoStruct * siguiente;};typedef struct NodoStruct Nodo;struct ListaStruct { Nodo * primero;};Implementación: constructor y destructor
La construcción y destrucción de una lista es similar a lo que ya veníamos trabajando. (ojo que el destructor más adelante lo volvemos a modificar)
lista.h
Lista* crearLista();void liberarLista(Lista * lista);lista.c
Lista* crearLista() { Lista * lista = malloc(sizeof(Lista)); lista->primero = NULL; return lista;}void liberarLista(Lista * lista) { free(lista);}Agregar un elemento al final
Para agregar un elemento a la lista, detectamos que necesitamos hacer cosas distintas si se trata de una lista vacía o una lista con algún elemento.
Como saber si una lista vacía es algo que le puede intersar al usuario de nuestro TDA, lo agregamos al .h
lista.h
int listaVacia(Lista * lista);void agregarAlFinal(Lista * lista, char * nombre, int edad);lista.c
int listaVacia(Lista * lista) { return lista->primero == NULL;}Nodo * crearNodo(char * nombre, int edad) { Nodo * nodo = malloc(sizeof(Nodo)); nodo->data.edad = edad; strcpy(nodo->data.nombre, nombre); nodo->siguiente = NULL; return nodo;}void agregarAlFinal(Lista *lista, char * nombre, int edad) { Nodo * nodo = crearNodo(nombre, edad); //si tengo que agregar al principio? if (listaVacia(lista)) { agregarEnListaVacia(lista, nodo); } else { agregarEnElFinal(lista, nodo); }}Agregar en la lista vacía es sencillo:
void agregarEnListaVacia(Lista * lista, Nodo * nodo) { lista->primero = nodo;}
Pero agregar al final tiene una complejidad: recorrer la lista. Anteriormente, la única estructura que recorríamos eran vectores, ya sea con notación vectorial
int i = 0;while (i < size) { vector[i]; //asi accedo a la info i++}O con aritmética de punteros
int* p = vector;while (p < vector + size) { *p; //asi accedo a la info
p++;}Pero para estas estructuras esa forma de recorrer no sirve, ya que los nodos no están en espacios contiguos. Por eso para recorrer una estructura enlazada hacemos:
Nodo * punteroVariable = lista->primero;
while(punteroVariable != NULL) { *punteroVariable; //asi accedo a la info punteroVariable = punteroVariable->siguiente}Como para agregar un elemento del final necesito llegar hasta el último nodo pero sin pasarme la condición del while cambia:
void agregarEnElFinal(Lista *lista, Nodo* nodo) { Nodo * punteroVariable = lista->primero; while(punteroVariable->siguiente != NULL) { punteroVariable = punteroVariable->siguiente; }//En este punto punteroVariable me apunta al último nodo de la lista punteroVariable->siguiente = nodo;}Actualizando el destructor
Tomamos nota de que nuestro destructor solo está liberando el struct lista y no a sus nodos, por lo tanto modificamos el código para recorrer la lista e ir liberando los nodos. Necesito una variable auxiliar para poder avanzar el puntero y luego liberar (ya que si lo hago en el orden inverso accedo a memoria que ya no es mía)
void liberarLista(Lista * lista) { Nodo * punteroVariable = lista->primero; Nodo * nodoALiberar; while (punteroVariable != NULL) { nodoALiberar = punteroVariable; punteroVariable = punteroVariable->siguiente; free(nodoALiberar); } free(lista);}Eliminando un elemento
Cuando eliminamos un elemento, también tenemos que tener en cuenta si estamos tratando con el último elemento de la lista o no, ya que en un caso hay que modificar el puntero del struct lista, mientras que en otro caso modificamos el siguiente del anteultimo elemento. Nuestra forma de resolverlo implica preguntar por la cantidad de elementos de la lista (También modificamos el TDA para exponer esa función)
lista.h
void eliminarUltimo(Lista * lista);int tamanio(Lista * lista);lista.c
Para contar simplemente contamos :)
int tamanio(Lista * lista) { int count = 0; Nodo * puntero = lista->primero; while (puntero != NULL) { count++; puntero = puntero->siguiente; } return count;}
El código de eliminar al final es:
void eliminarUltimo(Lista * lista) { if (tamanio(lista) == 1) { eliminarUnicoElemento(lista); } else { eliminarEnElFinal(lista); }}Eliminar un único elemento no trae problemas
void eliminarUnicoElemento(Lista * lista) { free(lista->primero); lista->primero = NULL;}Pero para eliminar en el final nos damos cuenta que necesitamos dos punteros, porque si tenemos uno sólo, al detectar el último elemento de la lista se nos escapó el anteultimo, el cual necesitamos para indicarle que es el nuevo final de la lista seteando NULL en su siguiente.
void eliminarEnElFinal(Lista * lista) { Nodo * anterior = lista->primero; Nodo * actual = lista->primero->siguiente; while (actual->siguiente != NULL) { anterior = actual; actual = actual->siguiente; } free(actual); anterior->siguiente = NULL;}En este punto ya tenemos nuestro TDA completo, sin embargo una cosa que le quisimos agregar y nos obligó a pensar un poco más es el agregar un elemento con una posición. Si la posición a agregar es 0 (el primer elemento) significa que tenemos que modificar el puntero del struct lista, en otro caso hay que modificar el siguiente de un nodo.
lista.h
void agregarEnPosicion(Lista * lista, int posicion, char * nombre, int edad);lista.c
void agregarEnPosicion(Lista * lista, int posicion, char * nombre, int edad) { Nodo * nodo = crearNodo(nombre, edad); if (posicion == 0) { agregarPrimero(lista, nodo); } else { agregarEnElMedioOAlFinal(lista, posicion, nodo); }}Cuando analizamos la opción de agregar en la primer posición, nos damos cuenta que el código a escribir puede ser el mismo tanto de si se trata de una lista vacía o una lista llena. Hay que:
lista.c
void agregarPrimero(Lista * lista, Nodo * nodo) { Nodo * primeroAnterior = lista->primero; lista->primero = nodo; nodo->siguiente = primeroAnterior;}Una suerte parecida ocurre al modificar un elemento del medio o del final. el último elemento de la lista tiene NULL como siguiente y se traslada al siguiente del nuevo nodo si es que debía agregarse al final. Al igual que lo hicimos anteriormente, necesitamos recordar el nodo anterior del buscado.
lista.c
void agregarEnElMedioOAlFinal(Lista * lista, int posicion, Nodo * nodo) { Nodo * anterior = lista->primero; Nodo * actual = lista->primero->siguiente; int count = 1; while (count < posicion) { anterior = actual; actual = actual->siguiente; count++; } nodo->siguiente = actual; anterior->siguiente = nodo;}Estas funciones las usamos desde un main de prueba. por ejemplo:
main.c
#include "lista.h"#include <stdio.h>int main(int argc, char **argv) { Lista * lista; lista = crearLista(); agregarAlFinal(lista, "Javier", 30); agregarAlFinal(lista, "Leo", 32); agregarEnPosicion(lista, 1, "Pablo", 29); imprimirLista(lista); printf("\n") eliminarUltimo(lista); imprimirLista(lista); liberarLista(lista); return 0;}Que nos quedó en el tintero (y que ya están en condiciones de resolver solitos)