30/04/2013 - Clase 4 - TDA Lista

Fecha de publicación: 01-may-2013 16:13:31

Arrancamos repasando muy rápidamenete lo visto hasta ahora en la materia:

1. Repaso de C, pila, pasaje de parámetros por valor, structs
2. Luego vimos manejo de memoria dinámica manual, con las funciones malloc, realloc y free
3. La clase pasada vimos la idea de TDA, y para su implementación en C tuvimos que utilizar las cosas vistas en los dos puntos anteriors

En esta clase arrancamos ya con la Unidad 3, específicamente vamos a ver uno (si no él) TDA más común y importante en la programación: la Lista

TDA Lista

Arrancamos contando el concepto del lista, y describiendo en forma abstracta las operaciones. Eso está en esta página, que de paso digo, deben leer porque es la guía del tema. Aunque no incluye el código.

Reflexionamos sobre el hecho de que los arrays de C no son listas, si no un tipo más básico que nos lleva a tener que preocuparnos por muchos detalles de la representación de los datos en la memoria. Por ejemplo, si necesito agregar un elemento más, tengo que yo, manualmente preocuparme por alocar más lugar.

Dijimos que en cierta forma usar arrays como listas, es como usar char* para strings. Otro TDA que C no trae ya de movida :(

Implementación

Entonces identificamos que la implementación del TDA podría representar (guardar) los datos/elementos de la lista de diferentes formas. Al menos dos:

• en una podría alojar los elementos contiguos uno detrás del otro. Para esto en C podría usar un array.
• o podría tener Nodos que no estén contiguos, pero que se conozcan entre sí. Es decir que cada nodo, conozca al siguiente.

A lo segundo se lo llama Lista Enlazada y fue la primer implementación que vimos.

Pero primero:

lista.h

Vimos la definición del TDA en forma abstract en el archivo lista.h

(Acá muestro solo la parte importante del código, para que no ocupe demasiado, pero les estoy adjuntando un zip con el export del proyecto en eclipse)

struct ListaStruct;

typedef struct ListaStruct* Lista;

typedef void* Elemento;

// ***********************

// ** OPERACIONES

// ***********************

Lista crearLista();

void liberarLista(Lista lista);

int tamanio(Lista lista);

int vacia(Lista lista);

void agregar(Lista lista, Elemento elemento);

Elemento elementoEn(Lista lista, int indice);

void removerItemEn(Lista lista, int indice);

Acá vemos que define el struct ListaStruct, aunque vacío, sin contenido, ya que va a depender de la implementación qué miembros tendrá.

Por otro lado, como nuestra lista va a aceptar cualquier tipo de elemento, ésto significa en C, utilizar punteros genéricos (a cualquier tipo de dato), que se hacía como void*.

Ahora, como se hace medio dificil leer el código con void* (y más si necesitamos despues un puntero a punteros genéricos void**), estamos declarando acá también un nuevo tipo Elemento que es equivalente a void*. Así, nuestras funciones van a declararse con Elemento, que suena más fácil de entender.

Lista Enlazada (Simple)

Arrancamos entonces a mostrar la implementación de la lista enlazada, en su versión más simple.

Dijimos que necesitábamos Nodos, y que cada nodo tendría:

• el dato que almacena
• un puntero al nodo siguiente.

Pero además, necesitamos definir el struct principial, la ListaStruct, que dijimos que solo necesitaba conocer al primer nodo (a través de un puntero).

Eso entonces lo hacíamos así:

#include <stdio.h>

#include <stdlib.h>

#include "lista.h"

struct NodoListaStruct {

    struct NodoListaStruct* proximo;

    Elemento dato;

};

typedef struct NodoListaStruct* Nodo;

struct ListaStruct {

    Nodo primero;

};

Y luego vimos como se implementaban cada una de las operaciones.

Arrancamos con el crear y el liberar.

Lista crearLista() {

    struct ListaStruct* lista = (struct ListaStruct*) malloc(sizeof(struct ListaStruct));

    lista->primero = NULL;

    return lista;

}

void liberarLista(Lista lista) {

    Nodo nodo = lista->primero;

    while(nodo != NULL) {

        Nodo proximo = nodo->proximo;

        free(nodo);

        nodo = proximo;

    }

    free(lista);

}

El crear es simple. Aunque vimos que liberar una lista no significaba símplemente liberar la zona de memoria apuntada por Lista, ya que eso solo liberaría el ListaStruct, pero como éste tiene un puntero al primer nodo que es otro struct, y a su vez este un puntero al próximo, etc.. todos los nodos nos iban a quedar "colgando", ocupando memoria que nadie iba a usar.

Pasaría esto:

Así que, liberar una lista enlazada requiere primero liberar todos sus nodos. Y para liberar un nodo, primero debemos pedirle la dirección del próximo nodo, antes de hacer free.

Esto es lo que hace el código que vimos.

Luego las operaciones relacionadas con el tamaño de la lista:

int tamanio(Lista lista) {

    Nodo nodo = lista->primero;

    int contador = 0;

    while (nodo != NULL) {

        contador++;

        nodo = nodo->proximo;

    }

    return contador;

}

int vacia(Lista lista) {

    return tamanio(lista) == 0;

}

Acá notamos que para saber cuántos elementos hay en la lista, tenemos que ir recorriendo todos los nodos, contándolos, hasta que encontremos el último nodo, cuyo puntero proximo estará en NULL.

La otra función, vacia, utiliza el tamanio. Aunque alguien ahí comentó una solución más eficiente, que sería:

int vacia(Lista lista) {

    return lista->primero == NULL;

}

Ya que no requiere recorrer los elementos.

Luego vimos que agregar un elemento, requería:

• crear un nuevo nodo
• conocer al último, y actualizarle su puntero proximo para que apunte al nuevo nodo

Eso es lo que sucede acá:

Nodo crearNodo(void* data);

Nodo ultimoNodo(Lista lista);

void agregar(Lista lista, void* data) {

    Nodo nuevoNodo = crearNodo(data);

    Nodo ultimo = ultimoNodo(lista);

    if (ultimo == NULL) {

        lista->primero = nuevoNodo;

    }

    else {

        ultimo->proximo = nuevoNodo;

    }

}

Nodo crearNodo(Elemento data) {

    Nodo nodo = malloc(sizeof(Nodo));

    nodo->dato = data;

    nodo->proximo = NULL;

    return nodo;

}

Nodo ultimoNodo(Lista lista) {

    Nodo nodo = lista->primero;

    while (nodo != NULL && nodo->proximo != NULL) {

        nodo = nodo->proximo;

    }

    return nodo;

}

Ubicar el último nodo, requiere recorrerlos todos.

Después, el obtener el dato en cierta posición, también requiere recorrrer hasta llegar a la posición:

// no tienen en cuenta indices incorrectos

Elemento elementoEn(Lista lista, int indice) {

    Nodo nodo = lista->primero;

    int i;

    for (i = 0; i < indice; i++) {

        nodo = nodo->proximo;

    }

    return nodo->dato;

}

Y, por último, remover también requiere ubicar al nodo, pero además, necesitamos conocer a su anterior (recordarlo), porque debemos conectarlo con el siguiente del nodo que vamos a borrar. Hacer "un puente", para garantizar que borramos al nodo, pero dejamos todo conectado como debe.

// no tienen en cuenta indices incorrectos

void removerItemEn(Lista lista, int indice) {

    Nodo actual = lista->primero;

    Nodo anterior = NULL;

    int i;

    for (i = 0; i < indice; i++) {

        anterior = actual;

        actual = actual->proximo;

    }

    if (anterior != NULL) {

        anterior->proximo = actual->proximo;

    }

    else {

        lista->primero = actual->proximo;

    }

    free(actual);

}

Inconvenientes o posibles "mejoras"

Notamos que para varias funciones teníamos que recorrer los nodos. Eso nos parecía un posible "problema", ya que el tiempo que esas funciones van a demorar va a depender de la cantidad de elementos que tenga. Cuántos más elementos yo agregue, más va a tardar.

Por ejemplo, la función tamanio.

tamanio() para una lista de 100 elementos va a tardar 10 veces más que para una lista de 10 elementos.

Anticipamos que esto está relacionado con el tema de la última unidad, Complejidad Computacional.

Y dijimos que las funciones se pueden analizar para entender su orden en cuanto a tiempo. Esto se denomina orden y se da con una ecuación matemática, que no expresará exáctamente cuanto tardará una función, si no, a grandes rasgos una idea de su magnitud.

En nuestro ejemplo tamanio se dice de orden lineal, porque crece linealmente con la cantidad de elementos, que llamamos "N".

Esto se escribe:

O(n)

Existen otros órdenes como exponencial, logarítmico, etc.

Mejorando tamanio()

Vimos que una forma de mejorar la función tamaño era hacer que la ListaStruct además de conocer al primer elemento, conozca también el tamaño actual.

Para esto tocamos:

• ListaStruct, para agregarle la longitud, un int.
• La función tamanio() que ahora solo hace return lista->longitud
• Además, tenemos que tocar las funciones que alteran los elementos, es decir:
  • agregar: para incrementar el tamaño
  • remover: para decrementar

Al hacer esto, tamanio() ahora ya no depende de la cantidad de items, porque la estructura lo recuerda como un número.

Así que pasamos de orden lineal O(n), a un orden constante, que se expresa como O(1), es decir que el tiempo de respuesta de la función es fijo. Siempre el mismo.

Mejorando el agregar

Para agregar también debíamos recorrer todo, hasta llegar al ultimo elemento (Orden O(n))

VImos que se podía mejorar haciendo que ListaStruct además de conocer al primer elemento, conozca al último.

Así, de nuevo tuvimos que tocar los mismos lugares, para actualizar el puntero a ultimo.

Y logramos la misma mejora, ahora la función agregar es O(1).

Doblemente enlazada

Por otro lado, mencionamos que, existe una variante a la lista enlazada, llamada dóblemente enlazada, donde los nodos no solo conocen al siguiente si no también al anterior. Esto era útil en el caso en que querramos recorrer la lista en sentido inverso.

Esto ya complicó un poco más el código, porque al agregar y al remover un elemento debíamos actualizar dos punteros ahora, proximo y anterior.

Pueden ver esta impelmentación con todas las mejoras anterios en lista.c.doblemente.enlazada

Lista basada en array

Finalmente vimos una implementación complétamente distinta, utilizando un array. En realidad un puntero a una sección de memoria que tendrá los elementos en forma contigua.

Ojo, vimos que no es que guardamos los elementos en sí, si no que tenemos punteros (recuerdan void*).

Tanto en el agregar como en el remover, teníamos que redimensionar la memoria para agrandar y achicar respectivamente.

Vimos que era muy parecido a lo que habíamos hecho en el ejemplo de Factura e items.

Pueden ver la implementacion en lista.c.array

Usos y ventajas

Finalmente dijimos que la lista array es mucho más eficiente para ubicar un elemento cualquiera, ya que el array permite indexar. En cambio la enlazada no.

Por otro lado, la desventaja de la implementación con array es que cada vez que agregamos un elemento, quizás haya que realocar un array completo nuevo, requiriendo así, en un momento 2 * tamaño + 1. CUando en la enlazada es mucho más eficiente el agregar que solo reserva lugar para un nuevo nodo.

Por el contrario, recorrer una lista enlazada es bastante costoso a nivel de tiempo.

Código fuente de los ejemplos

Pueden encontrar adjunto un zip con el proyecto de eclipse.

Lo pueden importar desde eclipse con File->Import, General->Archive File, seleccionar el zip.

O bien, abren el zip y le sacan los .c y .h si usan otro IDE.

Algo a notar es que para que funcione el main, tiene que elegir una de las implementaciones (ej: lista.c.array) y renombrarla (o copiarla) a lista.c. Y así lo mismo para las demás.

Entrega Trabajo Práctico

Recuerdo que la semana que viene es la entrega del TP1.

Quien ya lo tenga, me lo puede enviar antes del martes. A los demás, envíenme un mail con el zip para el martes (ese martes mismo puede ser). Así llevo un registro de quién entregó.