Skip to content

Tema 3: Estructuras de Datos Lineales

Resumen Ejecutivo

En esta sesión se introdujo el concepto de TAD Lista (Tipo Abstracto de Datos), diferenciándolo de las implementaciones concretas. El núcleo de la clase fue la programación "desde cero" de una Lista Enlazada en Java, detallando la lógica de punteros (referencias) para operaciones de inserción (add) y borrado (delete). Finalmente, se comparó el rendimiento (\(O(n)\) vs \(O(1)\)) entre ArrayList y LinkedList dentro del Java Collections Framework.

Conceptos Clave

  • TAD Lista: Colección homogénea y ordenada (secuencialmente, no necesariamente por valor) donde los elementos pueden repetirse.
  • Nodo: Objeto contenedor que almacena un dato y una referencia (enlace) al siguiente nodo .
  • Lista Enlazada (Linked List): Estructura dinámica formada por una secuencia de nodos. Puede ser simple, doble o circular.
  • Java Collections Framework (JCF): Biblioteca de Java que proporciona implementaciones optimizadas de estructuras de datos (como ArrayList y LinkedList).

Desarrollo del Temario

1. El TAD Lista: Definición y Necesidad

Una lista es una colección donde el orden hace referencia a la posición relativa (primero, segundo, tercero), no necesariamente al valor del dato (\(1 < 2 < 3\)).

  • Ejemplos Reales: Playlist de música, historial de navegación, pestañas del navegador .
  • Operaciones Básicas:
    • Inicializar(): Crear lista vacía.
    • Añadir(elemento): Insertar al final.
    • Borrar(elemento/posición): Eliminar nodos.
    • Obtener(posición): Acceso al dato.
    • Localizar(elemento): Buscar índice .

Nota del Profesor: En la teoría no me paro mucho, prefiero centrarme en la práctica porque es en lo que se basará el examen. .

2. Listas Enlazadas: Estructura Interna

A diferencia de los arrays (listas estáticas), las listas enlazadas son dinámicas (su tamaño varía en ejecución).

  • Componentes: Se componen de una secuencia de nodos.
  • El Nodo: Tiene dos partes fundamentales:
    1. Dato: La información almacenada (String, int, objeto).
    2. Referencia (Next): Apunta al siguiente nodo de la secuencia. El último nodo apunta a null .

Tipos de Listas Enlazadas:

  1. Simplemente enlazada: Cada nodo tiene una referencia al siguiente.
  2. Doblemente enlazada: Cada nodo tiene referencia al siguiente (next) y al anterior (prev).
  3. Circular: El último nodo conecta de nuevo con el primero, cerrando el ciclo.

3. Implementación en Java (¡OJO AL DATO!)

Esta sección fue el foco principal de la clase práctica. Se explicó cómo Java maneja las referencias (que actúan como punteros pero no lo son estrictamente como en C).

A. Clase Node

Se define una clase auxiliar Node. Los atributos se dejan con visibilidad de paquete (sin private) para facilitar el acceso desde la clase Lista.

class Node {
    String data; // El dato
    Node next;   // La referencia al siguiente

    Node(String str){
        data = str;
        next = null; // Al crearse, no apunta a nada aún
    }
}

B. Clase StringList (La Lista)

Se utilizan dos referencias para controlar la lista:

  • first: Apunta al primer nodo.
  • last: Apunta al último nodo (para optimizar la inserción al final) .

C. Lógica del Método add(String str)

El objetivo es añadir un elemento al final.

  1. Crear el nuevo nodo: Node node = new Node(str);.
  2. Caso Lista Vacía (first == null): Tanto first como last deben apuntar al nuevo nodo .
  3. Caso Lista NO Vacía:
    • El actual último (last.next) debe apuntar al nuevo nodo.
    • Actualizamos la referencia last para que sea el nuevo nodo .

D. Lógica del Método delete(int index) (Complejo)

El profesor dedicó gran parte de la clase a depurar este método. La lógica crítica es situarse en el nodo anterior al que queremos borrar.

Pasos Lógicos:

  1. Validación: Si la lista está vacía (first == null), no se puede borrar.
  2. Borrar el Primero (index == 0):
    • Hacemos first = first.next.
    • Caso borde: Si la lista queda vacía tras borrar, hay que actualizar last = null.
  3. Borrar en Medio o Final:
    • Usamos un bucle while para avanzar un puntero actual hasta la posición index - 1 (el nodo previo).
    • Operación de borrado: actual.next = actual.next.next; (Saltamos el nodo a borrar, enlazando el anterior con el siguiente del siguiente).
    • Caso borde: Si borramos el último, debemos actualizar last para que apunte al nodo actual (el penúltimo).

Explicación Verbal: "Para eliminar el nodo, básicamente decimos que el next del anterior ya no apunte a ese nodo, sino al siguiente. Así, la lista 'se olvida' del nodo intermedio y este desaparece.".

4. Java Collections Framework (JCF)

Es una biblioteca que nos da estas estructuras ya implementadas. Las dos principales para listas son:

Comparativa: ArrayList vs. LinkedList

El profesor enfatizó saber cuándo usar cuál basándose en la eficiencia (Big O notation).

Característica ArrayList LinkedList
Implementación Array dinámico (redimensionable). Lista doblemente enlazada.
Acceso Aleatorio (get) Muy Rápido \(O(1)\) (es un array). Lento \(O(n)\) (hay que recorrer).
Insertar/Borrar al Final Rápido (salvo si hay que redimensionar). Muy Rápido \(O(1)\).
Insertar/Borrar en Medio Lento \(O(n)\) (desplaza elementos). Lento \(O(n)\) (busca posición) pero rápido al enlazar.
Uso de Memoria Eficiente, pero puede tener huecos. Mayor consumo (guarda dato + 2 referencias).

Consejo de Examen: "Es importante saber seleccionar la colección adecuada según el problema que se quiere resolver." Si necesitas mucho acceso aleatorio, usa ArrayList. Si insertas mucho en extremos, usa LinkedList.

Preguntas de Autoevaluación

  1. ¿Cuál es la diferencia fundamental entre una referencia null y una lista vacía en la implementación de StringList?

    • Respuesta: Una lista vacía es un objeto StringList donde sus atributos first y last apuntan a null. Una referencia null a la lista significa que el objeto lista ni siquiera ha sido instanciado.

  2. Al implementar el método delete(int index), ¿por qué es necesario iterar hasta index - 1 y no hasta index?

    • Respuesta: Porque en una lista simplemente enlazada solo podemos avanzar. Para borrar un nodo, necesitamos modificar el puntero next del nodo anterior para que salte el nodo objetivo.

  3. Si estás diseñando un sistema de historial de navegación donde solo necesitas volver atrás (acceder al último visitado) y añadir nuevas páginas, ¿Qué estructura del JCF es más eficiente y por qué?

    • Respuesta: LinkedList (o Stack), ya que las operaciones de inserción y eliminación se realizan principalmente en los extremos, lo cual es \(O(1)\), mientras que el acceso aleatorio no es prioritario.

  4. Verdadero o Falso: En Java, un Nodo es un tipo de dato primitivo.

    • Respuesta: Falso. Un Nodo es un Objeto (tipo referenciado). null se puede asignar a un Nodo, pero no a un primitivo como int .

  5. ¿Qué complejidad temporal \(O(n)\) tiene el método get(int index) en una LinkedList y por qué?

    • Respuesta: Tiene complejidad \(O(n)\) (lineal), porque para acceder a la posición \(n\), el programa debe recorrer secuencialmente todos los nodos desde el primero (first) hasta llegar al deseado, a diferencia del acceso directo de un array.