Contexto
Un Tipo Abstracto de Datos (TAD) define un modelo matemático de comportamiento: qué operaciones pueden realizarse sobre los datos y qué contratos deben cumplirse, sin prescribir cómo se almacenan físicamente en la memoria.
Una lista puede implementarse mediante un arreglo contiguo en memoria (lista estática o dinámica contigua) o mediante bloques dispersos interconectados por referencias (lista enlazada). La comprensión profunda de cómo se manipulan los nodos enlazados es la base fundamental para dominar estructuras más complejas como árboles y grafos.
Consigna
Vas a implementar desde cero una Lista Simplemente Enlazada Genérica, sin utilizar ninguna clase del paquete java.util.
1. Especificación del TAD Lista
Lista.java:public interface Lista<T> { void agregarAlFinal(T elemento); void insertarEn(int indice, T elemento); T obtener(int indice); T eliminarEn(int indice); int longitud(); boolean estaVacia(); void limpiar(); }
2. Implementación de ListaEnlazada
- Estructura del Nodo:
- Clase estática privada
private static class Nodo<E>dentro deListaEnlazada<T>para no filtrar detalles de implementación hacia afuera. - Atributos:
E dato;yNodo<E> siguiente;.
- Clase estática privada
- Invariantes de Clase:
private Nodo<T> primero;(referencia al primer nodo onullsi está vacía).private int tamano;(cantidad de elementos contenidos).- En todo momento, recorrer desde
primerohasta encontrarnulldebe contabilizar exactamentetamanonodos.
- Lógica de Operaciones:
insertarEn(int indice, T elemento):- Validación:
if (indice < 0 || indice > tamano) throw new IndexOutOfBoundsException();. - Si
indice == 0: el nuevo nodo apunta al actualprimero, yprimeropasa a ser el nuevo nodo. - Si
indice > 0: se avanza hasta el nodo en posiciónindice - 1, se reconectan los punteros (nuevoNodo.siguiente = anterior.siguiente; anterior.siguiente = nuevoNodo;). - Incrementa
tamano.
- Validación:
eliminarEn(int indice):- Validación:
if (indice < 0 || indice >= tamano) throw new IndexOutOfBoundsException();. - Si
indice == 0: se guarda el dato deprimero,primero = primero.siguiente;, decrementatamanoy retorna el dato. - Si
indice > 0: se busca el nodo anterior, se desconecta el nodo objetivo (anterior.siguiente = anterior.siguiente.siguiente;), decrementatamanoy retorna el dato.
- Validación:
obtener(int indice): avanza hasta el nodo solicitado y retorna su dato.toString(): genera la cadena[elem1 -> elem2 -> null].
3. Programa de Verificación en MainLista
En MainLista.java:
- Instanciá
ListaEnlazada<Integer>. - Agregá elementos y mostrá el estado de la lista.
- Insertá en posición 0 (caso borde: nueva cabeza).
- Insertá en una posición intermedia.
- Eliminá el primer elemento y comprobá que la nueva cabeza sea el segundo.
- Intentá acceder a un índice fuera de rango dentro de un bloque
try-catchy verificá que se lanceIndexOutOfBoundsException.