7 estructuras de datos en 10 minutos

Intro

Las estructuras de datos, son muy importantes al momento de resolver algoritmos. 

Y ambos son clave para pasar una entrevista de programación. 

El detalle es que al consultar libros sobre estructuras de datos y/o algoritmos, muchas personas se sienten agobiadas:

• Ya que resultan siendo muy teóricos y densos.
• Y si no eres tan fanático de las matemáticas, te podrían asustar un poco.

La buena noticia es que:

Una vez que entiendes las estructuras de datos, verás que en realidad no son tan complicadas.

Hoy revisaremos las estructuras de datos más importantes:

• Usando el menor número posible de tecnicismos, 
• y buscando simplificarlas, sobre todo para aquellos que están comenzando.

¡Empecemos!

¿Qué son las Estructuras de Datos?

Primero veamos qué es una estructura de datos. 

Imagina que tienes un solo dato, como el precio de una acción. 

Ese precio por sí solo no significa mucho.

Pero si lo juntamos con muchos más precios de acciones, digamos con datos de todo un día, entonces se vuelve más significativo.

Cuando agrupamos varios elementos de datos, hablamos de datos compuestos. 

Tenemos que almacenar estos datos en algún tipo de estructura de datos, y elegir la correcta es muy importante.

Ninguna estructura de datos es perfecta; todas tienen sus ventajas y desventajas para diferentes tareas.

La forma en que medimos qué tan buena es una estructura de datos para hacer algo específico, como agregar un nuevo elemento, obtener un elemento, ordenar o buscar, se llama notación Big O. 

Esta notación permite expresar cómo crece el tiempo de una operación.

Por ejemplo, si tienes 10 elementos y luego agregas un millón más, ¿cuánto más tiempo tomará cada operación?

Linked List

Bien, hablemos de la primera estructura de datos, que es la lista enlazada (linked list). 

La unidad básica de la lista enlazada es un nodo, que contiene un valor y un puntero. 

• El valor puede ser algo tan simple como un número, por ejemplo, 17,
• y el puntero simplemente te conecta al siguiente nodo en la cadena, de ahí la parte "enlazada" de lista enlazada. 

El primer nodo de la lista se conoce como la cabeza (head), mientras que el último, que no tiene un puntero hacia otro nodo, se conoce como la cola (tail). 

Veamos las ventajas y desventajas de la lista enlazada.

• La lista enlazada es muy buena para agregar y eliminar nodos, ya que solo necesitamos cambiar hacia dónde apunta el puntero.
• Sin embargo, no es tan eficiente para recuperar nodos, incluso cuando conocemos el índice, o para buscar, porque cada nodo sólo "conoce" al nodo siguiente.

Array

Nuestra segunda estructura de datos es el arreglo o array. 

Es probable que ya estés familiarizado con los arreglos, porque son muy comunes en todos los lenguajes de programación.

Un arreglo es, literalmente, un bloque continuo de celdas en la memoria del ordenador.

Al llevar un registro de su ubicación en la memoria, puede calcular instantáneamente la ubicación de cualquier elemento dentro de él. 

Por ejemplo, digamos que:

• La ubicación del primer elemento es 1000,
• si queremos obtener el elemento en el índice número 5,
• simplemente sumamos 5 a 1000, obtenemos 1005,
• y luego podemos extraer ese valor directamente. 

Como resultado de esto, te puedes imaginar que los arrays son muy buenos para recuperar elementos.

Sin embargo, si tu arreglo crece mucho en tamaño, eventualmente empezará a "chocar" con otros datos en memoria.

Por esta razón, agregar elementos no siempre es eficiente en los arreglos, porque podríamos tener que mover todo el array a un nuevo lugar en la memoria para que quepa. 

• Afortunadamente, esto sucede de manera automática en lenguajes de alto nivel como JavaScript y Python,
• pero en lenguajes de bajo nivel tienes que declarar el tamaño de tu arreglo por adelantado.

Hash Table

Bien, la tercera estructura de datos, y esta es súper importante, se conoce como tabla hash (hash table). 

Probablemente la reconozcas porque es un objeto en JavaScript o un diccionario en Python. 

De hecho, "diccionario" es una muy buena palabra para explicar cómo funciona una hash table.

Básicamente le das una palabra o clave (key), y te devuelve la definición o valor correspondiente.

Por detrás:

• Una hash table funciona de manera similar a un arreglo, pero tenemos claves en lugar de posiciones contiguas de memoria.
• La clave se pasa a través de una función llamada función hash, que genera una ubicación en memoria. 
• Estas ubicaciones en memoria pueden estar en cualquier parte, por lo que no tiene el mismo problema de crecimiento que tienen los arrays.
• Sin embargo, surge otro problema: dependiendo del algoritmo de hash que se utilice, dos claves podrían terminar generando la misma ubicación en memoria. 
• Esto se conoce como una colisión, y existen diferentes maneras de resolver eso, pero, nuevamente, todo esto sucede "tras bambalinas".

Por tanto: 

• Las tablas hash son muy eficientes tanto para recuperar como para agregar elementos.
• Pero hay que tener cuidado con las colisiones.

Stack & Queue

Como cuarta estructura de datos, tenemos en realidad un par, que son la pila (stack) y la cola (queue). 

Son bastante similares y ambas están construidas sobre arreglos, con algunas características adicionales.

La pila es una estructura de datos LIFO, por sus siglas en inglés:

• Last In, First Out
• y significa: "último en entrar, primero en salir". 

Piensa en una pila de bandejas, o una pila de platos, en un restaurante:

La última bandeja que colocas en la parte superior, es la primera que debes retirar.

• Cuando agregamos un elemento en la parte superior, se llama "push" (empujar),
• y retiramos elementos con "pop" (sacar).

Para que lo puedas recordar fácilmente, recuerda que:

Cada lenguaje de programación realiza un seguimiento de las funciones que se han llamado, mediante una pila de llamadas (o call stack). 

Las pilas también son muy importantes para un algoritmo llamado búsqueda en profundidad (depth-first search), que te encontrarás con frecuencia.

Por otro lado, la cola (queue) es FIFO:

• First In, First Out
• y significa: "primero en entrar, primero en salir".

Imagina una cola para abordar un avión en el aeropuerto.

• Agregar un elemento al final se llama "encolar" (queuing),
• y retirarlo del frente se llama "desencolar" (dequeuing). 

Las colas se utilizan en un algoritmo muy importante llamado búsqueda en amplitud (breadth-first search). 

En general, las pilas y las colas son muy eficientes, pero tienen casos de uso limitados en comparación con otras estructuras de datos. 

Graphs & Trees

Y finalmente, hablaremos de los grafos y los árboles.

Este tema es tan grande que existe todo un campo de la informática llamado teoría de grafos.

Un grafo es similar a una lista enlazada, donde tienes nodos que apuntan a otros nodos, pero en este caso, los punteros se llaman aristas (edges). 

Las aristas también pueden tener pesos o números asignados. 

Imagina dos ciudades, Lima y Trujillo. 

• El camino entre ellas es la arista, 
• y la longitud del camino podría ser el peso de esa arista.

Relaciones complicadas, como las redes sociales, también se almacenan como grafos. 

Hay un tipo especial de grafo jerárquico llamado árbol (tree), en el que los datos se expanden en una sola dirección. 

Podemos usar estos árboles para representar muchas cosas, como un árbol genealógico o incluso un árbol HTML con elementos anidados.

Hay un tipo de árbol aún más específico llamado árbol de búsqueda binaria (binary search tree). 

Este árbol tiene reglas muy específicas, y estas reglas nos permiten realizar búsquedas de manera muy eficiente:

Las reglas son las siguientes: 

• Cada nodo puede tener máximo 2 hijos, izquierdo y derecho. 
• El hijo izquierdo debe ser menor que el nodo, y el hijo derecho debe ser mayor. 

Con estas reglas establecidas, podemos recorrer nuestro árbol y siempre tener una idea de dónde se encuentra un elemento. 

Así que, si tuviera un 5 en la parte superior y estuviera buscando un 7, sabría que está ya sea a la derecha o que no está en mi árbol en absoluto.

Desafortunadamente, el binary search tree (BST) tampoco es la estructura de datos perfecta:

• Si agregas elementos en un orden inusual, puede volverse muy desbalanceado o unidireccional,
• y pierdes muchas de las ventajas que obtienes con la optimización de búsqueda. 

Existen árboles auto-balanceados:

• Red-Black Tree
• AVL Tree
• B-tree

Pero eso se adentra en estructuras de datos más avanzadas, así que lo dejaremos hasta aquí por hoy.

Aprende viendo

¡También puedes ver un video explicativo, con animaciones, sobre estructuras de datos!

Conclusión

Muy bien! Te felicito por haber llegado hasta el final.

Estas estructuras de datos te proporcionarán una base excelente al momento de resolver algoritmos.

 

Si estás empezando en este mundo de la programación, te invito a darle una mirada a mis cursos.

Puedes empezar con JavaScript, o si ya tienes experiencia puedes seguir mis cursos backend o de desarrollo móvil.

Si tienes dudas, también puedes escribirme, y te ayudaré gustoso.

¡Espero que te haya gustado aprender sobre estructuras de datos!

Gracias, y nos vemos en una próxima ocasión.

# javascript # python