Como Criar uma Estrutura de Dados Lista Ligada em Java

Criar uma estrutura de dados que gerencie de forma eficaz uma coleção de elementos pode ser um desafio na programação. Uma das estruturas mais comumente usadas é a Lista Ligada. Neste post do blog, vamos guiá-lo pelo processo de criação de uma Lista Ligada em Java, mesmo que já exista uma classe integrada disponível na biblioteca padrão do Java.

Entendendo o Problema

Quando você pensa em estruturas de dados, pode pensar em arrays, mas às vezes eles não são suficientes. É aqui que as listas ligadas entram em cena. Uma Lista Ligada permite que você insira e exclua elementos de forma eficiente, sem precisar redimensionar um array. Ela consiste em uma sequência de nós, onde cada nó contém dados e uma referência ao próximo nó.

A Opção Integrada

Java fornece uma classe integrada LinkedList no pacote java.util, que é conveniente e adequada para muitas situações. No entanto, ser capaz de criar sua própria implementação pode aprofundar sua compreensão e dar mais controle sobre o comportamento da estrutura de dados.

Criando Sua Própria Lista Ligada

Abaixo, vamos explorar a construção de nossa própria Lista Ligada simples do zero. Para este tutorial, focaremos em uma lista ligada simples que permite inserir e excluir nós do início.

Passo 1: Definir a Classe Link

Primeiro, precisamos criar uma classe Link para representar cada elemento na lista. Veja como é o código:

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

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

    // Imprimir dados do Link
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

Passo 2: Definir a Classe LinkList

Em seguida, precisamos de uma classe para a lista como um todo:

class LinkList {
    private Link first;

    // Construtor LinkList
    public LinkList() {
        first = null;
    }

    // Retorna true se a lista estiver vazia
    public boolean isEmpty() {
        return first == null;
    }

    // Insere um novo Link no início da lista
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    // Exclui o link na frente da lista
    public Link delete() {
        Link temp = first;
        if (first == null) {
            return null; // ou lançar Exceção
        }
        first = first.nextLink;
        return temp;
    }

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

Passo 3: Testando a LinkList

Finalmente, vamos implementar um método main para testar nossa Lista Ligada:

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

        // Inserir alguns 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 a lista
        list.printList();

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

Conclusão

Neste post do blog, exploramos como criar uma Lista Ligada personalizada em Java, completa com métodos essenciais para inserir, excluir e imprimir nós. Embora a classe LinkedList nativa na biblioteca padrão do Java possa ser suficiente para muitas aplicações, implementar a sua própria pode ser uma experiência gratificante que aprimora suas habilidades de programação.

Melhorias Futuras

Após dominar essa implementação básica, considere adicionar:

• Lista Duplamente Ligada: Cada nó deve ter referências aos nós seguinte e anterior.
• Inserir/Excluir no Meio/Fim: Métodos para adicionar ou remover nós de várias posições.
• Métodos de Obter e Ordenar: Funções para recuperar elementos específicos ou ordenar a lista ligada.

Familiarizar-se com essas melhorias pode levar seu conjunto de habilidades para o próximo nível. Boas codificações!