Estructuras de datos
TAD, recursividad, complejidad, listas, pilas, colas, heaps, hash, árboles y grafos implementados en Java con invariantes y pruebas.
- TAD y complejidad
- Estructuras lineales
- Árboles y hash
- Grafos y recorridos
- 12
- secciones
- 36
- lecciones
- 36
- ejercicios resueltos
Avanza una sección
a la vez.
Empieza por la primera y continúa en orden. Cada sección incluye tres lecciones, ejemplos claros y respuestas desplegables.
Java, TAD y contratos
El modelo de Java necesario para distinguir interfaz, implementación y representación; referencias, genéricos, composición e invariantes de un tipo abstracto de datos.
- Java y referencias
- TAD, interfaz e invariante
- Genéricos e Iterable
Recursividad y pila de llamadas
Caso base, reducción del problema, registros de activación y diseño de soluciones recursivas correctas antes de escribir código.
- Caso base y progreso
- Pila de llamadas
- Recursión sobre arreglos y nodos
Eficiencia y notación Big O
Cómo contar operaciones, reconocer órdenes de crecimiento y comparar tiempo, memoria y costo amortizado con entradas de distinto tamaño.
- Tiempo y espacio
- Big O
- Costo amortizado
Arreglos y listas enlazadas
Representaciones contigua y enlazada, nodos, recorridos, inserción, eliminación e iteradores con sus costos y casos frontera.
- Arreglo dinámico
- Lista enlazada
- Iteradores y elección
Pilas: último en entrar, primero en salir
El contrato LIFO, push, pop y peek; implementaciones con arreglo o nodos y aplicaciones como deshacer, llamadas y validación de delimitadores.
- LIFO y operaciones
- Implementaciones
- Aplicaciones de Stack
Colas y arreglos circulares
El contrato FIFO, frente y final; por qué desplazar elementos es costoso y cómo los índices circulares reutilizan el arreglo sin mover datos.
- FIFO
- Cola enlazada
- Buffer circular
Heaps y colas de prioridad
Propiedad del heap, representación en arreglo, ascenso y descenso para priorizar trabajo sin ordenar toda la colección.
- Heap binario
- Subir y bajar
- PriorityQueue
Tablas hash y diccionarios
Funciones hash, factor de carga, colisiones, direccionamiento abierto, encadenamiento y el contrato entre equals y hashCode.
- Tabla hash y factor de carga
- Colisiones
- Map y claves seguras
Árboles y recorridos
Raíz, nodos, altura y subárboles; recorridos preorden, inorden, postorden y por niveles relacionados con recursión, pila y cola.
- Árbol binario
- DFS en árboles
- Recorrido por niveles
Árboles binarios de búsqueda
Invariante de orden, búsqueda, inserción, eliminación en sus tres casos y efecto de la altura sobre el rendimiento.
- Invariante ABB
- Buscar e insertar
- Eliminar y balancear
Grafos y representaciones
Vértices, aristas, dirección y peso; matrices frente a listas de adyacencia y modelado de redes reales sin perder semántica.
- Vértices y aristas
- Matriz de adyacencia
- Lista de adyacencia
DFS, BFS y proyecto final
Recorridos en profundidad y amplitud, componentes conexas en grafos no dirigidos, caminos mínimos sin peso y una biblioteca Java comprobada mediante invariantes, pruebas y mediciones.
- DFS
- BFS
- Proyecto y pruebas