Estructuras de datos

Arrays, listas, diccionarios (hash maps), árboles y grafos: cómo elegir la caja correcta para tus datos y por qué esa elección decide si un programa vuela o se arrastra.

Imagina que tienes que buscar un número de teléfono. Si los contactos están en una lista de papel sin ordenar, no te queda otra que leerla entera hasta encontrarlo. Si están en una agenda alfabética, saltas directo a la letra. Y si tuvieras una guía mágica donde dices el nombre y aparece el número al instante, ni siquiera tendrías que buscar. Esas tres agendas son, básicamente, tres estructuras de datos distintas. Mismo dato, tres formas de guardarlo, tres velocidades muy diferentes.

Elegir bien la estructura es una de esas decisiones que no se ven pero se sienten: es la razón por la que un programa vuela o se arrastra.

El costo se mide en "grande", no en segundos

No medimos la velocidad de una estructura en milisegundos —eso depende del computador—, sino en cómo crece el trabajo cuando crecen los datos. Es la famosa notación Big-O.

$O (1)$ — tiempo constante. Da igual si tienes 10 datos o 10 millones: la operación tarda lo mismo. Es el ideal.
$O (lo g n)$ — logarítmico. Duplicar los datos apenas añade un paso. Excelente.
$O (n)$ — lineal. El doble de datos, el doble de trabajo. Aceptable.
$O (n^{2})$ — cuadrático. El doble de datos, cuatro veces el trabajo. Empieza el peligro.

Con esta lente, las estructuras dejan de ser abstractas: cada una es un conjunto de operaciones con su propio costo.

Array: la fila de casilleros

Un array (o arreglo) es memoria contigua: casilleros numerados, uno tras otro. Su superpoder es el acceso por posición: pedir el elemento 5.000 cuesta $O (1)$ , porque el computador calcula directo dónde está.

Su debilidad es insertar en el medio. Si quieres meter un dato en la posición 3 de un array de un millón, hay que correr todos los que vienen después: $O (n)$ .

Un array guarda los datos pegados y numerados: llegar a cualquier índice es inmediato, pero abrir hueco en el medio obliga a correr al resto.

Lista enlazada: el tren de vagones

En una lista enlazada cada elemento (nodo) guarda su valor y una flecha al siguiente. No hay numeración: para llegar al quinto vagón, recorres del primero al quinto. Buscar es lento ( $O (n)$ ), pero insertar es trivial: enganchas un vagón nuevo cambiando dos flechas, sin mover a nadie.

Array y lista son el primer trade-off clásico: acceso rápido contra inserción rápida. No hay estructura perfecta, hay estructura adecuada.

Pila y cola: el orden importa

Con arrays y listas se construyen dos patrones de uso muy comunes:

Pila (stack, LIFO): lo último que entra es lo primero que sale, como una pila de platos. Es lo que hay detrás del botón "atrás" del navegador o del deshacer de un editor.
Cola (queue, FIFO): el primero que llega es el primero que se atiende, como la fila del banco. Aparece en cada sistema de tareas y de mensajería.

Hash map: la guía mágica

Aquí es donde ocurre la magia que mencionábamos al principio. Un hash map (diccionario, tabla hash) guarda pares clave → valor y responde en tiempo constante $O (1)$ promedio. Le das la clave "Ana" y te devuelve su teléfono sin recorrer nada.

El truco es una función de hash: convierte la clave en un número que dice en qué casillero guardar el valor. Buscar es aplicar la misma función y mirar directo ese casillero.

# El diccionario de Python es un hash map. Conteo de palabras en O(n):
texto = "el gato y el perro y el gato"
conteo = {}
for palabra in texto.split():
    conteo[palabra] = conteo.get(palabra, 0) + 1
# {'el': 3, 'gato': 2, 'y': 2, 'perro': 1}

Si en vez de un diccionario recorrieras una lista buscando cada palabra, el conteo sería $O (n^{2})$ . Con el hash map es $O (n)$ . Esa es, literalmente, la diferencia entre esperar y no esperar. En ciencia de datos, los diccionarios están por todas partes: agrupar, contar, unir tablas, cachear resultados.

Árboles: jerarquía y búsqueda ordenada

Un árbol organiza datos en jerarquía: un nodo raíz, que se ramifica en hijos, que se ramifican en más hijos. Las carpetas de tu computador son un árbol; el HTML de esta página también.

El caso estrella es el árbol de búsqueda balanceado: mantiene los datos ordenados de modo que buscar, insertar y borrar cuestan $O (lo g n)$ . Ese logaritmo no es casualidad: en cada paso descartas la mitad de los datos, igual que al buscar una palabra en el diccionario abriéndolo por la mitad. No por nada los índices de las bases de datos que veremos después son, por dentro, árboles.

Y no es un tema lejano de la IA: los árboles de decisión y todo Random Forest son esta misma estructura puesta a clasificar.

Grafos: cuando todo se conecta con todo

Un grafo son nodos unidos por aristas, sin una jerarquía fija. Es la estructura de las relaciones: amistades en una red social, calles entre esquinas, páginas web enlazadas, dependencias entre tareas.

Su fuerza es responder preguntas de conexión: ¿cuál es el camino más corto entre A y B?, ¿qué tan central es este nodo? El GPS que usas para llegar a casa está corriendo un algoritmo de grafos. Y cuando en los casos prácticos orquestamos un flujo de IA como un grafo de estados, estamos usando exactamente esta idea.

La tabla que conviene tener en la cabeza

Estructura	Buscar	Insertar	Brilla cuando…
Array	$O (n)$	$O (n)$	accedes mucho por posición
Lista enlazada	$O (n)$	$O (1)$	insertas y borras seguido
Hash map	$O (1)$	$O (1)$	buscas por clave
Árbol balanceado	$O (lo g n)$	$O (lo g n)$	necesitas orden y velocidad
Grafo	—	—	modelas relaciones

En resumen

No existe la mejor estructura de datos; existe la adecuada para lo que vas a hacer con ella. Si buscas por clave, un hash map. Si necesitas orden, un árbol. Si modelas relaciones, un grafo. Interiorizar el costo Big-O de cada operación es lo que te permite mirar un código lento y saber, casi de un vistazo, dónde está el problema. En la próxima lección subimos un nivel: qué pasa cuando estos datos tienen que sobrevivir en disco y ser consultados por mucha gente a la vez, y entramos de lleno a las bases de datos relacionales.