Curso exprés · No. 23
Una data structure no es más que una manera de organizar los datos para que las cosas que haces más a menudo sean rápidas. Elige la correcta y una operación es instantánea; elige la equivocada y la misma tarea se arrastra. Big-O es el lenguaje para esa diferencia — cómo crece el costo de una operación a medida que crecen los datos. Aprende unas cuantas estructuras y la notación, y «¿por qué esto es lento?» suele responderse solo.
Solo lo esencial · Una imagen por idea · Aprende las palabras
Antes de las estructuras concretas, la idea detrás de todas ellas. Una data structure no es algo académico — es la única decisión que más a menudo determina si tu código es rápido o dolorosamente lento.
Una data structure organiza 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 — porque la disposición que vuelve una operación instantánea a menudo vuelve otra lenta. Elige para tu caso común.
La estructura correcta convierte lo difícil en fácil
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. Los mismos datos, la disposición lo es todo.
La misma tarea puede ser trivial o casi imposible según cómo se guarden los datos. Buscar a un usuario por ID es instantáneo en una estructura y un suplicio a través de todo en otra. Así que una cantidad sorprendente de «hacer esto rápido» es en realidad «guardarlo con la forma correcta». Elegir bien desde el principio suele ganarle a cualquier cantidad de optimización ingeniosa más tarde — la estructura es la decisión.
Toda estructura es una compensación
Un auto deportivo y un camión de mudanzas son ambos vehículos — no preguntas cuál es mejor, preguntas mejor para qué. La velocidad en una cosa se paga con costo en otra.
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. Elegir significa saber para qué estás optimizando y qué estás dispuesto a ceder. No hay almuerzo gratis — toda estructura cambia fortaleza en una operación por debilidad en otra, y tu trabajo es elegir la compensación que encaja con tu uso.
Una data structure organiza los datos para que tus operaciones comunes sean rápidas. La forma correcta vuelve fácil una tarea difícil — y toda estructura cambia velocidad en una operación por debilidad en otra.
Para comparar estructuras necesitas una manera de hablar de velocidad que no dependa de la máquina. Big-O es ese lenguaje: mide cómo crece el trabajo a medida que crecen los datos.
Big-O mide el crecimiento, no los 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 costo 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.
Las formas comunes, 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 — toma el mismo tiempo sin importar el tamaño (tomar un elemento por index). O(n) — lineal — crece al ritmo de los datos (recorrer una list). O(n²) — cuadrática — explota a medida que crecen los datos (comparar cada elemento con todos los demás), y es la clásica «bien en pruebas, muere en producción». O(log n) — logarítmica — apenas crece aunque los datos se disparen (reduciendo la búsqueda a la mitad en cada paso). Saber qué forma tiene tu operación te dice si sobrevivirá a la escala.
La forma solo importa a escala
Dos rutas que son idénticas en un trayecto corto divergen salvajemente en uno largo — la diferencia es invisible hasta que la distancia es lo bastante grande para revelarla.
Para diez elementos, toda estructura se siente instantánea — las diferencias no se notan. Big-O trata de lo que pasa cuando n se hace grande: con un millón de elementos, un enfoque O(n²) que estaba bien en tu prueba ahora muele durante minutos mientras uno O(n) termina al instante. Por eso las cosas se vuelven «de repente» lentas en producción: la mala forma siempre estuvo ahí, solo oculta hasta que crecieron los datos. Piensa en la forma antes de que la escala la exponga.
Big-O mide cómo crece el trabajo con los datos, no segundos en bruto. O(1) y O(log n) sobreviven a la escala; O(n) es honesta; O(n²) está bien en pruebas y muere en producción.
La estructura más básica es el array, o list: una secuencia ordenada de elementos. Saber exactamente en qué es rápido y en qué es lento fija la base para todo lo demás.
Un array es 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í puedes ir directo a cualquiera por su número.
Un array (o list) guarda 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 lo predeterminado para «un montón de cosas en orden», y ese acceso directo por posición es su superpoder. Cuando sabes dónde está algo, lo tienes de inmediato.
Rápido por posición, lento de encontrar por valor
Puedes abrir el casillero 500 al instante — pero si solo sabes lo que hay dentro y no qué casillero, debes abrirlos uno por uno hasta encontrarlo.
El truco: un array es rápido solo cuando conoces el index. Para encontrar un elemento por su contenido — «¿está este correo en la list?» — tienes que revisar cada uno por turno, lo cual es O(n), lento para listas grandes. Así que un array es perfecto cuando accedes por posición y pobre cuando buscas por valor. Esa brecha es exactamente el problema que resuelve la siguiente estructura.
Insertar en el medio es costoso
Para meter un libro nuevo en el medio de un estante numerado y repleto, cada libro detrás de él debe correrse un lugar para hacer espacio — una pequeña inserción, mucho desplazamiento.
Añadir o quitar al final de un array es barato, pero insertar o borrar en el medio significa desplazar todo lo que está detrás para mantener intactos el orden y la numeración — O(n). Así que los arrays son ideales cuando mayormente lees por posición y agregas al final, y un mal encaje cuando constantemente insertas y quitas en el medio. Adáptalos al trabajo de acceso por index, con muchos agregados.
Un array es una secuencia ordenada e indexada: acceso instantáneo por posición, pero O(n) para buscar por valor o insertar en el medio. Estupendo para trabajo de lectura por index, con muchos agregados.
Si una estructura merece ser tu caballo de batalla por defecto, es el hash map. Resuelve la mayor debilidad del array — encontrar cosas por valor — y lo hace casi al instante.
Un hash map guarda pares clave-valor
Una guía telefónica: buscas a una persona por nombre y obtienes su número al instante. No recorres cada entrada — el nombre te lleva directo a la respuesta.
Un hash map (también llamado dictionary, hash table, o simplemente map) guarda los datos como pares clave-valor: le das una clave, te da el valor correspondiente. Busca a un usuario por su ID, un ajuste por su nombre, un conteo por una palabra — directamente, por la clave. Donde un array te obliga a conocer la posición, un hash map te deja encontrar por nombre con significado. Es la estructura para «búscame esto por su identificador».
La búsqueda es efectivamente instantánea
Un archivero mágico que, dada una etiqueta, se abre directo en el cajón correcto sin revisar los demás — la cantidad de cajones no lo ralentiza.
La magia de un hash map es que la búsqueda por clave es efectivamente O(1) — tiempo constante, sin importar cuántos elementos contenga. Usa la clave para calcular exactamente dónde vive el valor, así que 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: vuelve instantáneo el «encontrar por nombre», que es lo que los programas hacen constantemente.
El set: pertenencia 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? Comprobado al instante, sin recorrer.
Un primo cercano es el set: un hash map que guarda solo claves, sin valores, para responder rápido una pregunta — «¿está esta cosa presente?». Comprobar pertenencia y evitar duplicados son ambos O(1). Cada vez que te descubras recorriendo una list para preguntar «¿ya he visto esto?», un set convierte esa lenta comprobación O(n) en una instantánea. Échale mano para unicidad y pruebas rápidas de pertenencia.
Un hash map encuentra un valor por su clave en efectivamente O(1) — el caballo de batalla para la búsqueda por identificador. Su primo el set responde «¿está esto presente?» con la misma instantaneidad.
A veces el orden en que sacas las cosas importa tanto como lo que guardas. Dos estructuras formalizan los dos órdenes naturales — y la diferencia entre ellas es una sola regla intuitiva.
Un stack es último en entrar, primero en salir
Una pila de platos: añades arriba y tomas de arriba, 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. Esto coincide con cualquier cosa que se anida o se deshace en reversa: un historial de deshacer, el botón atrás, el call stack de un programa. Ambas operaciones son O(1). Cuando el orden natural es «el más reciente primero», o «deshaz lo último», quieres un stack.
Un queue es primero en entrar, primero en salir
Una fila en una taquilla: se atiende a la gente en el orden en que llegó, los recién llegados se unen atrás, y al frente se le atiende a continuación.
Un queue sigue FIFO — first in, first out. Añades atrás y quitas del frente, así que los elementos se manejan en orden de llegada. Esta es la estructura para la equidad y el orden: tareas por procesar, trabajos esperando, peticiones por atender por turno — exactamente la idea de la cola de mensajes del curso de queues. Como un stack, sus operaciones son O(1). Cuando el orden de llegada debe ser el orden de atención, quieres un queue.
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 lo cambia todo aguas abajo.
Los stacks y queues contienen el mismo tipo de datos; la única diferencia es de qué extremo quitas, y esa única regla moldea todo el comportamiento. Elegir entre ellos es elegir el orden en que tu trabajo regresa: en reversa y anidado (stack) o justo y secuencial (queue). Es una decisión pequeña con un gran efecto — acierta con el orden y el resto de la lógica cae en su lugar.
Un stack es último en entrar, primero en salir — deshacer, anidar, revertir. Un queue es primero en entrar, primero en salir — procesamiento justo y en orden. Los mismos datos; el extremo del que quitas es toda la diferencia.
Las dos últimas estructuras manejan datos que no son una línea plana sino que tienen forma — cosas que se ramifican en jerarquías, o se conectan en redes. Son cómo modelas relaciones.
Un tree es una jerarquía
Un árbol genealógico o un organigrama de empresa: una cosa en la cima, ramificándose hacia abajo en hijos, cada uno de los cuales puede ramificarse más — estructura que se abre en abanico, nunca vuelve a unirse.
Un tree organiza los datos como una jerarquía: una raíz en la cima, ramificándose en nodes que tienen hijos, y así hacia abajo. Modela cualquier cosa anidada — 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 encaje 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.
Un tree balanceado busca en O(log n)
Encontrar un nombre en una guía telefónica abriendo el medio, luego el medio de la mitad derecha, una y otra vez — cada paso descarta la mitad de lo que queda.
Un tree bien organizado (balanced) ofrece una propiedad poderosa: puedes buscarlo en O(log n) reduciendo a la mitad el espacio repetidamente, igual que 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í es como las bases de datos mantienen rápidas las búsquedas a escala enorme: datos ordenados en forma de tree, buscados por mitades.
Un graph es una red de conexiones
Un mapa de ciudades unidas por carreteras, o personas unidas por amistades — cosas conectadas entre sí en cualquier patrón, sin cima y sin fondo.
Un graph es la forma más general: nodes conectados por edges, en cualquier patrón, incluidos bucles. Modela redes — conexiones sociales, carreteras entre ciudades, enlaces entre páginas, dependencias entre tareas. Siempre que los datos sean fundamentalmente «cosas relacionadas con otras cosas» en lugar de una jerarquía o 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 graph en el fondo.
Un tree modela jerarquía y, cuando está balanced, busca en O(log n) por mitades. Un graph modela una red de conexiones. Úsalos cuando los datos tienen forma — anidados o enlazados.
Rara vez construyes estas desde cero — tu lenguaje las provee. La habilidad está en elegir la correcta para el trabajo, y saber suficiente Big-O para sentir una mala elección antes de que muerda.
Elige por la operación que más haces
Surtes la cocina según lo que cocinas cada noche, no según lo que se ve impresionante — las herramientas correctas son las de tu trabajo real y repetido.
La decisión práctica es casi siempre: ¿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. ¿Mayormente leer por posición? Array. Deja que la operación dominante elija la estructura, y acepta que será más lenta en las cosas que rara vez haces. Optimiza el caso común; la estructura es cómo.
Échale mano a un map antes que a un loop
Antes de buscar en una multitud cara por cara a alguien, 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 efectivo: cuando te descubras recorriendo una list para encontrar o emparejar cosas — un loop O(n), o peor un loop O(n²) dentro de un loop — pregúntate si un hash map o set podría volverlo instantáneo. Reemplazar una búsqueda anidada con una búsqueda en un map es una de las aceleraciones del mundo real más frecuentes que existen. La estructura, no un loop más rápido, suele ser el arreglo.
- ¿Qué operación domina — búsqueda, ordenamiento, añadir/quitar — para estos datos? - ¿Búsqueda por clave? Un hash map (o un set, para presencia) es O(1). - ¿Acceso por posición, con muchos agregados? Un array encaja. - El orden de quitar importa — el más reciente (stack) o el más antiguo (queue)? - ¿Datos anidados o en red — un tree o un graph? - A escala, cuál es el Big-O — y ¿hay algo secretamente O(n²)?
- data structure — una manera de organizar los datos para que las operaciones comunes sean rápidas. - Big-O / n — cómo crece el costo con el tamaño de los datos. - O(1) / O(n) / O(n²) / O(log n) — crecimiento constante, lineal, cuadrático, logarítmico. - array / list / index — una secuencia ordenada y numerada; O(1) por posición. - hash map / dictionary / set — búsqueda clave-valor y comprobaciones de presencia en O(1). - stack / queue / LIFO / FIFO — último-en-entrar-primero-en-salir y primero-en-entrar-primero-en-salir. - tree / graph / node / edge — jerarquía y red; los trees balanced buscan en O(log n).
- Eliges la estructura por la operación que más haces, no por costumbre. - Échale mano a un hash map o set en lugar de recorrer una list para encontrar o quitar duplicados. - Puedes nombrar el Big-O de tu camino caliente y no tienes ningún O(n²) oculto. - Usas un stack o queue cuando el orden de quitar importa, y un tree o graph cuando los datos tienen forma.
- Las cosas se mantienen rápidas a medida que crecen los datos, porque elegiste la forma antes de que la escala la expusiera.
No construyes estas desde cero — las eliges. Haz coincidir la estructura con la operación que más haces, échale mano a un map antes que a un loop, y deja que Big-O te avise antes de que lo haga la escala.