Listas cpp

Listas

Son una de las estructuras mas versátil, es lineal y dinámica, el concepto detrás de esta estructura es la base para muchos de los conceptos de las demas estructuras.

En una lista cada elemento apunta hacia su siguiente elemento, de ahí el nombre de lista y el último elemento apunta a nulo, lo que indica el final de lista.

Los archivos los puedes encontrar aquí

La inserción está basada en la inserción al inicio, ya que también hay inserción al final y entre elementos, la inserción entre elementos la dejaremos para los temas de ordenamiento o búsqueda.

Inserción al final la podemos encontrar en el repositorio.

typedef struct nod{
    int data;
    nod *sig;
}LISTA;

typedef LISTA* SIMPLE;

Tenemos la estructura, como había comentado en temas anteriores, creamos el nuevo tipo llamado LISTA y el tag nod, de esta manera podemos incluir a la lista dentro de si misma.

nod *sig es el puntero que nos ayuda a seguir los elementos en la lista.

Y creamos un nuevo tipo de dato llamado SIMPLE que es apuntador de tipo LISTA.

Se hace de esta manera para evitar demasiados parentésis y asteriscos por el tema de punteros a punteros.

Función push

void push(SIMPLE *head){
    SIMPLE nuevo;
    try{
        nuevo = new LISTA;
        nuevo->data = pedir();
        nuevo->sig = *head;
        *head = nuevo;
    }
    catch(std::bad_alloc&){
        std::cout << "Memory Error!\n";
        return;
    }
}

La función recibe un apuntador a SIMPLE, que si recordamos, es un apuntador a LISTA.

Creamos un apuntador llamado nuevo que será la dirección donde se agrega el nuevo valor.

Usamos try para que cuando se crea el espacio para nuevo, en caso de que no se pueda, el programa no se cierre y mostrar el mensaje de Memory Error.

¿Por qué en new usamos LISTA en vez de SIMPLE?

Es porque SIMPLE es un apuntador a LISTA por lo que si queremos reservar memoria para nuevo, debemos usar LISTA, si usaramos SIMPLE, estariamos creando un apuntador a apuntador.

Si se tiene exito en reservar memoria, entonces se accede al miembro data y se llama a la función pedir, esta función es de tipo int.

Después hacemos que nuevo->sig apunte a *head y que head sea igual a nuevo.

Por esto es una inserción al inicio, el dato recien insertado se mueve al inicio.

Función pop

void pop(SIMPLE *head){
    SIMPLE actual;
    while(*head != NULL){
        actual = *head;
        *head = (*head)->sig;
        delete actual;
    }
}

En realidad la función elimina todos los elementos.

Esta función itera sobre todos los elementos a tráves de moverse hacia la siguiente dirección de memoria mediante sig.

En la función creamos actual que es el nodo que nos sirve para recorrer cada dirección de memoria.

Usamos un while para saber que cuando head sea nulo, quiere decir que termino de eliminar los elementos.

Actual apunta a *head, después head apunta a la siguiente dirección de memoria, y se libera la dirección de actual que sería la dirección a la que *head apuntaba antes.

Se usan los paréntesis para respetar que sigue siendo un puntero.

Función imprimir

void imprimir(SIMPLE head){
    int i = 0;
    while(head != NULL){
        ++i;
        std::cout << "ID nodo lista: " << i << " Valor: " << head->data << '\n';
        head =  head->sig;
    }
}

Esta función itera sobre cada elemento de la lista apuntado hacia la siguiente dirección de memoria.

Como no se requiere modificar es que no se le pone asterisco en los parámetros.

Si habrás notado en ningún momento se pide tamaño o cantidad de datos, simplemente se siguen insertando, esto es porque cada que se usa new se va reservando la dirección de memoria y simplemente se va recorriendo, en este caso como es inserción al inicio, el apuntador a NULL queda al final de la lista