Lista simplemente enlazada

Las estructuras de datos son fundamentales en programación. Una de las más básicas y útiles es la lista simplemente enlazada. En este artículo, exploraremos qué son las listas simplemente enlazadas, cómo implementarlas en Java y cómo pueden ser utilizadas en proyectos reales.

¿Qué son las Listas Simplemente Enlazadas?

Las listas simplemente enlazadas son una colección de elementos, llamados nodos, que están conectados de manera secuencial mediante enlaces. Cada nodo contiene un valor y una referencia (o enlace) al siguiente nodo en la secuencia. La característica clave es que los nodos solo conocen el siguiente nodo en la lista, lo que las hace eficientes para ciertas operaciones.

Implementación en Java

Vamos a explorar cómo implementar una lista simplemente enlazada en Java. Utilizaremos una clase ListaSimplementeEnlazada y una clase Nodo para representar los nodos individuales.

public class Nodo {
    public int dato;
    public Nodo siguiente;

    public Nodo(int dato) {
        this.dato = dato;
        this.siguiente = null;
    }
}

public class ListaSimplementeEnlazada {
    private Nodo head;
    private Nodo tail;

    // Constructor y métodos...
}

En la clase Nodo, definimos dos atributos: dato, que almacena el valor del nodo, y siguiente, que es una referencia al siguiente nodo en la lista. En la clase ListaSimplementeEnlazada, tenemos atributos head y tail, que representan el primer y último nodo de la lista, respectivamente.

Funcionalidades Básicas

Vamos a explorar algunas de las operaciones básicas que podemos realizar con nuestra lista simplemente enlazada.

Agregar Elementos

public void agregarAlFinal(int dato) {
    Nodo nuevoNodo = new Nodo(dato);
    if (this.isEmpty()) {
        agregarEnListaVacia(nuevoNodo);
        return;
    }
    tail.siguiente = nuevoNodo;
    tail = nuevoNodo;
}

public void agregarAlInicio(int dato) {
    Nodo nuevoNodo = new Nodo(dato);
    if (this.isEmpty()) {
        agregarEnListaVacia(nuevoNodo);
        return;
    }
    nuevoNodo.siguiente = head;
    head = nuevoNodo;
}

public void agregarEntreNodos(int dato, int datoAnterior, int datoSiguiente) {
    // Crear el nuevo nodo con el dato proporcionado
    Nodo nuevoNodo = new Nodo(dato);
    
    // Buscar el nodo anterior al nuevo nodo
    Nodo anterior = buscarNodo(datoAnterior);
    
    // Verificar si el nodo anterior existe
    if (anterior == null) {
        System.out.println("El nodo con el dato anterior no existe en la lista.");
        return;
    }
    
    // Verificar si el nodo anterior es el último nodo
    if (anterior == tail) {
        System.out.println("No se puede agregar entre el nodo anterior y el siguiente porque el nodo anterior es el último nodo en la lista.");
        return;
    }
    
    // Buscar el nodo siguiente al nuevo nodo
    Nodo siguiente = anterior.siguiente;
    
    // Verificar si el nodo siguiente existe
    if (siguiente == null || siguiente.dato != datoSiguiente) {
        System.out.println("El nodo con el dato siguiente no existe en la lista o no sigue al nodo anterior proporcionado.");
        return;
    }
    
    // Insertar el nuevo nodo entre los nodos anterior y siguiente
    anterior.siguiente = nuevoNodo;
    nuevoNodo.siguiente = siguiente;
}

Este código implementa tres métodos para agregar nodos a una lista simplemente enlazada en diferentes posiciones: al principio, al final y entre dos nodos existentes.

Método agregarAlFinal(int dato)

Este método agrega un nuevo nodo con el valor dato al final de la lista. Aquí está el análisis detallado:

1. Creación del Nuevo Nodo: Se crea un nuevo nodo con el valor dato.
2. Verificación de Lista Vacía: Se verifica si la lista está vacía usando el método isEmpty(). Si la lista está vacía, se llama al método agregarEnListaVacia(nuevoNodo) para manejar el caso especial de una lista vacía y luego se sale del método.
3. Asignación de Punteros: Si la lista no está vacía, el puntero siguiente del nodo tail (último nodo de la lista) se establece en el nuevo nodo, y luego tail se actualiza para que apunte al nuevo nodo, convirtiéndolo en el nuevo último nodo de la lista.

Método agregarAlInicio(int dato)

Este método agrega un nuevo nodo con el valor dato al inicio de la lista. Aquí está el análisis detallado:

1. Creación del Nuevo Nodo: Se crea un nuevo nodo con el valor dato.
2. Verificación de Lista Vacía: Se verifica si la lista está vacía usando el método isEmpty(). Si la lista está vacía, se llama al método agregarEnListaVacia(nuevoNodo) para manejar el caso especial de una lista vacía y luego se sale del método.
3. Asignación de Punteros: Si la lista no está vacía, el puntero siguiente del nuevo nodo se establece en el nodo head (primer nodo de la lista), y luego head se actualiza para que apunte al nuevo nodo, convirtiéndolo en el nuevo primer nodo de la lista.

Método agregarEntreNodos(int dato, int datoAnterior, int datoSiguiente)

Este método agrega un nuevo nodo con el valor dato entre dos nodos existentes cuyos valores son datoAnterior y datoSiguiente. Aquí está el análisis detallado:

1. Creación del Nuevo Nodo: Se crea un nuevo nodo con el valor dato.
2. Búsqueda del Nodo Anterior: Se busca el nodo con el valor datoAnterior utilizando el método buscarNodo(datoAnterior). Si no se encuentra el nodo anterior, se muestra un mensaje de error y se sale del método.
3. Verificación del Nodo Anterior como Último Nodo: Se verifica si el nodo encontrado es el último nodo de la lista. Si es así, se muestra un mensaje de error y se sale del método.
4. Búsqueda del Nodo Siguiente: Se busca el nodo con el valor datoSiguiente que sigue al nodo anterior. Si no se encuentra el nodo siguiente o si no sigue al nodo anterior, se muestra un mensaje de error y se sale del método.
5. Inserción del Nuevo Nodo: El nuevo nodo se inserta entre el nodo anterior y el nodo siguiente. El puntero siguiente del nodo anterior se establece en el nuevo nodo, y el puntero siguiente del nuevo nodo se establece en el nodo siguiente.

Búsqueda de un nodo dentro de la lista

public boolean buscar(int dato) {
    Nodo actual = head;
    while (actual != null) {
        if (actual.dato == dato) {
            return true;
        }
        actual = actual.siguiente;
    }
    return false;
}

Podemos buscar elementos en la lista que contengan un valor específico.

Eliminar un nodo de la lista

Este código implementa un método llamado eliminarNodo(int dato) en la clase ListaSimplementeEnlazada, que se encarga de eliminar un nodo de la lista que contenga el valor especificado en el parámetro dato. Aquí está el análisis detallado del código:

// Método para eliminar un nodo de la lista
public void eliminarNodo(int dato) {
    if (this.isEmpty()) { // Verificar si la lista está vacía
        return; // Si la lista está vacía, no hay nodos que eliminar
    }

    if (tail.dato == dato) { // Verificar si el último nodo contiene el dato a eliminar
        tail = tail.siguiente; // Si es así, mover el puntero de la cola al siguiente nodo
    }

    Nodo iterador = tail; // Inicializar un iterador desde el final de la lista
    Nodo anterior = null; // Inicializar un puntero que apuntará al nodo anterior al iterador
    if (head.dato == dato) { // Verificar si el nodo inicial es el que se va a eliminar
        head = head.siguiente; // Si es así, mover el puntero de la cabeza al siguiente nodo y terminar la ejecución
        return;
    }

    // Buscar el nodo con el valor especificado
    while (iterador != null && iterador.dato != dato) {
        anterior = iterador; // Avanzar el puntero anterior al siguiente nodo
        iterador = iterador.siguiente; // Avanzar el iterador al siguiente nodo
    }

    // Verificar si se llegó al final de la lista sin encontrar el valor especificado
    if (iterador == null) {
        System.out.println("El valor no existe dentro de la lista simplemente enlazada");
        return;
    }

    // Enlazar el nodo anterior al nodo siguiente, omitiendo el nodo a eliminar
    anterior.siguiente = iterador.siguiente;
}

Este método recorre la lista enlazada para buscar el nodo que contiene el valor dato a eliminar. Si el nodo a eliminar es el primer nodo (head), se actualiza el puntero head para apuntar al siguiente nodo y se detiene la ejecución del método. Si el nodo a eliminar es el último nodo (tail), simplemente se actualiza el puntero tail para que apunte al siguiente nodo, evitando así el nodo a eliminar.

Si el nodo a eliminar está en el medio de la lista, el método recorre la lista enlazada mientras mantiene un puntero al nodo anterior al nodo actual. Cuando se encuentra el nodo a eliminar, se enlaza el nodo anterior con el nodo siguiente, omitiendo así el nodo a eliminar de la lista.

Finalmente, si el valor especificado no se encuentra en la lista, se imprime un mensaje de error indicando que el valor no existe en la lista simplemente enlazada.

Aplicaciones en Proyectos Reales

Las listas simplemente enlazadas son ampliamente utilizadas en proyectos de software. Por ejemplo, pueden ser utilizadas en:

• Manejo de listas de reproducción en reproductores de música.
• Historial de navegación en navegadores web.
• Listas de tareas en aplicaciones de gestión de proyectos.

Conclusión

El manejo de memoria dinámica y el uso de estructuras de datos como las listas simplemente enlazadas son fundamentales en el desarrollo de software por varias razones importantes:

1. Eficiencia en el uso de la memoria: Las estructuras de datos como las listas simplemente enlazadas permiten asignar y liberar memoria de manera dinámica según sea necesario durante la ejecución del programa. Esto permite un uso más eficiente de la memoria, ya que solo se utiliza la cantidad necesaria de memoria en cualquier momento.
2. Flexibilidad en la manipulación de datos: Las listas simplemente enlazadas proporcionan una forma flexible de almacenar y manipular datos. Los nodos pueden ser insertados, eliminados o modificados fácilmente sin tener que reorganizar toda la estructura de datos, lo que facilita la implementación de algoritmos eficientes para diferentes operaciones.
3. Adaptabilidad a cambios dinámicos: Las listas simplemente enlazadas son especialmente útiles cuando la cantidad de datos o la estructura de los datos puede cambiar durante la ejecución del programa. Esto permite adaptarse fácilmente a cambios dinámicos en los datos sin requerir modificaciones extensas en el código.
4. Aplicaciones en una variedad de problemas: Las listas simplemente enlazadas son versátiles y se pueden utilizar en una amplia gama de problemas y aplicaciones, como la implementación de listas de reproducción en reproductores de música, la gestión de historiales de navegación en navegadores web, la manipulación de listas de tareas en aplicaciones de gestión de proyectos, entre otros.

Código para la implementación para una lista simplemente enlazada.

https://github.com/BranthonyC/EDD_UDV_2024/tree/feature/ListaSimplementeEnlazada