Repasa referencias, genéricos y Big O. Los usarás para separar tamaño de capacidad y comparar operaciones.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Arreglo dinámico con Lista enlazada y resolver un caso nuevo.
Reserva entre 75 y 120 minutos o divide el laboratorio en dos sesiones.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Arreglo dinámico y Lista enlazada? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Relacionarás cada representación con las operaciones que favorece y comprobarás casos frontera mediante invariantes.
Al terminar podrás
- El arreglo ofrece índices rápidos, pero tiene capacidad separada del tamaño
- Una lista enlazada paga referencias para cambiar enlaces
- La operación dominante decide entre arreglo, lista y biblioteca estándar
01
Memoria contigua
El arreglo ofrece índices rápidos, pero tiene capacidad separada del tamaño
Un arreglo de Java tiene una longitud fija y ofrece acceso por índice en O(1); su organización física exacta es un detalle de la máquina virtual. Una colección dinámica mantiene cantidad de elementos y capacidad interna como valores distintos. Insertar en medio exige desplazar; crecer exige crear otro arreglo y copiar.
Índices válidos: 0 hasta size - 1.
size nunca supera capacity.
Las posiciones fuera del contenido no deben recorrerse como elementos.
¿Por qué usar datos.length en hasNext puede entregar null inesperados?
Mostrar respuesta ＋
Porque length representa capacidad, no cantidad de elementos almacenados. hasNext debe comparar con size.
02
Memoria enlazada
Una lista enlazada paga referencias para cambiar enlaces
Cada nodo contiene un valor y una referencia al siguiente. Acceder al índice i requiere avanzar desde la cabeza, pero insertar o eliminar al inicio cuesta O(1). El caso vacío y la eliminación de la cabeza merecen tratamiento explícito.
cabeza == null representa la lista vacía.
El último nodo apunta a null.
Un enlace perdido puede hacer inaccesible el resto.
¿Qué operación es O(1) en una lista simplemente enlazada pero O(n) en un arreglo?
Mostrar respuesta ＋
Insertar o eliminar al inicio: la lista cambia pocas referencias; el arreglo debe desplazar los elementos.
03
Elegir y recorrer
La operación dominante decide entre arreglo, lista y biblioteca estándar
ArrayList suele ser una buena opción general cuando importa indexar y recorrer. Una lista enlazada resulta educativa para comprender referencias, pero no garantiza mejor rendimiento práctico. Implementar un Iterator desacopla el recorrido; debe indicar agotamiento y definir qué pasa si la colección cambia.
No elijas por el nombre de la estructura.
Compara frecuencia de acceso, inserción y memoria.
En aplicaciones normales prefiere java.util salvo un requisito especial.
¿Cuándo tiene valor implementar tu propia lista?
Mostrar respuesta ＋
Para aprender invariantes, para un requisito muy específico o para investigación. En producción normalmente conviene una colección estándar probada.
Tu recorrido en tres ideas
- El arreglo ofrece índices rápidos, pero tiene capacidad separada del tamaño
- Una lista enlazada paga referencias para cambiar enlaces
- La operación dominante decide entre arreglo, lista y biblioteca estándar
Audita dos implementaciones de Colección<T>
Conecta representación, invariantes, iteradores, casos frontera y costo real de cada operación.
CASO
Una versión usa arreglo con capacidad y otra nodos; ambas contienen fallos al recorrer, buscar y eliminar.
Procedimiento
- Escribe los invariantes y pruebas que fallen antes de cambiar código.
- Corrige tamaño, límites, avance de referencias y agotamiento del iterador.
- Compara acceso, inserción y recorrido con tamaños crecientes.
Evidencia mínima
- Pruebas que fallen antes de corregir y pasen después.
- Invariantes comprobados tras cada modificación.
- Tabla de complejidad y medición coherente.
Mostrar razonamiento modelo ＋
El arreglo debe iterar hasta size, no capacity. En la lista, cada rama que continúa debe actualizar el nodo actual. La corrección se demuestra antes de discutir qué implementación es más rápida.
Para ir más lejos¿Qué cambia si permites modificaciones durante la iteración?
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Recorrer la capacidad completa en vez del tamaño lógico.
Perder un enlace al cambiar referencias en el orden equivocado.
Ahora hazlo sin guía
Implementa addFirst, addLast, get y remove en una lista genérica con size e iterador.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Cubre vacía, cabeza, medio y cola.
- El iterador termina en size real.
- Verifica invariantes después de cada modificación.