Listas Enlazadas

  1. Implemente el TDA lista enlazada con las siguientes primitivas:

    1. lista_t *lista_crear(),

    2. void lista_destruir(lista_t *l, void (*destruir_dato)(void *dato));,

    3. bool lista_es_vacia(const lista_t *l);,

    4. bool lista_insertar_comienzo(lista_t *l, void *dato);,

    5. bool lista_insertar_final(lista_t *l, void *dato);,

    6. void *lista_extraer_primero(lista_t *l);,

    7. void *lista_extraer_ultimo(lista_t *l);,

    8. void *lista_buscar(const lista_t *l, const void *dato, int (*cmp)(const void *a, const void *b));,

    9. void *lista_borrar(lista_t *l, const void *dato, int (*cmp)(const void *a, const void *b));,

    10. void lista_recorrer(const lista_t *l, bool (*visitar)(void *dato, void *extra), void *extra);.

  2. Agregue al TDA lista enlazada las siguientes primitivas:

    1. void lista_mapear(lista_t *l, void *(*f)(void *dato, void *extra), void *extra); que aplique la función f a cada uno de los datos de la lista.

    2. lista_t *lista_filtrar(lista_t *l, bool (*f)(void *dato, void *extra), void *extra); que retorne una nueva lista que tenga los elementos de l donde f devuelva true. Los elementos deben ser extraídos de la lista l.

    3. bool lista_extender(lista_t *a, const lista_t *b); que agregue a la lista a todos los elementos de la lista b.

    4. void **lista_a_vector(const lista_t *l, size_t *n); que retorne un vector con cada uno de los datos de la lista l y la cantidad de elementos en n.

  3. Implemente el TDA iterador de lista enlazada, el cual tiene acceso a la implementación interna del TDA lista. El TDA iterador sirve para iterar cada uno de los datos contenidos en una lista. Debe tener las siguientes primitivas:

    1. lista_iterador_t *lista_iterador_crear(lista_t *l);, crea un nuevo iterador que apunta al primer elemento de la lista l.

    2. void lista_iterador_destruir(lista_iterador_t *li);.

    3. void *lista_iterador_actual(const lista_iterador_t *li);, devuelve el dato actual del iterador o NULL si el iterador ya se terminó.

    4. bool lista_iterador_siguiente(lista_iterador_t *li);, incrementa el iterador. Devuelve true si la lista aún no se terminó.

    5. bool lista_iterador_termino(const lista_iterador_t *li);, retorna true si el iterador ya llegó al final de la lista.

    Y además:

    1. void *lista_iterador_eliminar(lista_iterador_t *li);, elimina el nodo actual de la lista, devuelve el dato contenido en ella. El iterador automáticamente pasa a apuntar al elemento siguiente.

    2. bool lista_iterador_insertar(lista_iterador_t *li, void *dato);, inserta un nodo nuevo después de la posición actual. El iterador permanece apuntando el dato actual.

    Teniendo este iterador implementado deberíamos ser capaces de iterar una lista l con un fragmento como el siguiente:

    lista_iterador_t *li;
for(
    li = lista_iterador_crear(l);
    !lista_iterador_termino(li);
    lista_iterador_siguiente(li)
) {
    void *dato = lista_iterador_actual(li);
    dato_imprimir(dato);
}
lista_iterador_destruir(li);

  4. Agregue al TDA lista enlazada una primitiva que invierta la lista.

  5. Una lista circular es una lista cuyo último nodo está ligado al primero, de modo que es posible recorrerla infinitamente.

    Implementar el TDA lista circular, incluyendo las primitivas insertar(), borrar() y extraer().

  6. Una lista doblemente enlazada es una lista en la cual cada nodo tiene una referencia al anterior además de al próximo de modo que es posible recorrerla en ambas direcciones.

    Implementar el TDA lista doblemente enlazada, incluyendo las primitivas insertar(), borrar() y extraer().