26/04/2013 - Clase 4 - Listas Enlazadas en C

Fecha de publicación: 26-abr-2013 18:27:03

Intro

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)

TDA Lista

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.

    • Lista: Nuestra lista lo único que necesita es un puntero al primer nodo.
    • Nodo: Cada eslabón de la lista tiene que contener un elemento y un puntero al que le sigue. Nos damos cuenta que Lista no puede ser Nodo ya que no tiene asociado un elemento.
    • Elemento: Es lo que agregamos y quitamos a la lista (En clase lo llamamos Data)

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.

    • Si es una lista vacía, se necesita modificar el puntero "primero" que tiene la lista
    • Si es una lista con elementos, se necesita modificar el puntero "siguiente" que tiene el último nodo.

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:

    1. asignar el siguiente del nuevo nodo a lo que antes se conocía como el primer elemento de la lista. Si no existía el nodo, el primero es NULL y por ende el siguiente del nuevo nodo también será NULL indicando así el final de la lista.
    2. Luego hay que hacer que el puntero primero del struct lista apunte al nodo.

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)

    • Hacer un eliminar que reciba una posición
    • Modificar la función agregarAlFinal para que reutilice el método que recibe una posición