Tutoría 2: Implementación de Array 2D Disperso y Listas Doblemente Enlazadas

Resumen Ejecutivo

Esta sesión se centra en la resolución de un simulacro de examen de nivel avanzado, abordando la implementación eficiente de una estructura de datos compleja. Se desarrolla paso a paso la clase SparseArray (Array Disperso) utilizando una lista doblemente enlazada, donde solo se almacenan los valores distintos de cero para optimizar memoria. Además, se profundiza en la lógica de manipulación de punteros (prev y next) para operaciones de inserción, actualización y borrado de nodos.

Conceptos Clave

Array Disperso (Sparse Array): Estructura que contiene una gran cantidad de elementos con valor cero, por lo que su almacenamiento tradicional es ineficiente.
Lista Doblemente Enlazada: Estructura de datos dinámica donde cada nodo tiene referencia al elemento anterior (prev) y al posterior (next) [190.22s].
TAD (Tipo Abstracto de Datos): Modelo lógico que define un conjunto de datos y las operaciones que se pueden realizar sobre ellos.
Manejo de Punteros: La lógica crítica para "saltar" o "bordear" nodos al eliminarlos de una lista [2862s].

Desarrollo del Temario

1. Normas de Examen y Definición del Problema

¡OJO AL DATO!: Para que el ejercicio se califique en un examen, es imprescindible respetar estrictamente los nombres de paquetes, clases y signaturas de métodos indicados en el enunciado.

Problema: Implementar un Array 2D Disperso de enteros.
Estrategia: Usar una lista doblemente enlazada. Los nodos de la lista representan únicamente los elementos del array con valores distintos de cero.
Paquete: exam | Clase: SparseArray.

2. Estructura del Nodo (`Node`)

Para implementar la lista, primero definimos el objeto que contendrá la información. A diferencia de una lista simple, este nodo necesita almacenar las coordenadas del array.

Atributos del Nodo:
- row (Fila): Índice vertical.
- col (Columna): Índice horizontal.
- value (Valor): El dato entero (distinto de cero).
- next: Puntero al siguiente nodo.
- prev: Puntero al nodo anterior [231.02s].

Nota de implementación: En el constructor del nodo, los punteros prev y next se inicializan a null [610.88s].

3. La Clase Principal (`SparseArray`)

Esta clase gestiona la lista y simula el comportamiento del array.

Atributos: * first: Referencia al principio de la lista. * rows y columns: Dimensiones máximas del array (usadas solo para validar índices, no para reservar memoria real). * noZeros: Contador de elementos distintos de cero (equivalente al size habitual).

Constructor: * Signatura: public SparseArray(Integer rows, Integer columns). * Lógica: Inicializa las dimensiones y pone el contador a cero y first a null.

4. Operación: Escribir Valor (`setValue`)

Esta es la operación más compleja, ya que implica lógica de búsqueda, actualización e inserción.

Signatura: public boolean setValue(Integer row, Integer column, Integer value).

Lógica Paso a Paso: 1. Validación (Casos Base): Devuelve false si: * Los índices están fuera de rango (\(< 1\) o \(>\) dimensiones máximas). * El valor a insertar es 0 (los arrays dispersos no guardan ceros). 2. Búsqueda (Método Auxiliar): Se recomienda crear un método privado findNode(row, col) que recorra la lista y devuelva el nodo si existe en esas coordenadas [1447s]. 3. Actualización vs. Inserción: * Si el nodo existe: Se reemplaza el valor existente por el nuevo. * Si NO existe: Se crea un nuevo nodo y se inserta siempre en la primera posición (first).

Ejemplo de Inserción al Inicio: Si insertamos un nuevo nodo: 1. newNode.next apunta al antiguo first. 2. newNode.prev es null. 3. Si la lista no estaba vacía, el prev del antiguo first debe apuntar al newNode [2187s]. 4. first se actualiza apuntando al newNode.

5. Operación: Resetear Posición (`resetPosition`)

Esta operación equivale a asignar un valor 0 a una celda, lo que en términos de implementación significa eliminar el nodo de la lista.

Signatura: boolean resetPosition(Integer row, Integer column).

Lógica de Borrado de Nodos: Para eliminar un nodo, debemos hacer que sus vecinos se "ignoren" mutuamente, saltándose al nodo a borrar: 1. Búsqueda: Localizar el nodo objetivo. 2. Re-enlazado (Bypassing): * El next del nodo anterior debe apuntar al next del nodo actual. * El prev del nodo siguiente debe apuntar al prev del nodo actual. * Analogía: "Hacer que te bordeen o te salten" [2862s].

Casos Especiales: * Eliminar el primero (first): Si el nodo a borrar es first, actualizamos first para que apunte a first.next y ponemos su prev a null [2819s]. * Eliminar el último: El nodo anterior simplemente debe apuntar a null como su siguiente.

6. Operaciones de Lectura (`getValue` y `toString`)

getValue: Busca el nodo. Si existe, devuelve su valor. Si no existe (o índices inválidos), devuelve null.
toString: Recorre la lista y genera una representación en cadena.
- Formato esperado: [row=X, col=Y, value=Z] para cada nodo.
- Si está vacío: [Zero array].

7. Ejercicio Adicional (Listas Doblemente Enlazadas Genéricas)

El profesor introdujo brevemente un tercer ejercicio sobre una clase DoubleLinkedList con nodos de tres atributos (dato, siguiente, anterior) [3474s]. * Nota: La explicación de los métodos de borrado (delete) se volvió confusa hacia el final de la clase. El profesor recomendó plantear las dudas específicas sobre la gestión de punteros en la cola y cabecera a través del foro [4615s].

Preguntas de Autoevaluación

¿Por qué es más eficiente usar una lista enlazada para un array disperso en lugar de una matriz estándar int[][]?
En la operación setValue, ¿qué sucede si intentamos escribir el valor 0 en una posición válida?
Describe la secuencia de cambios de punteros necesaria para insertar un nodo al principio de una lista doblemente enlazada no vacía.
Si eliminamos un nodo que está en medio de la lista (ni el primero ni el último), ¿cuántos punteros de otros nodos debemos actualizar?
¿Qué valor devuelve el método getValue si pedimos una coordenada (f, c) que no ha sido guardada previamente en la lista?