El mapa: 16 conceptos en seis grupos

Un mapa de metro: primero ves todas las líneas, luego viajas estación por estación.

Arriba hay tres ideas básicas: Data Structure, Trade-off y Big-O. Debajo, seis grupos: las formas de crecimiento de Big-O, el array, el hash map y el set, las estructuras con orden (stack y queue), las estructuras con forma (tree y graph) y, por último, cómo elegir entre ellas en la práctica.

Cómo leer este curso

Un pasaporte: los mismos campos para todos, así es fácil compararlos.

Cada concepto recibe el mismo tratamiento: su nombre en inglés (el término que encontrarás en la documentación y en las entrevistas), una imagen de la vida diaria, un diagrama y una ficha: qué es, cómo funciona, un ejemplo, el coste y cómo se relaciona con otras estructuras. La única regla de este curso: no existe la mejor estructura — solo la que encaja con la operación que más haces.

Data Structure — organizar los datos para las operaciones que más haces

Una caja de herramientas ordenada con ranuras etiquetadas frente a un montón de herramientas en un saco — las mismas herramientas, pero una te deja tomar la correcta al instante y la otra te obliga a hurgar cada vez.

Una data structure es una manera de disponer los datos en memoria. Distintas disposiciones hacen rápidas distintas operaciones: una es estupenda para buscar cosas por nombre, otra para mantener el orden, otra para tomar siempre el elemento más reciente. Todo el juego consiste en hacer coincidir la estructura con lo que harás más a menudo.

La misma tarea puede ser trivial o casi imposible según cómo se guarden los datos. Encontrar una palabra en un diccionario ordenado lleva segundos; encontrarla entre esas mismas palabras volcadas en orden aleatorio podría llevar todo el día. Así que una cantidad sorprendente de «haz esto rápido» es en realidad «guárdalo con la forma correcta». La estructura es la decisión.

Trade-off — toda estructura renuncia a algo

Un auto deportivo y un camión de mudanzas son ambos vehículos — no preguntas cuál es mejor, preguntas mejor para qué.

Ninguna estructura es la mejor en todo. Una ofrece búsqueda instantánea pero ningún orden; otra mantiene el orden pero es lenta de buscar; otra es rápida para añadir pero lenta para encontrar dentro. Eso es el trade-off: la fortaleza en una operación se paga con debilidad en otra. No hay almuerzo gratis — tu trabajo es elegir la compensación que encaja con tu uso.

Big-O notation — crecimiento, no segundos

Preguntar no cuánto tarda una entrega, sino cómo cambia el tiempo total a medida que la ruta pasa de diez paradas a diez mil — la forma del crecimiento, no la lectura de un cronómetro.

La notación Big-O describe cómo crece el coste de una operación a medida que crece la cantidad de datos, llamada n. Ignora los milisegundos exactos y la computadora concreta, y captura la forma: ¿duplicar los datos duplica el trabajo, lo cuadruplica, o apenas lo cambia? Esa forma es lo que decide si algo se mantiene rápido a escala, así que Big-O es cómo los ingenieros comparan enfoques sin llegar a ejecutarlos.

Complexity classes — formas de excelente a pésima

Cuatro maneras en que una tarea escala: una se queda en un solo paso sin importar el montón, una crece con el montón, una explota como el montón al cuadrado, y una apenas crece aunque el montón lo haga.

Unas pocas formas cubren la mayoría del código:

• O(1) — constante: el mismo tiempo sin importar el tamaño (tomar un elemento por index).
• O(log n) — logarítmica: apenas crece aunque los datos se disparen (reducir la búsqueda a la mitad en cada paso).
• O(n) — lineal: crece al ritmo de los datos (recorrer una lista).
• O(n²) — cuadrática: explota (comparar cada elemento con todos los demás). La clásica «bien en pruebas, muere en producción».

Con diez elementos, cualquier estructura se siente instantánea — las diferencias no se notan. Big-O trata de lo que pasa cuando n se hace grande. Por eso las cosas se vuelven lentas «de repente» en producción: la mala forma siempre estuvo ahí, solo que oculta hasta que los datos crecieron.

Array — una secuencia ordenada y numerada

Una fila de casilleros numerados: los elementos están en orden y cada uno tiene una posición — casillero 0, casillero 1, casillero 2 — así que puedes ir directo a cualquiera por su número.

Un array (o list) guarda los elementos en orden, cada uno en una posición numerada llamada index, que empieza en 0. Como los elementos están en una disposición conocida y contigua, saltar a cualquier posición por su index es instantáneo — O(1). Los arrays son la opción por defecto para «un montón de cosas en orden», y el acceso directo por posición es su superpoder.

Hay un precio. Añadir o quitar al final es barato. Pero insertar o borrar en el medio desplaza todo lo que viene después para mantener intactos el orden y la numeración — O(n).

Linear search — encontrar por valor

Puedes abrir el casillero 500 al instante — pero si solo sabes qué hay dentro y no en qué casillero, tienes que abrirlos uno por uno hasta encontrarlo.

La trampa: un array es rápido solo cuando conoces el index. Para encontrar un elemento por su contenido — «¿está este email en la lista?» — tienes que revisar cada uno por turno. Eso es la linear search, O(n): lenta en listas grandes. Ese hueco es justo el problema que resuelve la siguiente estructura.

Hash Map — pares clave-valor

Una guía telefónica: buscas a una persona por su nombre y obtienes su número al instante. No recorres todas las entradas — el nombre te lleva directo a la respuesta.

Un hash map (también llamado diccionario, hash table o simplemente map) guarda los datos como pares clave-valor: le das una clave y te devuelve el valor correspondiente. Un usuario por ID, un ajuste por nombre, un conteo por palabra — directamente, por la clave. Donde un array te obliga a conocer la posición, un hash map te deja encontrar por un nombre con sentido.

Hash function — por qué la búsqueda es instantánea

Un archivador mágico que, dada una etiqueta, abre directo el cajón correcto sin revisar los demás — el número de cajones no lo hace más lento.

La magia de un hash map es que buscar por clave es en la práctica O(1) — tiempo constante, sin importar cuántos elementos contenga. La clave pasa por una hash function que calcula dónde vive el valor, así que el map salta directo allí en lugar de buscar. Un millón de entradas o diez, encontrar una es igual de rápido. Por eso el hash map es el caballo de batalla: «encontrar por nombre» es lo que los programas hacen constantemente.

Set — presente o no, sin valores

Una lista de invitados en la puerta — no necesitas ningún detalle, solo un sí o un no: ¿está este nombre en la lista? Se comprueba al instante, sin recorrer nada.

Un primo cercano es el set: un hash map que guarda solo claves, sin valores, para responder rápido una pregunta — «¿está presente esto?». Comprobar pertenencia y evitar duplicados son ambos O(1). Cada vez que te veas recorriendo una lista para preguntar «¿ya vi esto?», un set convierte esa lenta comprobación O(n) en una instantánea.

Stack — último en entrar, primero en salir (LIFO)

Una pila de platos: pones encima y tomas de encima, así que el último plato que dejaste es el primero que recoges.

Un stack sigue LIFO — last in, first out. Añades (push) y quitas (pop) por el mismo extremo, así que el elemento más reciente sale primero. Encaja con todo lo que se anida o se deshace en orden inverso: un historial de deshacer, el botón de atrás, la call stack de un programa. Ambas operaciones son O(1).

Queue — primero en entrar, primero en salir (FIFO)

Una cola en una taquilla: se atiende a la gente en el orden en que llegó, los recién llegados se ponen al final y se atiende al primero de la fila.

Una queue sigue FIFO — first in, first out. Añades por detrás (enqueue) y quitas por delante (dequeue), así que los elementos se procesan en orden de llegada. Es la estructura para la equidad y el orden: tareas por procesar, trabajos en espera, peticiones que atender por turno — justo la idea de la cola de mensajes del curso de queues. Como un stack, sus operaciones son O(1).

La regla determina el comportamiento

El mismo montón de trabajo, dos puertas: una devuelve el elemento más reciente, la otra el más antiguo. La única elección de qué extremo cambia todo lo que viene después.

Los stacks y las queues guardan el mismo tipo de datos; la única diferencia es por qué extremo quitas. Elegir entre ellos es elegir el orden en que vuelve tu trabajo: inverso y anidado (stack) o justo y secuencial (queue). Una decisión pequeña con un efecto grande — acierta con el orden y el resto de la lógica encaja sola.

Tree — una jerarquía

Un árbol genealógico o el organigrama de una empresa: una cosa arriba, que se ramifica hacia abajo en hijos, cada uno de los cuales puede ramificarse más — una estructura que se abre en abanico y nunca vuelve atrás.

Un tree organiza los datos como una jerarquía: una raíz (root) arriba, que se ramifica en nodos que tienen hijos, y así hacia abajo. Modela todo lo anidado — carpetas dentro de carpetas, comentarios y sus respuestas, un menú de categorías. La forma ramificada refleja el anidamiento del mundo real, lo que hace de los trees el ajuste natural siempre que tus datos son «cosas dentro de cosas». La mayoría de las jerarquías que encuentras en el software son trees por debajo.

Balanced tree — búsqueda en O(log n)

Encontrar un nombre en una guía telefónica abriendo por la mitad, luego por la mitad de la mitad derecha, una y otra vez — cada paso descarta la mitad de lo que queda.

Un tree bien organizado, equilibrado, da una propiedad potente: puedes buscar en él en O(log n) dividiendo el espacio a la mitad una y otra vez, como encuentras una palabra en un diccionario sin leer cada página. Esa forma logarítmica apenas crece aunque los datos exploten — mil millones de elementos son solo unos treinta pasos. Así mantienen las bases de datos las búsquedas rápidas a escala enorme: datos ordenados en forma de tree, buscados por mitades.

Graph — una red de conexiones

Un mapa de ciudades unidas por carreteras, o de personas unidas por amistades — cosas conectadas entre sí en cualquier patrón, sin arriba ni abajo.

Un graph es la forma más general: nodos conectados por aristas (edges), en cualquier patrón, incluidos los ciclos. Modela redes — conexiones sociales, carreteras entre ciudades, enlaces entre páginas, dependencias entre tareas. Siempre que los datos sean en el fondo «cosas relacionadas con otras cosas» y no una jerarquía ni una línea, es un graph. Muchos problemas difíciles e interesantes — la ruta más corta, quién está conectado con quién — son problemas de graphs en el fondo.

Dominant operation — elige por lo que más haces

Abasteces la cocina según lo que cocinas cada noche, no según lo que luce impresionante.

La decisión práctica casi siempre es: ¿qué operación haré más, y qué estructura vuelve rápida esa? ¿Buscar por clave, constantemente? Hash Map. ¿Necesitas las cosas en orden de llegada? Queue. ¿Sobre todo lees por posición? Array. Deja que la dominant operation elija la estructura, y acepta que será más lenta en lo que rara vez haces. Optimiza el caso común; la estructura es el cómo.

Map before loop — usa un map antes que un bucle

Antes de buscar a alguien entre la multitud cara por cara, compruebas si hay una lista de invitados — la lista responde al instante lo que la búsqueda hace despacio.

Un movimiento muy común y muy eficaz: cuando te descubras recorriendo una lista para encontrar o emparejar cosas — un bucle O(n), o peor, un bucle O(n²) dentro de otro bucle — pregúntate si un hash map o un set podría volverlo instantáneo. Cambiar una búsqueda anidada por una consulta a un map es una de las aceleraciones más frecuentes en el mundo real. La solución suele ser la estructura, no un bucle más rápido.

Cómo se conecta todo

Un árbol genealógico de herramientas: cada una cubre una debilidad de la anterior.

Big-O es la regla con que se mide cada estructura. Un Hash Map arregla el punto débil del Array (encontrar por valor); un Set es un Hash Map sin valores. Stack y Queue son una secuencia con la regla «tomar solo por un extremo». Un Tree añade jerarquía, y uno equilibrado busca en O(log n); un Graph levanta la última restricción y permite cualquier enlace.