Cargando aplicación...
Preparando tu experiencia meskeIA
Explora arrays, pilas, colas, listas enlazadas y árboles binarios con animaciones interactivas
| Estructura | Acceso | Búsqueda | Inserción | Eliminación |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Lista Enlazada | O(n) | O(n) | O(1)* | O(1)* |
| BST | O(log n) | O(log n) | O(log n) | O(log n) |
* O(1) si se tiene referencia al nodo. BST: casos promedio, puede degradar a O(n) si no está balanceado.
Conceptos fundamentales para programadores
| Estructura | Acceso | Búsqueda | Inserción | Eliminación | Memoria | Uso típico |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) continua | Acceso por índice, cache-friendly |
| Lista Enlazada | O(n) | O(n) | O(1)* | O(1)* | O(n) + punteros | Inserciones/eliminaciones frecuentes |
| Pila (Stack) | O(n) | O(n) | O(1) | O(1) | O(n) | Deshacer, recursión, expresiones |
| Cola (Queue) | O(n) | O(n) | O(1) | O(1) | O(n) | BFS, procesamiento en orden |
| Árbol BST | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Búsqueda ordenada, rangos |
| Hash Table | O(1) amort. | O(1) amort. | O(1) amort. | O(1) amort. | O(n) dispersa | Diccionarios, cachés, índices |
| Grafo | O(1) | O(V+E) | O(1) | O(V+E) | O(V+E) | Redes, rutas, relaciones |
* O(1) si se tiene referencia directa al nodo. BST casos promedio; puede degradar a O(n) sin balanceo.
El historial usa una Pila (Stack): cada página visitada se apila, el botón atrás hace pop. Las pestañas abiertas usan una lista doblemente enlazada.
Google usa tablas hash invertidas: palabra → lista de URLs. Con 50.000M páginas, la búsqueda es O(1) en lugar de O(n).
A* usa una Cola de Prioridad (heap). En un mapa 1000×1000 con obstáculos, encuentra el camino óptimo en <10ms.
Dijkstra sobre un grafo de 300M nodos (red de carreteras de Europa) encuentra la ruta óptima. LinkedIn representa conexiones como grafo no dirigido ponderado.
Array cuando: acceso por índice frecuente (cache-friendly), tamaño conocido, pocas inserciones en medio. Lista cuando: inserciones/eliminaciones frecuentes en cualquier posición, tamaño desconocido. En la práctica, los arrays casi siempre ganan por localidad de caché.
Con mala función hash, muchas claves colisionan en el mismo bucket → lista enlazada → O(n) en peor caso. Solución: rehashing cuando el factor de carga supera 0,75.
Un BST degenerado (insertar 1,2,3,4,5 en orden) se convierte en lista enlazada: O(n) búsqueda. AVL y Red-Black Trees garantizan O(log n) mediante rotaciones automáticas.
Stack: LIFO (Last In, First Out) — como una pila de platos. Queue: FIFO (First In, First Out) — como una cola del supermercado. Stack para llamadas de función, deshacer. Queue para procesamiento en orden, BFS.
Heap: cuando solo necesitas el máximo/mínimo rápidamente (O(1) peek, O(log n) insert/delete). BST: cuando necesitas búsqueda por valor arbitrario O(log n). Priority Queue implementa Heap.
El espacio de memoria que usa la estructura. Lista enlazada necesita O(n) nodos + punteros (overhead ×2 vs array). En sistemas embebidos o con millones de objetos, este overhead puede ser crítico.
BFS (Cola): encuentra el camino más corto en grafos no ponderados. Usa O(n) memoria (guarda nivel completo). DFS (Stack/Recursión): explora profundidad, usa menos memoria O(h) donde h es la altura. DFS para detectar ciclos, componentes conexos.
Una función hash sin colisiones para un conjunto conocido de claves. Posible cuando las claves son fijas (ej: palabras clave de un lenguaje de programación). gperf genera tablas hash perfectas mínimas.
Por índice → Array. Por clave → Hash Table. Secuencialmente → Lista. Jerárquicamente → Árbol.
Búsqueda O(1) → Hash Table. Búsqueda ordenada → BST. Inserción/eliminación → Lista. Min/max → Heap.
Jerárquicas (padre-hijo) → Árbol. Muchos-a-muchos → Grafo. Secuenciales → Array/Lista.
Limitada → Array (sin overhead de punteros). Sin límite → Lista, Árbol.
Sí, total → BST o Array ordenado. Sí, parcial (min/max) → Heap. No → Hash Table.
Inserciones frecuentes en medio → Lista. Pocas inserciones, muchas lecturas → Array. Dinámico con búsqueda → BST balanceado.
Python: list (array dinámico), dict (hash table), heapq (heap). Java: ArrayList, HashMap, TreeMap. C++: vector, unordered_map, priority_queue.
Arrays son 5-10x más rápidos que listas enlazadas para iteración secuencial por localidad de caché. Prefiere arrays salvo que las inserciones en medio sean críticas.
Mantén el factor de carga de Hash Tables entre 0,6-0,75. Sobre 0,8, las colisiones degradan el rendimiento a O(n).
Nunca implementes BST sin balanceo en producción. Usa TreeMap (Java), SortedDict (Python sortedcontainers) o equivalente.
Para eliminación O(1) cuando tienes el nodo (LRU Cache usa HashMap + Lista doblemente enlazada). Sola, la lista enlazada rara vez es óptima.
Los problemas reales usan combinaciones: HashMap<String, BST> para búsqueda de rango por clave, o Array of Linked Lists para hash table con chaining.
La complejidad teórica asume distribución uniforme. Mide con tus datos reales: un HashMap puede ser más lento que un Array pequeño por el overhead de hashing.