En un post anterior ya hablamos de estructuras de datos básicas, como los arrays o los objetos, entre otros temas. En el post actual vamos a hablar de estructuras algo más avanzadas, por lo que si aún no conoces las primeras (en verde), deberías volver atrás:
- 1️⃣🟩 Estructuras elementales (primitivos): Tipos de datos
- 2️⃣🟩 Estructuras básicas: arrays, objetos, conjuntos, mapas...
- 3️⃣🟨 Estructuras lineales: Pilas, colas y listas enlazadas.
- 4️⃣🟥 Estructuras no lineales: Grafos dirigidos y no dirigidos.
- 5️⃣🟥 Estructuras avanzadas: Árbol binario, Árbol B y tablas hash.
Las estructuras de datos que vamos a ver en este artículo son estructuras personalizadas debido a que las estructuras básicas anteriores se nos quedan cortas por alguna razón: no son eficientes para buscar, no pueden guardar toda la información, no son intuitivas para casos concretos, etc.
Estructuras lineales
Una vez conocemos las estructuras anteriores, probablemente necesitemos trabajar con estructuras más complejas o específicas. La mayoría de las estructuras que hemos visto hasta ahora son lineales, es decir, se pueden recorrer de forma secuencial.
Si seguimos dentro de estructuras lineales, podemos encontrarnos 4 tipos populares:
Vamos a verlo con ejemplos paso a paso:
🟪 Pila (Stack)
Las pilas son estructuras que se caracterizan en que sólo se pueden insertar elementos por un mismo extremo. Así pues, si insertas dos elementos (A, y luego B), tienes que sacar B antes para poder sacar A.
En Javascript, esto se puede hacer con una estructura .push() y .pop():
const array = [];
array.push("A"); // Mete A, Devuelve 1 (tamaño del array)
array.push("B"); // Mete B, Devuelve 2 (tamaño del array)
array.pop(); // Devuelve B
array.pop(); // Devuelve A
array.pop(); // Devuelve undefined
Casi siempre esto se suele denominar estructuras LIFO (Last input, first output): «El último que entra es el primero que sale».
🟪 Cola (Queue)
Las colas son estructuras que se caracterizan en que entran por un extremo y salen por el otro. Así pues, si insertas dos elementos (A, y luego B), primero sacar A y luego sacarás B.
En Javascript, esto se puede hacer con una estructura .push() y .shift():
const array = [];
array.push("A"); // Mete A, Devuelve 1 (tamaño del array)
array.push("B"); // Mete B, Devuelve 2 (tamaño del array)
array.shift(); // Devuelve A
array.shift(); // Devuelve B
array.shift(); // Devuelve undefined
Estas estructuras se denominan FIFO (First input, first output): «El primero que entra, es el primero que sale».
🟪 Cola doble (Deque)
Una modificación de las colas son las colas dobles. Estas son iguales que las colas simples, pero permiten tanto entrada como salida, por lo que es una estructura mucho más versátil:
En Javascript, se podría utilizar una estructura .push(), .pop() y .shift(), usando también otro llamado .unshift().
const array = [];
array.push("A"); // Mete A, Devuelve 1 (tamaño del array)
array.push("B"); // Mete B, Devuelve 2 (tamaño del array)
array.push("C"); // Mete C, Devuelve 3 (tamaño del array)
array.pop(); // Devuelve C
array.shift(); // Devuelve A
array.unshift("Z"); // Mete Z, Queda ["Z", "B"], Devuelve 2 (tamaño del array)
array.push("X"); // Mete X, Queda ["Z", "B", "X"], Devuelve 3 (tamaño del array)
🟪 Listas enlazadas (Linked list)
Por último, tenemos las listas enlazadas. Estas estructuras pueden tener múltiples implementaciones y pueden ser mucho más complejas, pero básicamente se basan en que los datos enlazan al dato siguiente, de forma que teniendo acceso a uno de los datos, podemos acceder al siguiente:
- Listas enlazadas: Acceso al siguiente elemento
- Listas doblemente enlazadas: Acceso al siguiente y al anterior
- Listas circulares: El último elemento enlaza al primer elemento
Estructuras de bajo nivel
Ten en cuenta que estas estructuras lineales no permiten acceder a elementos concretos directamente, como cuando hacemos un array[50]. Si necesitas ir al elemento 50, tendrás que recorrer 49 elementos antes. Esto hace que un
Por otro lado, si no necesitas acceso a elementos concretos, pero vas a realizar muchas inserciones y/o eliminaciones, con una estructura de este tipo gastarías menos recursos. No obstante, aquí ya estamos hilando muy fino.
Estructuras no lineales
A medida que avanzamos en el desarrollo, nos iremos encontrando situaciones en las que necesitamos estructuras de datos no lineales, es decir, estructuras donde los datos no están organizados de forma secuencial, sino que tienen diferentes caminos y formas de relacionarse.
Esto suele ser así porque los datos están almacenados de una forma adecuada para que sea fácil y rápido encontrarlos.
Este tipo de estructuras los datos se almacenan en elementos llamados nodos (las bolitas circulares) y se relacionan a través de líneas llamadas arcos o aristas.
Veamos que tipos existen:
🟥 Grafo dirigido
En los grafos dirigidos la principal características que es los nodos se enlazan en una dirección específica. Los nodos se relacionan a través de arcos que tienen una única dirección.
🟧 Grafo no dirigido
Por otro lado, los grafos no dirigidos tienen como principal característica que los nodos se enlazan mediante aristas, que tienen múltiples direcciones. De esta forma, nos podemos mover en cualquier dirección, no sólo una como en los anteriores.
Estas estructuras de datos son muy comunes en campos donde hay que relacionar grandes volúmenes de datos y necesitas que tengan un cierto orden y relación para facilitar ciertas cuestiones.
Estructuras avanzadas
Por último, tenemos estructuras avanzadas donde tienen características mucho más específicas y sirven para casos más avanzados de los que solemos hacer en un principio.
Por ejemplo, veamos tres casos bastante populares:
🟦 Árbol binario
Los árboles binarios (binary tree) son una estructura particular de las estructuras de tipo árbol. Estas estructuras se caracterizan en que son nodos con un valor numérico y que se dirigen hacia abajo. De cada nodo, pueden salir o colgar un número de nodos concreto. En el caso de los árboles binarios sólo pueden salir como máximo 2 nodos y como mínimo ninguno.
La regla principal de un árbol binario es que el nodo hijo izquierdo debe tener un valor más pequeño que su padre, y el nodo hijo derecho debe tener un valor más grande que su padre. Esto lo hace una estructura intuitiva para recorrer.
🟪 Árbol B
Por otro lado, los árboles B (B tree) son estructuras de tipo árbol más avanzadas, donde cada nodo no está limitado a tener sólo dos hijos máximo, sino que puede tener múltiples hijos.
La particularidad de los árboles B es que deben estar balanceados para ser eficientes. Esto significa que la estructura debe tener un nivel de profundidad similar para todos sus nodos, y si insertamos nuevos elementos, el árbol B debe rebalancearse para mantener su efectividad de búsqueda.
Los árboles B (y algunas variantes como árboles B+) son las estructuras de base que utilizan muchas bases de datos, debido al buen rendimiento de búsqueda que tienen.
⬛ Tabla hash
Las tablas hash son estructuras que utilizan un algoritmo para transformar una cadena de texto en un número entero que se pueda utilizar como índice en la tabla. De esta forma, se pueden mapear claves a índices y permitir un acceso rápido y eficiente a la información.
Las tablas hash se utilizan en una gran variedad de situaciones debido a su alta velocidad y lo eficiente y rápida que es la búsqueda de información.
