Estructuras de datos

La forma en que guardas los datos no es un detalle: es la decisión que determina que vas a poder hacer rápido y que te va a costar caro. Puedes guardar los mismos mil registros en un arreglo, en una lista enlazada, en una tabla hash o en un árbol, y el dato será el mismo; pero la operación que vas a repetir millones de veces (buscar, insertar, recorrer en orden) será veloz en unas estructuras y desesperante en otras. Elegir bien la estructura es, con frecuencia, más rentable que optimizar el código que la usa.

Esta ficha no es un catálogo para memorizar, sino un mapa mental. La pregunta ordenadora es siempre la misma: que operación voy a repetir más veces? En torno a esa pregunta se ordenan las estructuras.

Contiguo contra enlazado: arreglo y lista

Un arreglo guarda sus elementos uno al lado del otro, en memoria contigua. Esa sencillez tiene un precio maravilloso y una trampa. El precio maravilloso es el acceso directo: si sabes la posición, llegar al elemento cuesta lo mismo tengas diez o diez millones. La trampa es que insertar o borrar en medio obliga a desplazar todo lo que viene después, y que el tamaño suele ser fijo de antemano.

La lista enlazada es la respuesta al revés: cada elemento vive donde pueda y guarda una flecha al siguiente. Insertar y borrar en una posición conocida es barato, porque solo hay que recomponer flechas. Pero para llegar al elemento número mil hay que saltar desde el primero, uno por uno: ya no hay acceso directo. La elección entre arreglo y lista es, en el fondo, la elección entre acceder rápido o modificar rápido.

Pila y cola: dos órdenes naturales

Hay dos formas de ordenar el acceso que aparecen una y otra vez. La pila es el modelo del plato apilado: lo último en entrar es lo primero en salir. Sirve para todo lo que se anida, como las llamadas de una función dentro de otra o el botón de deshacer. La cola es el modelo de la fila del banco: lo primero en entrar es lo primero en salir, y sirve para todo lo que debe ser justo en el orden de llegada. Una variante útil es la cola de prioridad, donde sale primero el más importante, no el más antiguo: es la base de los planificadores de tareas.

La tabla hash, y por qué es casi magia

Si lo que necesitas es buscar un valor por su nombre y encontrarlo al instante, la tabla hash es la estructura favorita. La idea es simple y poderosa: pasas la clave por una función hash que produce un número, y ese número te dice en que casilla guardar o buscar el valor. Si la función es buena, buscar, insertar y borrar son casi instantáneos en promedio: casi constante, sin importar cuantos elementos haya. Por eso los diccionarios de Python, los mapas de JavaScript y los objetos de tantos lenguajes son, por debajo, tablas hash.

La magia deja de serlo en dos momentos. El primero es la colisión: dos claves distintas que producen el mismo número. Es inevitable, porque hay infinitas claves posibles y casillas finitas, así que toda tabla hash necesita una estrategia para resolver colisiones, usualmente encadenando los valores chocados en una pequeña lista. El segundo es el peor caso: si un adversario conoce tu función hash, puede elegir claves que colisionen todas y degradar la tabla a una lista lenta. Por eso las tablas hash modernas usan funciones con cierta aleatoriedad.

Árboles: cuando interesa el orden

Un árbol organiza los datos en ramas a partir de una raíz, y el caso más útil es el árbol binario de búsqueda: cada nodo tiene a la izquierda los menores y a la derecha los mayores. En un árbol así, buscar, insertar y borrar crecen lentamente: doblar los elementos añade solo un paso. Es el punto dulce entre el arreglo (acceso directo, inserción cara) y la lista (inserción barata, búsqueda lenta).

El peligro es el desequilibrio. Si insertas los datos ya ordenados, el árbol degenera en una lista y pierde toda su ventaja. Por eso se inventaron los árboles balanceados, como el AVL, que se reacomodan en cada inserción para mantenerse aproximadamente parejos. Las bases de datos llevan esta idea más lejos con los árboles B, anchos y poco profundos, pensados para vivir en disco, donde cada salto entre nodos es caro.

Montículos, grafos y la regla práctica

El montículo es un árbol con una propiedad simple (el padre siempre menor, o mayor, que sus hijos) que hace que sacar el elemento extremo cueste poco. Es la estructura detras de la cola de prioridad y de algoritmos como el heapsort. El grafo, en cambio, no es jerárquico: es una red de puntos unidos por aristas, y modela mapas, dependencias, redes sociales y rutas. Recorrer un grafo en anchura (nivel por nivel) o en profundidad (hasta el fondo antes de retroceder) resuelve buena parte de los problemas de caminos y conexiones.

La regla práctica para elegir no requiere memoria de catálogo. Si vas a acceder por posición, arreglo. Si vas a insertar y borrar mucho en medio, lista. Si vas a buscar por clave al instante, tabla hash. Si necesitas los datos ordenados y consultas por rango, árbol balanceado. Si lo que importa es siempre el extremo, montículo. Y si lo que modelas son relaciones entre cosas, grafo. Con esos seis polos se cubre la mayoría de los casos reales.

Lo que queda fijo

No existe la estructura de datos perfecta, sino la correcta para la operación que más se repite. Toda estructura favorece unas operaciones sacrificando otras, y el oficio está en reconocer cual de ellas es la crítica antes de elegir. Por eso esta área se entiende mejor como un mapa mental (que operación voy a repetir) que como una lista de definiciones. Cuando la elección acierta, el rendimiento aparece solo; cuando falla, ningún código brillante compensa la estructura equivocada.