Ejemplo Sencillo de una Linked List simple en C++

Las estructuras de datos son muy importantes en el desarrollo de aplicaciones robustas, es menester por parte de los desarrolladores en cualquier lenguaje, el conocerlas, saber sus ventajas y desventajas y cual es la más apropiada según la situación que se tenga en el momento, o los requerimientos del cliente que necesita un sistema.

En esta ocasión, les mostrare a mis estimados lectores, un ejemplo de implementación muy sencillo y fácil de entender de una de las estructuras datos más importantes: las linked list.. en este el ejemplo se trata de una linked list simple implementada en lenguaje C++.

Antes de entrar en materia con el código debemos entender algunos conceptos importantes característicos de la estructura.

1. En las linked list  cada componente de la lista se le denomina NODO.
2. Cada NODO tiene un par de elementos, uno donde se almacena el dato en si y otro donde se almacena la referencia (puntero) al próximo dato de la lista.

       3. Cada elemento de la linked list mantiene un orden único entre si.

       4. A diferencia de los arrays las linked list no tiene un tamaño predeterminado, su tamaño puede ser modificado de forma dinámica, ya sea agregando o borrando elementos de la lista.

En términos generales esto estas son las características mas destacables, ahora si, vayamos a su implementeción en C++.

Primero que nada y antes de continuar, voy asumir que quien lea este post, conoce los conceptos básicos de  la programación orientada a objetos (POO) en C++, si ese no es el caso, es necesario reforzar esos conceptos antes de continuar, para ello puedes ir a este enlace:

CURSO C++ POO

**Es mi canal de youtube, puedes suscribirte para no perder pista de nuevo contenido respecto a programación. 

Dicho esto, continuemos con el ejemplo:

Necesitamos definir 2 Clases u objetos. La que define cada uno de los NODOS, y la que define el procesamiento de los mismos.

Para definir los NODOS utilizaremos la Clase StringNode, y su definición seria la siguiente:

Clase StringNode 

Esta clase se define en un archivo separado cuyo nombre es StringNode.h, de esta manera seccionamos la definición de la clase con su implementación, como se puede observar únicamente cuenta con dos elementos privados, en los cuales se define el contendor del dato(elem) y  la referencia al próximo de la lista(next). Ademas declaramos la Clase StringLinkedList, como una clase AMIGA (friend), lo cual nos permitirá poder acceder libremente a los elementos (elem y next) desde esa otra clase para poder trabajar con ellos desde allí.

Ahora vayamos a la definición de la clase amiga, para esto generando otro archivo fuente por separado, llamado StringLinkedList.h:

Como podemos observar arriba, la clase define algunas rutinas importantes de nuestra linked list, la declaración tanto del constructor de la clase así como su respectivo destructor que nos ayudará a liberar la memoria. La funcion empty() , nos retorna un dato tipo bool, y nos servirá para verificar si nuestra lista esta vacía. La funcion front() , nos retorna el primer dato de la lista, después,  esta la funcion addFront() y removeFront(), que nos ayudaran a agregar mas elementos a la lista, o a borrar elementos existentes, respectivamente. Por último, se define un puntero llamado "head", del tipo de la clase NODO que hicimos anteriormente, lo cual nos ayudara a referenciar, donde esta el primer elemento(¿dónde empieza?) de nuestra linked list.

Después vamos crear un archivo fuente nuevo, que se llamará StringLinkedList.cpp, el cual contendrá la implementación de las funciones descritas en nuestra clase StringLinkedList:

Ahora en este archivo fuente, hace falta incluir nuestro archivo cabecera que contiene la declaración de la Clase StringLinkedList. En el constructor, únicamente inicializamos el puntero head, como nulo ya que aun no hay elementos en la lista. Luego, el destructor ~StringLinkedList() , contiene una rutina que va a iterar mientras la lista no este vacía, removiendo cada nodo de la linked list, y asegurando la liberación total de la memoria. En seguida la función empty(), únicamente nos retorna (falso o verdadero), si head es igual NULL, si es verdadero quiere decir que la lista esta vacía, en caso contrario, la lista contiene elementos. De forma similar, la función front(), nos retorna el primer elemento de la lista.

Pasemos a lo mas interesante, la función addfront() y removefront()..

addfront(): recibe un argumento de tipo string, y crea un objeto del tipo NODO (StringNode), y se inicializan sus elementos, de tal forma que el argumento "e", va a ser contenido en "elem", y el puntero next, se le asigna el valor de head, el cual ya dijimos que cuando no hay elementos en la lista este valor es NULL, y por lo tanto ahora head apunta hacia el NODO que acabamos de crear, dejándolo como el primer elemento de la lista.

removefront():En este caso, ocurre el evento contrario a addfront(), ahora instanciamos un puntero temporal del tipo NODO llamado "old" y a este le asignamos el valor de head, de esta manera podremos manipular la posicion de "head", para que sea el proximo elemento de la lista el que ahora ocupe, la primera posición de la lista( head= old->next). Por último, solo queda borrar el objeto temporal que creamos.

 Y listo!! ya solo queda probar si esta funcionado:

Para esto creamos un nuevo archivo fuente, cuyo nombre es main.cpp, y incluimos la librería que contiene la declaración de la clase de nuestra linked list, así como cualquier otra que nos sea de utilidad. Creamos un objeto tipo StringLinkedList, y por medio de la función addfront(), ingresamos elementos de prueba, siendo el último elemento ingresado, el que será el primero de nuestra lista. Ya solo nos queda por medio de la funcion front(), obtener el primer elemento de lista e imprimirlo en pantalla.

Con esto terminamos la explicación, como podrás darte cuenta una vez que conoces y estas familiarizado con los conceptos de la POO, es muy sencillo de implementar, aunque si bien es cierto la STL de C++ , ya contiene este tipo de estructura, es muy importante que sepas como funciona de esta manera podrás identificar rápidamente cuando algo funcione , que es lo que esta pasando internamente en el programa. Espero que haya sido de utilidad y prometo volver con mas en una próxima ocasión,  saludos a todos! :)