Facundo Uferer
1. ¿Qué es un TAD? La Interfaz Frente a la Memoria
Un Tipo Abstracto de Dato (TAD) define QUÉ operaciones se pueden hacer (contrato lógico), mientras que la estructura de datos define CÓMO se organizan los bytes en la RAM (implementación física).
// El cliente declara la interfaz TAD
List<String> lista = new ArrayList<>();
// O cambia la implementación física sin romper nada:
List<String> lista = new LinkedList<>();2. Memoria Contigua vs Nodos Dispersos en el Heap
En un array, las casillas son adyacentes: saltar al índice 3 se calcula matemáticamente en O(1). En una lista enlazada, los nodos están desparramados en direcciones aleatorias del Heap: para llegar al índice 3 hay que caminar 3 punteros en O(N).
// Array: Aritmética de memoria directa
array[3]; // base + 3 * sizeof(elem) -> O(1)
// Lista Enlazada: Desreferenciar punteros
cabeza.siguiente.siguiente.siguiente; // O(N)3. Anatomía de un Nodo en Memoria
Un nodo es una clase autorreferencial en el Heap con dos compartimentos: la carga útil (dato) y el puntero al próximo nodo (siguiente). El último nodo de la cadena tiene su puntero en null (tierra).
class Nodo<T> {
T dato;
Nodo<T> siguiente; // Puntero al mismo tipo
public Nodo(T dato) {
this.dato = dato;
this.siguiente = null;
}
}4. Inserción al Inicio: El Baile de Punteros en O(1)
Insertar al frente es inmediato: 1. Crear nuevo nodo, 2. Enlazar nuevo.siguiente = cabeza, 3. Mover cabeza = nuevo. ¡Si invertís el orden de los pasos 2 y 3, perdés toda la lista existente!
public void agregarAlInicio(T dato) {
Nodo<T> nuevo = new Nodo<>(dato);
nuevo.siguiente = cabeza; // PASO 1: Enlazar primero
cabeza = nuevo; // PASO 2: Mover cabeza
}5. Inserción al Final y Recorrido en O(N)
Para agregar al final sin puntero tail, es obligatorio recorrer toda la lista usando un cursor auxiliar mientras actual.siguiente != null. El costo es O(N) proporcional a la cantidad de elementos.
Nodo actual = cabeza;
while (actual.siguiente != null) {
actual = actual.siguiente; // Avanza O(N)
}
actual.siguiente = nuevo;6. Eliminación Intermedia: El Puente de Punteros
Para quitar un nodo intermedio, la flecha del nodo anterior se desvía y conecta directamente con el siguiente: anterior.siguiente = actual.siguiente. Al no tener referencias entrantes, el nodo eliminado es limpiado por el Garbage Collector.
anterior.siguiente = actual.siguiente;
actual.siguiente = null; // Limpieza defensiva
// El recolector de basura (GC) destruye el nodo huérfano7. Variantes: Doblemente Enlazada y Circular
La lista doblemente enlazada agrega un puntero `anterior` en cada nodo permitiendo recorridos bidireccionales y eliminación en O(1) conociendo el nodo. La lista circular enlaza el último nodo de vuelta a la cabeza.
class NodoDoble<T> {
T dato;
NodoDoble<T> anterior;
NodoDoble<T> siguiente;
}8. Tabla de Complejidad Big-O: Array vs Lista
Elegir la estructura correcta depende del patrón de uso. Si hacés muchas lecturas por índice aleatorio, el Array es el rey. Si hacés inserciones y eliminaciones continuas al frente, la Lista Enlazada no tiene rival.
// El 95% de los casos en Java se resuelven con ArrayList
// debido a la localidad espacial y caché L1/L2.