Lista ligada - estrutura

Aprenda sobre a estrutura da lista ligada

A lista ligada, ao contrário de uma lista comum, ela é formada por nós, ou node, que é representado por uma classe que contém internamente o valor do nó, e a referência para o próximo nó da lista.

A seguir temos uma demonstração de lista ligada:

Repare na imagem acima, que cada nó contém um valor (10, 23, 14 e 36), e a referência para o próximo nó.

O último nó da lista ligada contém null como valor, pois ele não faz referência a nenhum outro nó.

Pelo fato desta estrutura ser padrão e para otimizarmos a sua implementação para suportar a criação de uma lista ligada de qualquer tipo, podemos usar o recurso de generics do Java em sua implementação.

A seguir temos a implementação da classe nó, que chamaremos aqui de node.

public class Node<T> {
    private final T valor;
    private Node proximo;

    public Node(T valor) {
        this.valor = valor;
    }

    public T getValor() {
        return valor;
    }

    public Node<T> getProximo() {
        return proximo;
    }

    public void setProximo(Node<T> node) {
        proximo = node;
    }

}

O código acima é de fácil entendimento, ele é composto por uma classe padrão em Java com dois atributos, um construtor e os getters e setters definidos para os atributos.

O uso do generics é feito ao declararmos T na classe, onde a usamos da seguinte forma para criarmos listas ligadas de diferentes tipos:

Node n1 = new Node<Integer>(10); // criação de um node do tipo inteiro contendo o valor 10
Node n2 = new Node<String>("Lista ligada"); // criação de um node do tipo string contendo o valor "Lista ligada"
    

Pelo fato desta classe ser muito genérica, o que podemos fazer é definir uma classe para a lista ligada para representá-la de modo mais específico, ficando assim:

public class ListaLigada<T> {

    private Node<T> inicio;

    public ListaLigada() {
        inicio = null;
    }

    public Node getInicio() {
        return inicio;
    }

}

Repare no código acima como esta classe é simples, e apenas contém o nó inicial dela, pois os outros elementos poderão ser acessados diretamente pelo nó inicial, conforme veremos na próxima aula.

Também não adicionamos o setter para o nó início, porque teremos o método adicionar para adicionar novos nós na lista.

Esteja ciente também que ao longo das próximas aulas, adicionaremos métodos para esta classe para executar as operações básicas nela, como adicionar ou remover elementos na lista.

Com esta classe implementada, sua utilização é simples conforme o código a seguir:

ListaLigada l1 = new ListaLigada<Integer>(); // criação de uma lista ligada do tipo inteiro
ListaLigada l2 = new ListaLigada<String>(); // criação de uma lista ligada do tipo string
    

Com isso já temos a implementação da estrutura básica de uma lista ligada, e nas próximas aulas adicionaremos mais recursos a ela, mas antes disso vamos entender as diferenças entre uma lista ligada e uma lista nativa.

Diferenças entre uma lista ligada e uma lista nativa (array)

Para facilitar o entendimento das diferenças entre uma lista ligada e uma lista nativa (array), elas serão listadas em formato de tabela a seguir:

Resumindo a tabela acima, podemos concluir que as listas ligadas são mais eficientes caso precisamos realizar muitas operações de adição e remoção de elementos, enquanto que as listas nativas (array) são melhores caso você precise realizar muitos acessos de leitura de dados na array.