Una estructura de datos es una forma de organizar los datos en memoria para que las operaciones que necesitas sean baratas. Arreglos, listas, tablas hash y árboles guardan los mismos elementos; se distinguen en lo rápido que los encuentran, insertan, borran u ordenan. Elegir bien suele importar más que cualquier microoptimización.
Conceptos clave
- Tipo abstracto de datos e implementación: una pila o un mapa es una interfaz; los arreglos o los nodos enlazados son maneras de construirla.
- Memoria contigua o enlazada: los arreglos aprovechan la caché y se indexan en tiempo constante; los nodos enlazados insertan barato pero obligan a seguir punteros.
- Hashing: una función hash lleva una clave a una posición; las colisiones se resuelven con encadenamiento o sondeo.
- Árboles balanceados: mantener un árbol de búsqueda poco profundo da búsqueda, inserción y borrado logarítmicos.
- Montículos y colas de prioridad: acceso rápido al elemento menor o mayor.
Vocabulario
- Coste amortizado: el coste medio por operación en una secuencia larga, como cuando un arreglo dinámico se duplica.
- Factor de carga: la razón entre los elementos guardados y las posiciones de una tabla hash.
- Invariante: una propiedad que la estructura mantiene tras cada operación, como el orden del montículo.
- Estructura persistente: la que conserva disponibles las versiones antiguas tras una actualización.
Qué estudiar, en orden
- Construye un arreglo dinámico y una lista enlazada simple; mide el tiempo de insertar al principio y al final.
- Implementa una tabla hash con encadenamiento, luego redimensiónala y observa el factor de carga.
- Implementa un árbol binario de búsqueda y después una variante balanceada, como un AVL o un rojo-negro.
- Construye un montículo binario y úsalo para una cola de prioridad y para heapsort.
- Mira los conjuntos disjuntos, los tries y los árboles B, y pregúntate qué hace rápido cada uno.