Estructuras de datos
Algoritmos6 algoritmos · 12 ejercicios corregidos · código en Java, Python, JavaScript, C# y PHP
Un algoritmo rápido sobre una estructura mal elegida sigue siendo lento. Buscar en una lista es O(n); en una tabla hash, O(1). Sacar el mínimo de un array desordenado es O(n); de un montículo, O(log n). Elegir bien dónde guardas los datos suele importar más que cómo los recorres.
Las colecciones de Java (ArrayList, LinkedList, HashMap, TreeMap, ArrayDeque, PriorityQueue), de Python o de C# son estas estructuras ya programadas. Programarlas una vez a mano es la mejor forma de entender qué coste tiene cada operación y por qué.
Los algoritmos
Árbol binario de búsqueda
Un árbol donde cada nodo tiene a la izquierda los valores menores y a la derecha los mayores: buscar, insertar y borrar en O(log n) si está equilibrado, y recorrerlo en orden da los datos ordenados.intermedio2 ejerciciosPila (stack)
Una colección en la que solo se mete y se saca por arriba: el último que entra es el primero que sale (LIFO). Deshacer, el botón «atrás», la pila de llamadas o comprobar paréntesis.básico2 ejerciciosCola (queue)
Una colección en la que se entra por el final y se sale por el principio: el primero que llega es el primero que sale (FIFO). Colas de impresión, de mensajes, de procesos o el recorrido en anchura.básico2 ejerciciosLista enlazada
Una secuencia de nodos en la que cada uno guarda un valor y una referencia al siguiente. Insertar o borrar en un punto ya localizado es O(1), sin mover nada; llegar a una posición cuesta O(n).intermedio2 ejerciciosTabla hash
Guarda pares clave-valor en un array: una función hash convierte la clave en una posición y buscar, insertar o borrar cuesta O(1) de media. Es lo que hay detrás de HashMap y dict.intermedio2 ejerciciosMontículo y cola de prioridad
Un árbol guardado en un array en el que cada padre es menor (o mayor) que sus hijos: el mínimo está siempre en la raíz y meter o sacar cuesta O(log n). Es la cola de prioridad de PriorityQueue.intermedio2 ejercicios
Cuál elegir
| Estructura | Insertar | Buscar | Borrar | En la biblioteca |
|---|---|---|---|---|
| Pila (stack) | O(1) arriba | O(n) | O(1) arriba | ArrayDeque, list, Stack<T> |
| Cola (queue) | O(1) al final | O(n) | O(1) al principio | ArrayDeque, deque, Queue<T> |
| Lista enlazada | O(1) si tienes el nodo | O(n) | O(1) si tienes el nodo | LinkedList, LinkedList<T> |
| Tabla hash | O(1) de media | O(1) de media | O(1) de media | HashMap, dict, Dictionary<K,V> |
| Árbol binario de búsqueda | O(log n)* | O(log n)* | O(log n)* | TreeMap, SortedDictionary |
| Montículo y cola de prioridad | O(log n) | O(1) el mínimo | O(log n) el mínimo | PriorityQueue, heapq |
* Si el árbol está equilibrado; uno degenerado (datos insertados en orden) se comporta como una lista: O(n).