Estructuras de Datos

Introducción

Las estructuras de datos son las diferentes formas de organizar la información en la memoria de una computadora con el propósito de ser usada de manera efectiva.

Durante este documento se revisarán las estructuras de datos más comunes y fundamentales, ya que estas son la base de muchos algoritmos que resuelven problemas sumamente complejos de nuestro día a día (la base de datos de una tienda, encontrar el camino más corto hacia un lugar). Si bien estas estructuras de datos se pueden llegar a profundizar a un nivel alto de complejidad, aquí únicamente revisaremos sus componentes principales (de manera gráfica y su representación en código, empleando el lenguaje C++) y el uso básico de las mismas. Se espera que el lector tenga un conocimiento básico sobre apuntadores y el entendimiento básico del uso de la memoria dinámica en lenguaje C (uso de malloc, calloc, free, etc.).

Estructuras de datos:

1. Vector
2. Listas Enlazadas

• Simples
• Doblemente Ligadas

3. Pilas (Stack)

4. Filas (Queue)

5. Árboles

• Árboles de evaluación
• Árboles BST (Binary Search Trees)
• Árboles AVL
• Tablas de Hash
• Heap

Conclusiones

Referencias

VECTORES

Sin saberlo en nuestros primeros cursos de programación, la primera estructura de datos que aprendimos, o que generalmente se enseña, es el arreglo, ya sea unidimensional o multidimensional.

Así como los arreglos, un vector es una colección de datos colocados de manera contigua en la memoria. Sin embargo, para que un arreglo sea igual a un vector y poder realizar las mismas operaciones, tendrá que volverse un arreglo dinámico (arreglo inicializado con la función malloc). Tanto el arreglo dinámico como el vector pueden realizar inserciones de nuevo elementos, eliminación de datos e incrementar o decrementar el tamaño del vector/arreglo dinámico. En cambio, el arreglo común es completamente estático. A diferencia de los arreglos dinámicos el vector es una clase, lo cual facilita el uso de las operaciones mencionadas anteriormente.

Declaración del vector en C++

#include <vector> //librería de la clase vector
vector<tipo_dato> nombre_variable;
vector<tipo_dato> nombre_variable;

Las funciones de la clase vector son muy variadas pero las principales son las siguientes: (“Vector — C++ Reference”, n.d.)

• nombre_vector.size(); ←Devuelve el tamaño del vector.

• nombre_vector.resize(); ← Cambia el tamaño del vector.

• nombre_vector.insert();← Inserta un nuevo elemento.

• nombre_vector.erase(); ← Elimina un elemento de una posición determinada

• nombre_vector.empty(); ← Devuelve si esta vacío o no el vector

• nombre_vector.clear(); ← Elimina todos los elementos del vector

Representación en código de la clase Vector — C++

Como vimos los vectores son muy útiles para guardar datos en memoria continua. Sin embargo, aunque parece muy simple realizar una operación de inserción o eliminación en cualquier parte de la lista, si nos metemos a las entrañas del código veremos que el trabajo que realiza no es tan simple.

Si insertamos o eliminamos un elemento de la lista que se encuentra en medio tendríamos que recorrer todos los elementos que le suceden para dejar un espacio si es insertado u ocupar el espacio del elemento eliminado. En el peor de los casos si insertamos el elemento al principio del vector, se tendría que recorrer cada elemento una posición a la derecha para dejar el espacio disponible.

Ejemplo de inserción

Esto puede se volverá aún más ineficiente en cuanto el número de elemento en el vector incremente. No será lo mismo recorrer 10 elementos a recorrer miles de elementos.

La solución a este problema se encuentra en las listas ligadas que veremos a continuación.

LISTAS LIGADAS

Las listas ligadas no son mas que datos almacenados en memoria discontinua que están unidos entre si median apuntadores a la dirección de memoria de donde se encuentra el dato.

Cada elemento de la lista es conocido como nodo, conformado el dato del elemento y el apuntador al siguiente nodo, comúnmente llamado next.

Existen tres tipos de listas ligadas: Simples, Dobles y Circulares

Estructura de una lista ligada simple

• Nodo: elemento de la lista, el primer elemento es conocido como head. El último nodo siempre apuntara a NULL para saber que la lista ha terminado.
• Valor
• Apuntador al siguiente nodo (next)

Representación visual

Representación en código

Clase Link o Nodo — C++

Clase Lista — C++

La ventaja más grande de las listas ligadas sobre un arreglo son las operaciones de inserción y eliminación de datos (en este caso nodos). Si bien un vector tiene que recorrer todos los elementos contenidos para hacer espacio o quitarlo, en una lista ligada es mucho más rápido y simple.

Pasos para insertar un nodo después de la posición requerida

1. Se cuenta hasta la posición donde el nodo será insertado después de esa posición.

2. El apuntador next del nuevo nodo apuntaría a la misma dirección que el nodo que se encuentra en la posición del contador.

3. El next del nodo de la posición actual apuntará al nuevo nodo.

Código para insertar un elemento después de la posición — C++

Una gran desventaja de las listas ligadas es no poder acceder directamente a los elementos que le contienen. En un arreglo podemos utilizar el índice del elemento y poder obtenerlo directamente. Por el contrario, en una lista ligada se debe recorrer toda desde principio hasta encontrar la posición del elemento deseado.

Además de eso las listas ligadas simples solo pueden ser recorridas hacia una dirección, que es a donde estaría apuntando el siguiente nodo. Sin, embargo las listas ligadas dobles resuelven este problema añadiendo un apuntador al anterior nodo.

Estructura de una lista ligada doble

• Nodo: elemento de la lista, el primer elemento es conocido como head, el último nodo se le conoce como tail. El último nodo y el primero siempre apuntaran a NULL para saber que la lista ha terminado en ambos sentidos.
• Valor
• Apuntador al siguiente nodo (next)
• Apuntador al nodo anterior (prev)

Representación visual

Representación en código

Clase DLink o DNodo — C++

Si bien el proceso de inserción de un elemento es prácticamente igual a la lista enlazada simple, este puede ser un poco enredoso por los apuntadores prev y next.

Pasos para insertar un nodo después de la posición requerida

1. Se cuenta hasta la posición donde el nodo será insertado después de esa posición.

2. El apuntador next del nuevo nodo apuntará al next del nodo de la posición actual.

3. El next del nodo de la posición actual apuntará al nuevo nodo.

4. El previo del nuevo nodo apuntaría al mismo previo del nodo siguiente del nuevo nodo. El nodo con dirección 211 es el siguientes del nuevo nodo con dirección 201, el precio del nodo 211 seria el nodo 210 como se muestra en la imagen.

5. Y finalmente el previo del nodo siguiente del nuevo nodo (nodo 211) apuntaría al nuevo nodo. Quien es el siguiente del previo del nuevo nodo (siguiente del nodo 210).

Código para insertar un elemento después de la posición para una lista doblemente ligada — C++

PILAS

Las pilas (stack) como el nombre lo indica, es una estructura de datos lineal en la que se apila la información como si apiláramos unos platos unos sobre otros.

Figura 1. Pilas en la vida real y pilas en codigo

Al igual que con los platos el último en apilar es el primero en salir, este orden de operaciones es conocido como LIFO por sus siglas en ingles (Last In First Out). Esta forma solo podemos acceder al elemento que se encuentra arriba de la pila (top) y podemos acceder a los elementos de abajo quitando uno a uno los de encima.

Declaración usando la librería list

Funciones de una Pila

• s1.pop_front(): Sacar el elemento de arriba de la pila.

• s1.front(): Regresa el valor del elemento de arriba de la pila.

• s1.push_front(): Ingresa un valor a la pila.

Una pila tiene como limite el maximo de elementos que pueden ser insertados. En la imagen de ejemplo el maximo serian 5 elementos. Si se quisiera insertar un elemento más, este arrojaría como error Overflow().

Si pudiéramos ver el interior de la clase list y ver como esta construida la pila, sería aproximadamente así:

USOS DE UNA PILA

Aunque parezca muy simple la estructura de una pila, es realmente sorprendente la cantidad de usos que puede ofrecer. Estos solo son algunos de ellos:

• Juegos de cartas.

• Algoritmos de búsqueda de profundidad para la investigación de inteligencia artificial (para resolver laberintos).

• Acción de hacer y deshacer en un programa (el famoso Ctrl+Z).

• La administración de procesos en un Sistema Operativo

Estos y muchos mas ejemplos hay sobre porque se debería implementar una pila.

FILAS

Las filas son muy parecidas a las pilas, sin embargo, estas son iguales a las filas de nuestro día a día, las que hacemos para formarnos mientras esperamos nuestro turno.

Figura 1. Filas en la vida real y en código

Al igual que en una fila para el cine, el primero en entrar a la fila es el primero en salir de esta, el orden de operaciones es conocido como FIFO por sus siglas en inglés (First In First Out). A diferencia de la pila, los elementos se acomodan uno tras otro y no encima de otros. Así el ultimo en entrar se encontraría al final de la fila (Back) y el primero en salir al frente de la fila (front).

Declaración usando la librería list

Funciones de una Fila

• s1.pop_front(): Sacar el elemento de en frente de la fila. También se le conoce como Dequeue().

• s1.push_back(): También conocido como Enqueue(). Ingresa un elemento al final de la fila.

• s1.front(): Devuelve el valor que se encuentra al frente de la fila.

Así que como las pilas, se tiene un máximo de elementos a insertar, si se intentará insertar un elemento en una fila llena esta devolvería como error Overflow().

Si viéramos el código de la clase lista para una fila, sería muy similar a esto.

USOS DE LAS FILAS

Al igual que las pilas, por muy simple que parezca su estructura es variado y necesario los diversos usos que se le pueden dar.

• Tiempo de espera por clientes en un Call Center.

• Impresión de líneas de una impresora.

• Manejo de recursos compartidos.

ARBOLES

Los árboles por su composición se asemejan a las listas ligadas, están conformados por nodos en los cuales contienen apuntadores al siguiente nodo. A diferencia de estas, los árboles no son una estructura de datos lineal, sus apuntadores llevan a diferentes caminos hacia una dirección. Se podría decir que la definición de un árbol es recursiva ya que los árboles están conformados por más arboles (subárboles), que a su vez están conformados por arboles (más subárboles). Así como los árboles de la vida real o un árbol familiar, la estructura de un árbol es jerárquica, es decir, esta comienza por una raíz o padre el cual tiene 0, 1 o más hijos, que estos a su vez tienen hijos. Existen arboles de múltiples hijos, pero durante este texto revisaremos únicamente los arboles que tiene de 0 a 2 hijos.

Estructura de un árbol

• Nodo raíz
• Apuntador a su rama izquierda (left)
• Apuntador a su rama derecha (right)

Representación gráfica de un árbol

Representación en código — C++

Características de un árbol

• Niveles: Cantidad de niveles del árbol.

• Balanceado: Se dice que un árbol esta balanceado si su diferencia entre niveles se encuentra en el rango de ±1. Si sus subárboles no está balanceados se dice que el árbol general tampoco lo está. Este factor se obtiene restando la suma de niveles de la rama izquierda con la suma de niveles de la rama derecha.

• Lleno: Un árbol se dice que esta lleno si tiene 0 o 2 hijos en cada árbol y subárbol.

• Perfecto: Se dice que es perfecto si esta lleno y tiene todas sus hojas al mismo nivel.

• Degenerado: Se dice que un árbol esta degenerado si esta se comporta como una lista ligada.

La forma para recorrer un árbol no es tan simple como de una lista enlazada, debe establecerse un orden para que sea entendible su recorrido. Existen cuatro tipos de recorridos de árboles, en orden, pre-orden, post-orden y por niveles.

• En orden: Se empieza a recorrer todo el lado izquierdo, se visita (imprime, muestra) el valor del nodo y después se recorre todo el lado derecho.

• Pre-orden: Se visita el nodo, luego se recorre el lado izquierdo y al final todo el lado derecho.

• Pos-orden: Se recorre primero todo el lado izquierdo, luego todo el lado derecho y al final se visita el nodo.

• Por niveles: se recorre cada nivel de izquierda a derecha y de arriba hacia abajo.

Hay diversos tipos de árboles y representaciones de estos, en este trabajo revisaremos únicamente los árboles de evaluación (EVAL tree), los árboles de búsqueda binaria (BST) y los árboles que se auto balancean (AVL).

ARBOLES DE EVALUACION

Los árboles de evaluación son aquellos que en sus nodos internos poseen operadores aritméticos y en los nodos hoja los operandos.

Código para la evaluación de un EVAL tree — C++

ARBOLES DE BUSQUEDA BINARIA

Los ejemplos usados en este texto para representar un árbol han sido basados en los árboles binarios, siendo uno de los árboles más usados. La característica de estos es que no pueden tener más de 2 hijos y la inserción de un nuevo nodo se realiza dependiendo de su valor, siendo el siguiente patrón: Los nodos con valor más pequeño que la raíz (del árbol o subárbol) serán insertados a l izquierda, los nodos más grandes que la raíz serán insertados a la derecha.

Figura 1. Árbol de búsqueda binaria.

Este tipo de árbol representa una forma más eficiente de ordenamiento y de búsqueda a diferencia de un arreglo. Ya que en el arreglo a pesar de que también se puede llevar a cabo la búsqueda binaria, este tendrá que estar previamente ordenado para realizarla. Mientras con el árbol BST este conforme se insertan los elementos se va ordenando y una vez se hace un recorrido En Orden este nos dará todos los valores ordenados sin mayor problema, y por si misma estructura nos permite hacer una búsqueda binaria fácilmente. El recorrido en orden la Figura 1 sería el siguiente: 1 ,5, 9, 10, 15, 20, 21, 25, 26, 27, 29, 30,33, 35, 36.

Código para agregar nodos a un árbol BST — C++

Código para buscar un valor del árbol BST — C++

ARBOLES AVL

Un problema que tienen los árboles BST es que si se insertan demasiados elementos en una rama este podría convertirse en un árbol degenerado cuya complejidad de búsqueda será igual a la de una lista enlazada; o también podría convertirse en un árbol incompleto de una rama con gran profundidad aumentando la complejidad del tiempo de búsqueda. Este problema es debido al desbalance del árbol y es solucionado por los árboles AVL.

Figura 2. Árbol degenerado (factor de balance -3) y desbalanceado (factor de balance -2)

El árbol AVL corrige el desbalance de un árbol una vez es detectado, realizando rotaciones sencillas o dobles hacia un lado o el otro dependiendo de qué rama se encuentra desbalanceada.

Figura 3. Árbol binario desbalanceado.

Como vimos un árbol está desbalanceado si su factor de balance se encuentra fuera del rango ±1 (menor a -1 y mayor a 1). En la Figura 3 vemos que la rama izquierda del nodo 10 es donde se encuentra el desbalance, se aplicará una rotación hacia la rama derecha, teniendo como hijo izquierdo de nodo raíz al nodo 8, el nodo 10 pasará a ser su hijo derecho. Este tipo de rotación es una rotación sencilla.

Ahora su factor es 0 significando que se encuentra balanceado.

Las rotaciones dobles son más complejas de visualizar y de hacer, ya que hay reflexionar dónde colocar los nodos rotados y a qué dirección.

Figura 4. Árbol binario desbalanceado que requiere doble rotación

El árbol de la Figura 4 requiere una rotación doble ya que desde el nodo raíz, el desbalance se carga hacia su rama derecha y el desbalance se extiende a la rama izquierda del nodo 20. Para esto primero se moverá el nodo 9 hacia abajo como nuevo hijo del nodo 18 y el nodo 12 será el hijo derecho del nodo 9.

Como vemos una rotación sencilla no es suficiente debido a que el desbalance persiste en el nodo 9 y 20. Para eso volvemos a rotar al lado contrario de la primera rotación, teniendo como nuevo nodo raíz al nodo 18.

TABLAS DE HASH

Después de revisar las anteriores estructuras de datos hemos visto cómo cada una de estas tiene un orden de complejidad distinto para acceder a los datos. La mayoría de las estructuras que vimos tienen un orden de complejidad O(n), las listas enlazadas simples y dobles, las pilas y las filas; los árboles tienen orden de complejidad O(log(n)) por su estructura. Sin embargo los vectores y arreglos tienen la peculiaridad de tener un orden de complejidad inmejorable, siendo O(1) un factor constante, debido a que se puede acceder a los elementos directamente mediante su índice.

Figura 1. Tabla de complejidad en tiempo y espacio (“Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell”, n.d.)

Figura 2. Ejemplo de acceso directo a los valores de un arreglo dinámico

Pero qué sucede si requerimos realizar una base de datos con la información de todos los estudiantes de una universidad. Si tomamos de ejemplo al ITESM, esta universidad tiene aproximadamente más de 90,000 estudiantes activos cuyos ID son similares a este ejemplo “A02713209”. Si deseamos guardar cada matrícula de los estudiantes en un arreglo dinámico, ese sería descomunalmente grande, la inserción y ordenamiento como hemos visto sería muy compleja por su tamaño. Sin embargo aún buscamos ese orden de complejidad O(1) de los arreglos, aquí es donde entran en juego las tablas de Hash.

Las tablas de Hash son una estructura de datos en la cual se utiliza una función de Hash para determinar el índice de un elemento dependiendo del tamaño de la lista y el valor del ID. Donde dichos datos no necesariamente están ordenados, pero aparentan estarlo por la llave que les asigna un índice de almacenamiento.

Representación Gráfica de la tabla de Hash

Representación en código — C++

Si quisiéramos insertar el primer elemento de la Figura 3 aplicaríamos la función de Hash para obtener su índice correspondiente: 22 mod 10 = 2. Nuestra llave para el elemento 22 será el 2.

Aplicamos lo mismo para el siguiente elemento: 4 mod 10 = 4. La llave para este elemento es 4.

No obstante, al aplicar el mismo procedimiento para el elemento siguiente, el número 72. Obtenemos que la llave es 2, cuyo espacio ya es ocupado por el 22. El manejo de colisiones en una tabla de Hash es uno de los mayores retos de este tipo de estructura. La solución más simple a este inconveniente sería buscar el siguiente espacio disponible e insertar el elemento en dicho lugar. A este proceso se le conoce como sondeo linear.

72 mod 10 = 2

42 mod 10 = 2

76 mod 10 = 6

77 mod 10 = 7

12 mod 10 = 2

Representación en código del sondeo lineal — C++

Esta solución, aunque simple a la larga, se vuelve costosa en cuanto a tiempo de búsqueda al momento de insertar más elementos que colisionan entre sí. Esto se puede apreciar al insertar el ultimo elemento, el numero 12, este colisiona con el numero 22 y al no haber espacio en la lista se coloca al final de esta. Entre más elementos se inserten la complejidad dejará de ser O(1) y se tornará O(n), siendo tan poco efectiva como las anteriores estructuras. Pero esta no es la única forma de manejar las colisiones. Otra forma es el manejo de “buckets” insertan los elementos de un mismo índice en el mismo lugar como si fuera una cubeta (como el nombre sugiere). Así si retomamos el ejemplo anterior, la tabla quedaría de la siguiente forma una vez insertados todos los elementos.

El número de operaciones se reduce mucho más al buscar los elementos que colisionan, más nos topamos con el problema inicial del tamaño máximo que tendrá el bucket para almacenar los elementos que colisionan. Otra solución es mezclar los arboles AVL con la lista, de la siguiente forma:

Se balancea el árbol conforme cada inserción minimizando la cantidad de operaciones para obtener un valor que colisiona.

Así muchas soluciones existen para manejar las colisiones, pero lo mas optimo es tener una buena función de hash que impida la agrupación de elementos y distribuirlos mejor. El algoritmo SDBM hace un buen trabajo insertando y distribuyendo los elementos minimizando las colisiones: (“Hash Functions”, n.d.)

Función de hash SDBM: hash(i) = hash(i — 1) * 65599 + str[i];

Algoritmo optimizado:

HEAP

La estructura de datos Heap es muy parecida a un árbol binario, la cual no debe confundirse con la alocación en la memoria dinámica llamada de la misma forma. Este se utiliza para filas de prioridad, es decir que, dependiendo de nuestro criterio, unos valores tendrán mayor prioridad que otros.

Representación gráfica del Heap

Figura 1 y 2. Heap de prioridad al números mayores y Heap de prioridad a números menores

Representación en código — C++

El Heap tiene dos propiedades muy importantes: propiedad de forma y orden.

• Propiedad de forma: Establece que el Heap será siempre un árbol completo. Para que esto se cumpla la inserción de elementos se realizará por niveles y de izquierda a derecha. Gracias a esta propiedad, la representación del Heap puede ser fácilmente trasladada de un árbol a un arreglo.

• Propiedad de orden: Dependiendo del criterio que se establezca este se deberá cumplir conforme se inserten nuevos elementos. Es decir, si la prioridad son los elementos menores, entonces los hijos del nodo raíz deberán ser mayores. En caso contrario, los hijos tendrán que ser menores al padre si la prioridad se tiene en los números de mayor valor. Este ejemplo se puede revisar en las Figuras 1 y 2, donde el primer Heap los valores mayores tienen prioridad y el segundo Heap es todo lo contrario.

Estas propiedades se pueden romper conforme se remueven o insertar nuevos elementos al Heap. En dado caso, se deberá realizar las operaciones reheap-up o reaheap-down según corresponda.

Método de inserción

La inserción de nuevos elementos en un Heap es muy sencilla, se podría decir que es una inserción por niveles de izquierda a derecha. Este tipo de inserción respeta la propiedad de forma del Heap para que este siempre sea un árbol completo.

De momento todo está en orden y las 2 propiedades se cumplen a la perfección. Pero una vez se inserte el elemento 2, la propiedad de orden será rota. En este caso se deberá hacer un Reheap-up para mover el 2 su lugar correcto.

REHEAP-UP

1. Comparamos si el nodo insertado cumple con el criterio establecido, en este caso que los hijos sean mayores que el padre. El elemento 2 (el hijo) es menor que el elemento 10 (el padre), así que realizamos un swap entre estos.

2. Repetimos el primer paso de manera recursiva.

La ventaja de representar el Heap como un arreglo es facilitar el swap entre padres e hijos para las operaciones Reheap-up y Reheap-down. Mientras que con el árbol se deberían cambiar muchos apuntadores de un lugar a otro, con el arreglo solo se necesitaría una variable temporal y hacer el swap básico. Lo único que no es muy intuitivo es determinar cuál es el padre o hijo de cada valor. Para esto usamos unas simples operaciones para obtener su posición:

• Raíz: El índice [0] siempre será la raíz del Heap
• Padre = (pos_actual-1)/2
• Hijo izquierdo = (2*pos_actual)+1
• Hijo derecho = (2*pos_actual)+2

Código de acceso a Nodo Padre — C++

Código de acceso a Nodos hijo izquierdo y derecho — C++

Código para insertar elementos al Heap — C++

Método de eliminación

Al ser una estructura por prioridad, la raíz es el único elemento que se remueve al sacar los elementos del Heap.

1. Eliminamos el Nodo raíz y lo reemplazamos con el último nodo agregado, en este caso el Nodo de la posición 8 con valor 10.

2. Aplicamos Reheap-down de manera recursiva para colocar los valores en su lugar adecuado comparando los valores.

Código para eliminar elementos del Heap — C++

Código para Reheap-down — C++

COCLUSIONES

Las estructuras de datos vistas en este documento son la base esencial de muchas otras estructuras de datos existentes. Aunque algunas parezcan muy simples y de poca utilidad realmente son las herramientas para implementar otras. Por ejemplo, podrías pensar que los arreglos son completamente innecesarios una vez vistas el resto de las estructuras, pero olvidamos que estos arreglos (dinámicos o no) son la fundación de algunas de estas estructuras, ejemplo: la estructura Heap, tablas de Hash, Fila, Pila. Así como las listas son la base de los árboles y los árboles de los grafos (estructura no cubierta en este documento).

De esta forma ninguna estructura de datos es despreciable, se tiene que escoger correctamente cuál usar para diferentes problemas e implementaciones, debido a que cada una consume diferente tiempo y espacio. Por ejemplo, para una base de datos de una tienda se podrían implementar arboles AVL, tablas de Hash o arreglos dinámicos, más dependiendo del tamaño de la base de datos y la rapidez que requerimos para acceder a sus elementos escogeremos una u otra (en este caso las tablas de Hash son comente utilizadas para esta aplicación). Otro ejemplo sería encontrar el camino para resolver un laberinto, las estructuras de datos Fila y Pila son excelentes para este problema, la Fila nos permitiría encontrar el mejor camino (por su recorrido por niveles) y la Pila no permite encontrar un solo camino (recorrido por profundidad). Las listas enlazadas tienen una aplicación útil para hacer un menú sencillo y acceder a ciertas facilidades, ejemplo si quisiéramos hacer un apuntador de laser que tuviera un menú al cual podemos acceder presionando un botón, cada de que lo presionamos podremos cambiar de color, dependiendo del desarrollador podría optar por una lista doble o circular.

Así, muchos ejemplos existen para cada estructura de datos, uno más complejo que el otro, pero sin restarles importancia, ya que cada una es tan útil en su ámbito como las otras. Ahora nos queda por probar aún más estructuras y usos para éstas, ya que así como estructuras hay muchas, también hay infinidad de problemas que requieren resolverse con las mismas.

REFERENCIAS

1. Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell. Retrieved 10 November 2020, from https://www.bigocheatsheet.com/
2. Vector — C++ Reference. Retrieved 10 November 2020, from http://www.cplusplus.com/reference/vector/vector/
3. Hash Functions. Retrieved 10 November 2020, from http://www.cse.yorku.ca/~oz/hash.html