Cómo Crear una Estructura de Datos Lista Ligada en Java

Crear una estructura de datos que gestione eficazmente una colección de elementos puede ser un desafío en la programación. Una de las estructuras más comúnmente utilizadas es la Lista Ligada. En esta entrada de blog, te guiaremos a través del proceso de creación de una Lista Ligada en Java, incluso si ya hay una clase incorporada disponible en la biblioteca estándar de Java.

Entendiendo el Problema

Cuando piensas en estructuras de datos, podrías pensar en arreglos, pero a veces se quedan cortos. Aquí es donde entran en juego las listas ligadas. Una Lista Ligada te permite insertar y eliminar elementos de manera eficiente sin necesidad de redimensionar un arreglo. Consiste en una secuencia de nodos donde cada nodo contiene datos y una referencia al siguiente nodo.

La Opción Incorporada

Java proporciona una clase LinkedList incorporada en el paquete java.util, que es conveniente y adecuada para muchas situaciones. Sin embargo, poder crear tu propia implementación puede profundizar tu comprensión y darte más control sobre el comportamiento de la estructura de datos.

Creando Tu Propia Lista Ligada

A continuación, exploraremos cómo construir nuestra propia Lista Ligada simple desde cero. Para este tutorial, nos enfocaremos en una lista ligada simple que permite insertar y eliminar nodos desde el inicio.

Paso 1: Definir la Clase Link

Primero, necesitamos crear una clase Link para representar cada elemento en la lista. Así es como se ve en código:

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    // Constructor de Link
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    // Imprime los datos del Link
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

Paso 2: Definir la Clase LinkList

A continuación, necesitaremos una clase para la lista completa:

class LinkList {
    private Link first;

    // Constructor de LinkList
    public LinkList() {
        first = null;
    }

    // Retorna verdadero si la lista está vacía
    public boolean isEmpty() {
        return first == null;
    }

    // Inserta un nuevo Link al principio de la lista
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    // Elimina el link al frente de la lista
    public Link delete() {
        Link temp = first;
        if (first == null) {
            return null; // o lanzar una excepción
        }
        first = first.nextLink;
        return temp;
    }

    // Imprime todos los links en la lista
    public void printList() {
        Link currentLink = first;
        System.out.print("Lista: ");
        while (currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}

Paso 3: Probar la LinkList

Finalmente, implementemos un método principal para probar nuestra Lista Ligada:

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        // Insertar algunos elementos
        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        // Imprimir la lista
        list.printList();

        // Eliminar elementos
        while (!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("eliminado: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

Conclusión

En esta entrada de blog, exploramos cómo crear una Lista Ligada personalizada en Java, completa con métodos esenciales para insertar, eliminar e imprimir nodos. Si bien la clase LinkedList nativa en la biblioteca estándar de Java puede ser suficiente para muchas aplicaciones, implementar la tuya propia puede ser una experiencia gratificante que mejora tus habilidades de programación.

Mejoras Futuras

Una vez que domines esta implementación básica, considera agregar:

• Lista Doblemente Ligada: Cada nodo debería tener referencias tanto al siguiente como al nodo anterior.
• Insertar/Eliminar en el Medio/Fondo: Métodos para añadir o eliminar nodos de varias posiciones.
• Métodos de Obtener y Ordenar: Funciones para recuperar elementos específicos o ordenar la lista ligada.

Familiarizarte con estas mejoras puede llevar tus habilidades al siguiente nivel. ¡Feliz codificación!