TAD Lista: Estáticas, Dinámicas y Enlazadas
Respondé todas las preguntas y presioná Calificar para ver tu puntaje.
Respuesta correcta: El TAD define el contrato lógico (qué operaciones se pueden hacer y sus pre/postcondiciones); la Estructura de Datos es la implementación física en memoria (cómo se almacenan y enlazan los bytes).
¿Por qué? Un TAD es una especificación matemática abstracta independiente del lenguaje. La estructura de datos concreta es la decisión técnica de implementación (por ejemplo, implementar el TAD Lista mediante un arreglo contiguo o una lista enlazada con nodos).
primero
Respuesta correcta: Verdadero
¿Por qué? Verdadero. Solo requiere instanciar el nuevo nodo, hacer que apunte al actual primero y actualizar primero para que apunte al nuevo nodo, sin importar cuántos elementos tenga la lista.
obtener(i)
Respuesta correcta: O(N) en el peor y caso promedio, ya que se debe recorrer secuencialmente la cadena de punteros desde la cabeza hasta la posición i.
¿Por qué? A diferencia de un arreglo contiguo donde la posición de memoria se calcula directamente como base + i * tamaño, en una lista enlazada los nodos están dispersos en el Heap, obligando a recorrerlos uno a uno a través de sus referencias.
base + i * tamaño
¿Por qué? Verdadero. Si primero hiciéramos que A apunte al nuevo nodo antes de enlazarlo con B, perderíamos la referencia a B y al resto de la lista (Memory Leak o referencia huérfana).
ArrayList
LinkedList
Respuesta correcta: El arreglo contiguo tiene mucho menor overhead de memoria por elemento, ya que no necesita almacenar punteros de referencia extra por cada nodo ni crear un objeto envoltorio por cada celda.
¿Por qué? Cada nodo en una lista enlazada requiere memoria extra para el puntero a la siguiente posición (y anterior si es doblemente enlazada), además del encabezado de objeto de la JVM, generando un overhead sustancial comparado con un arreglo contiguo.
¿Por qué? Verdadero. Esto permite recorrer la lista en ambos sentidos (hacia adelante y hacia atrás) y realizar eliminaciones en O(1) cuando ya se tiene la referencia directa al nodo a eliminar.
Nodo<T>
private static class
Respuesta correcta: Para evitar que el código cliente dependa de los detalles de implementación interna de los nodos, preservando el principio de encapsulamiento del TAD.
¿Por qué? El usuario del TAD Lista solo debe interactuar con los métodos del contrato (agregar, obtener, eliminar). La existencia y manejo de los nodos es un detalle privado de implementación que no debe exponerse.
agregar
obtener
eliminar
null
siguiente
Respuesta correcta: Falso
¿Por qué? Falso. En una lista circular, el último nodo apunta de regreso al primer nodo de la lista, formando un ciclo continuo sin ningún puntero a null.
Respuesta correcta: Eliminar el nodo cabeza (índice 0), ya que requiere actualizar la referencia principal primero de la lista.
¿Por qué? Eliminar la cabeza no tiene un "nodo anterior" que reconectar; la referencia raíz de la estructura (primero) debe actualizarse directamente para apuntar a primero.siguiente. Si la lista queda vacía, primero pasa a ser null.
primero.siguiente
¿Por qué? Verdadero. Por ejemplo, en una lista enlazada, que el atributo tamano refleje con exactitud la cantidad de nodos alcanzables desde primero es un invariante fundamental de integridad.
tamano
Puntaje: