Estructuras de datos y algoritmos que todo programador debe conocer

Una estructura de datos es una forma concreta de organizar y almacenar información en la memoria de un programa, de manera que se pueda acceder a ella y manipularla de forma eficiente según las necesidades. La idea de fondo es que los datos no se guardan de cualquier manera, sino con una organización que facilita ciertas operaciones a costa de otras, y por eso existen distintas estructuras adaptadas a distintos usos. Entre las fundamentales están el array o arreglo, que guarda elementos en una fila contigua y permite acceder a cualquiera de forma instantánea si se conoce su posición, aunque insertar o borrar en el medio resulta costoso; la lista enlazada, donde cada elemento apunta al siguiente formando una cadena, lo que facilita insertar y borrar en cualquier punto pero obliga a recorrerla para llegar a un elemento concreto; la pila, que sigue el criterio de que el último en entrar es el primero en salir; la cola, que sigue el criterio opuesto de que el primero en entrar es el primero en salir; el mapa o tabla hash, que guarda pares de clave y valor y permite buscar un valor por su clave de forma casi instantánea; el árbol, que organiza los datos en una jerarquía de nodos; y el grafo, que representa relaciones arbitrarias entre elementos conectados en red. La razón por la que conviene conocer varias estructuras es que cada una destaca en unas operaciones y es ineficiente en otras, de modo que elegir la adecuada para lo que el problema requiere puede marcar una diferencia enorme en el rendimiento. Elegir bien la estructura de datos es una de las decisiones que más impacto tiene en la eficiencia de un programa, y saber reconocer qué estructura encaja con cada situación es una habilidad central de la programación.

Un algoritmo es una secuencia finita de pasos bien definidos que resuelve un problema o completa una tarea, algo así como una receta precisa que, seguida al pie de la letra, conduce siempre al resultado buscado a partir de unas entradas dadas. En programación, los algoritmos son el corazón de lo que hace un programa: buscar un elemento dentro de un conjunto de datos, ordenar una lista de menor a mayor, encontrar el camino más corto entre dos puntos de un mapa, o calcular un resultado a partir de ciertos datos, todos son problemas que se resuelven mediante algoritmos. Una idea clave es que un mismo problema suele admitir varios algoritmos distintos que llegan al mismo resultado correcto, pero que difieren notablemente en su eficiencia, es decir, en la cantidad de trabajo que requieren. El ejemplo clásico es la búsqueda de un dato: se puede buscar recorriendo todos los elementos uno por uno desde el principio, lo que funciona siempre pero puede ser lento con muchos datos, o bien, si los datos están ordenados, se puede usar la búsqueda binaria, que en cada paso descarta la mitad de los datos restantes y así encuentra el elemento muchísimo más rápido. Esta diferencia ilustra por qué no basta con que un algoritmo sea correcto, sino que también importa que sea eficiente, sobre todo cuando la cantidad de datos es grande. Por eso, saber diseñar y elegir buenos algoritmos, y entender cómo se comporta cada uno a medida que crecen los datos, es una de las habilidades más valiosas de un programador, y está estrechamente ligada a la elección de la estructura de datos adecuada, ya que un algoritmo eficiente suele apoyarse en la estructura correcta. La notación Big O es precisamente la herramienta que permite comparar la eficiencia de distintos algoritmos de forma objetiva.

La notación Big O es una forma estandarizada de describir cómo crece el trabajo que requiere un algoritmo a medida que aumenta el tamaño de la entrada, es decir, la cantidad de datos que procesa. Su gran virtud es que no mide el tiempo en segundos, que dependería del hardware concreto y del lenguaje, sino que captura la tendencia de crecimiento, permitiendo comparar la eficiencia de distintos algoritmos de manera objetiva e independiente de la máquina. Se expresa con la letra O seguida de una función del tamaño de los datos, y las complejidades más comunes, de mejor a peor, son las siguientes. La complejidad constante indica que el tiempo no cambia con la cantidad de datos, de modo que tarda lo mismo con diez elementos que con un millón; es la mejor posible, y un ejemplo típico es buscar un valor en un mapa a partir de su clave. La complejidad logarítmica indica que el tiempo crece muy poco aunque los datos crezcan mucho, porque en cada paso se descarta una gran parte del trabajo restante; es excelente, y su ejemplo clásico es la búsqueda binaria en datos ordenados. La complejidad lineal indica que el tiempo crece en proporción directa a los datos, de forma que el doble de datos supone el doble de tiempo; es razonable, y corresponde por ejemplo a recorrer una lista entera una vez. Existe también una complejidad algo peor que la lineal, característica de los buenos algoritmos de ordenación. Y la complejidad cuadrática indica que el tiempo crece con el cuadrado de los datos, de manera que multiplicar por diez los datos multiplica por cien el trabajo; es peligrosa con volúmenes grandes, y aparece típicamente cuando se comparan todos los elementos con todos mediante bucles anidados. Lo esencial que aporta Big O es la capacidad de anticipar cómo se comportará un algoritmo cuando los datos crezcan, algo que no se aprecia con pocos datos pero que puede ser decisivo con muchos.

La eficiencia importa, incluso cuando el programa ya funciona correctamente, porque la corrección y la eficiencia son dos cualidades distintas, y un programa puede dar siempre el resultado correcto y aun así ser inservible en la práctica por ser demasiado lento cuando los datos crecen. La razón está en cómo escalan los algoritmos: una solución que se comporta perfectamente durante el desarrollo y las pruebas, donde normalmente se usan cantidades modestas de datos, puede degradarse de forma catastrófica en producción, donde los datos reales pueden ser órdenes de magnitud mayores. El caso más ilustrativo es el de un algoritmo de complejidad cuadrática, que compara cada elemento con todos los demás: con cien elementos hace del orden de diez mil operaciones y parece instantáneo, pero con cien mil elementos hace del orden de diez mil millones de operaciones y puede tardar minutos o bloquearse, porque al multiplicar por mil la cantidad de datos, el trabajo se multiplica por un millón. Este tipo de problemas suele pasar inadvertido hasta que el sistema tiene usuarios y datos reales, momento en el que aparece de golpe y de forma difícil de diagnosticar si no se entiende la cuestión de la escalabilidad. Por eso un programador con criterio no se conforma con la pregunta de si el programa funciona, sino que además se pregunta cómo se comportará cuando la cantidad de datos crezca, y elige estructuras de datos y algoritmos cuya complejidad sea adecuada al tamaño esperado del problema. Dicho esto, la eficiencia debe buscarse con sentido de la medida: no tiene sentido complicar el código para ahorrar microsegundos en partes que procesan pocos datos o que no son críticas, y la optimización prematura, es decir, optimizar antes de saber dónde está realmente el cuello de botella, es un error conocido. Lo sensato es conocer la complejidad de lo que se escribe, evitar los patrones claramente ineficientes cuando los datos pueden crecer, y medir para optimizar donde de verdad importa.

La forma de decidir qué estructura de datos usar consiste en identificar cuáles son las operaciones que el programa va a realizar con más frecuencia sobre esos datos y elegir la estructura que hace esas operaciones de manera eficiente, aceptando que sea menos buena en las operaciones que se usarán poco. Como cada estructura destaca en unas cosas y es mala en otras, la clave está en hacer coincidir el perfil de uso con las fortalezas de la estructura. Por ejemplo, si el programa va a hacer muchas búsquedas de un valor a partir de un identificador o una clave, un mapa o tabla hash es casi siempre la mejor elección, porque permite esas búsquedas de forma casi instantánea, mientras que buscar recorriendo una lista sería mucho más lento. Si lo principal es acceder a elementos por su posición numérica y el conjunto no cambia mucho de tamaño, un array es ideal por su acceso instantáneo por índice. Si en cambio se van a insertar y borrar elementos con frecuencia en cualquier punto, una lista enlazada facilita esas operaciones. Si el orden de procesamiento importa, se elige según el criterio necesario: una pila cuando lo último en llegar debe atenderse primero, como al deshacer acciones, o una cola cuando lo primero en llegar debe atenderse primero, como al procesar tareas en orden. Si los datos son jerárquicos, como una estructura de carpetas o una organización por niveles, un árbol encaja naturalmente. Y si lo que se modela son relaciones arbitrarias entre elementos, como conexiones entre personas o rutas entre lugares, un grafo es lo adecuado. La recomendación práctica es preguntarse qué se va a hacer más: buscar, insertar, borrar, recorrer en orden, acceder por posición o por clave, y elegir en consecuencia. Con la experiencia, esta elección se vuelve casi automática, pero incluso al principio, razonar sobre el perfil de operaciones lleva a decisiones acertadas y evita el error común de usar siempre la misma estructura para todo por costumbre.

El nivel de dominio de estructuras de datos y algoritmos que se necesita depende del tipo de trabajo y del proceso de selección, pero en general se trata de conocimientos fundamentales que conviene tener, con matices según el contexto. Por un lado, para el trabajo diario de muchos programadores, especialmente en desarrollo de aplicaciones y web, no hace falta implementar desde cero estructuras complejas ni algoritmos sofisticados, porque los lenguajes y las bibliotecas ya proporcionan implementaciones eficientes y bien probadas de arrays, listas, mapas y demás. Sin embargo, sí es muy importante entender cómo funcionan esas estructuras y cuál conviene usar en cada caso, así como tener una noción práctica de la eficiencia, porque esa comprensión es lo que permite escribir código que escala bien, diagnosticar por qué un programa correcto es demasiado lento y tomar buenas decisiones de diseño. En ese sentido, el conocimiento conceptual y práctico de estructuras de datos y algoritmos es realmente útil y diferencia a un programador competente. Por otro lado, en los procesos de selección de muchas empresas, sobre todo de las más grandes y de perfil técnico, las entrevistas suelen incluir problemas de algoritmos y estructuras de datos en los que se pide resolver un problema y razonar sobre su complejidad, por lo que para acceder a esos puestos sí conviene preparar específicamente este tema y practicar la resolución de problemas. La recomendación equilibrada es, por tanto, adquirir una buena comprensión de las estructuras fundamentales, de los algoritmos básicos y de la notación de complejidad, suficiente para usarlas con criterio en el trabajo real y para razonar sobre eficiencia, y complementarla con práctica de resolución de problemas si se aspira a puestos cuyos procesos de selección lo exigen. En cualquier caso, se trata de conocimientos que enriquecen a cualquier programador y que rara vez sobran, por lo que invertir en ellos suele valer la pena, sin necesidad de convertirlo en una obsesión.