C++ / estructuras de datos basados en nodos

Bienvenidos sean a este post, hoy veremos una estructura de datos.

En el post anterior vimos a vector que es una estructura de datos muy popular pero tenia un inconveniente. Este era si nos centrabamos en agregar los elementos al inicio del mismo. Este inconveniente no existe en las estructura de datos basados en nodos porque no almacenan la informacion en bloques continuos. Es decir, que este ubica a los nodos en memoria sin orden y practicamente en lugares aleatorios de la memoria. Por esto se dice que cada nodo esta enlazado con los otros.

El mas popular e introductorio a este tipo de estructura es el conocido como listas enlazadas. De forma basica, tenemos los distintos nodos enlazados entre si pero tambien dos partes que se denominan como head y tails, siendo uno para el puntero inicial y el otro para el puntero final de la lista respectivamente. Una de las ventajas de este contra vector es su rapidez, pero vector es mucho mas compacto con respecto a este. Veamos un ejemplo para entenderlo:

#include <iostream>
using namespace std;

class LinkedList{
    struct Node {
        int x;
        Node *next;
    };

public:
    LinkedList(){
        head = NULL;
    }

    ~LinkedList(){
        Node *next = head;
        while(next) {
            Node *borrable = next;
            next = next->next;
            delete borrable;
        }
    }

    void agregar(int val){
        Node *n = new Node();
        n->x = val;
        n->next = head;
        head = n;
    }

    int quitar(){
        Node *n = head;
        int ret = n->x;

        head = head->next;
        delete n;
        return ret;
    }

private:
    Node *head;
};

int main() {
    LinkedList lista;

    lista.agregar(5);
    lista.agregar(10);
    lista.agregar(20);

    cout << lista.quitar() << endl;
    cout << lista.quitar() << endl;
    cout << lista.quitar() << endl;

    return 0;
}

Hablemos primero sobre la clase LinkedList, la cual sera nuestra lista enlazada. Lo primero que tenemos es un struct, el cual representara a cada nodo de nuestra lista. En esta tenemos dos propiedades, la primera representa al valor que almacena y la segunda sera para el siguiente nodo. En la parte privada, tenemos una sola propiedad y esta representa al head de nuestra lista. En la parte publica, primero tenemos el constructor que iniciara a nuestra head con un valor nulo o el puntero null, si quieren saber mas sobre este tema tengo este post, y tambien un destructor. Este tendra un puntero del tipo node y a este lo iniciaremos con el valor en head. El bucle que se ejecutara mientras next posea un valor, en este crearemos un puntero que contendra el next actual, luego le asignamos el valor del siguiente nodo y por ultimo borramos el nuevo puntero. Esto se repetira hasta que next no posea ningun valor. Lo siguiente son los dos metodos encargados de manejar los valores de la lista.

El metodo agregar recibira un valor y se encargara de agregarlo a la lista como un nodo. Para ello primero crearemos un puntero de tipo Node, Lo siguiente sera asignar a x el valor recibido, a next le asignaremos head y head ahora apuntara al puntero creado aca. Esto se repetira con cada valor que vayamos agregando y se reemplazara a head. El metodo quitar tambien crea un puntero del tipo Node y le asignamos a head. Despues almacenaremos en una variable el valor que posee el nodo. Seguido a esto pasaremos a head al siguiente nodo, borramos el puntero y finalmente devolvemos el valor eliminado. Esto es especialmente util para saber cual valor fue eliminado.

En el main, primero creamos a la lista. Despues le asignamos tres valores mediante el metodo agregar y seguido a esto los quitaremos pero usaremos a cout para mostrar el valor que devuelve. Compilemos y ejecutemos para ver su salida:

$ ./lista
20
10
5
$

Observen que se respeto el ingrreso de los datos, asi como la remocion de los mismos de la lista. Hasta aca podemos ver que los elementos se ingresan de manera distinta, pero no tanto, con respecto a un vector. Pero en que debemos centrarnos para poder usar uno u otro? Simple, las operaciones y la velocidad. Tomemos como ejemplo el cliente de email del post anterior. En ese caso, el vector nos venia muy bien para leer un elemento en cualquier posicion porque siempre tiene un tiempo constante y podemos realizar esta tarea sin mayor esfuerzo. Si usaramos una lista enlazada este los almacenara en forma lineal y tardaremos mas tiempo en recuperarlo. Por lo tanto, si nosotros necesitamos mayor uso de lectura que de escritura, el vector va a ser una mejor opcion.

En cambio, si necesitamos una coleccion donde estas continuamente agregando y removiendo elementos, una lista enlazada es mas adecuada que un vector. Un tema que no debemos olvidar es la memoria cache. Los vectores tienen una muy buena ubicacion en memoria, al leer el primer elemento de este implica que copiaremos N cantidad de elementos en el cache. Esto hara que las proximas lecturas del vector seran mas rapidas que las de listas enlazadas pero esto sera un tema que analizaremos en el proximo post.

En resumen, hoy hemos visto a estructuras de datos basados en nodos, que son, como se comportan, como podemos usarla, un ejemplo para verla en accion, asi como los pros y contras con respecto a los vector. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.