Lista ligada com cauda - estrutura

Aprenda sobre a estrutura da lista ligada com cauda (tail)

A lista ligada com cauda (tail), 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.

Em adição a lista ligada comum, ela contém um nó (node) extra que mantém a referência do último nó da lista, o que facilita a implementação de alguns métodos, como o de adição, o tornando mais performático.

A seguir temos uma demonstração de lista ligada com cauda (tail):

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ó.

Ainda na imagem, repare que início e fim são as duas referências mantidas na lista ligada com cauda (tail).

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 com cauda"); // 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 com cauda para representá-la de modo mais específico, ficando assim:

public class ListaLigadaCauda<T> {

    private Node<T> inicio; // referência do nó inicial da lista
    private Node<T> fim; // referência do nó final da lista

    public ListaLigadaCauda() {
        inicio = null;
        fim = null;
    }

    public Node getInicio() {
        return inicio;
    }

    public Node getFim() {
        return fim;
    }

}

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

Também não adicionamos os setters para os nós início e fim, 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:

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

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

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

Para facilitar o entendimento das diferenças entre uma lista ligada com cauda 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 com cauda (tail) 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.