Lista ligada com cauda - adicionar na posição p

Aprenda a adicionar um elemento na posição p em uma lista ligada com cauda (tail)

Adicionar elementos em uma posição p é uma tarefa um pouco mais complexa do que somente adicionar no final da lista.

Pelo fato da lista ligada com cauda não possuir índices, teremos que percorrer a lista para encontrar o nó onde adicionaremos o novo elemento, fazendo as referências entre eles de modo correto.

O processo para adicionar um elemento na posição p pode ser dividido em três etapas.

A primeira delas é verificar se o índice é válido, pois a posição p onde iremos inserir o novo elemento não pode ser maior do que o tamanho da lista.

A segunda parte consiste no caso especial onde a posição a qual desejamos inserir o novo elemento é a posição 0, pois neste caso não precisaremos percorrer a lista sendo que temos acesso ao nó inicial dela diretamente na lista ligada com cauda, bastanto apenas configurar a referência do novo nó nela.

A terceira etapa consiste em percorrer a lista até a posição correta, e após isso fazer a referência do novo nó.

Para implementar a primeira etapa, onde devemos validar se a posição p é válida, precisamos do tamanho da lista, o que pode ser custoso pois teremos que percorrer a lista para descobrir o seu tamanho.

Pensando em otimizar este processo, vamos fazer uma pequena alteração na nossa classe da lista ligada com cauda, adicionando a ela um contador (int tamanho) que é incrementado e decrementado sempre que adicionamos ou removemos um elemento da lista, respectivamente.

Isto fará com que a obtenção do tamanho seja simplificada a verificação de uma variável.

Veja a seguir como a classe ListaLigadaCauda ficará após esta alteração adicionando a novo atributo tamanho:

public class ListaLigadaCauda<T> {

    private Node<T> inicio;
    private Node<T> fim;
    private int tamanho;

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

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    public Node getFim() {
        return fim;
    }

}

Com essa alteração, conseguimos implementar de modo otimizado a validação da posição p.

Vamos a seguir demonstrar como implementar este algoritmo de modo de modo gradual, passo a passo.

A seguir temos a declaração do método e a implementação da validação da posição p, onde caso ela seja inválida lançamos uma exception, conforme o código a seguir:

public void adicionar(T valor, int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }
}

Na sequência adicionamos a este método o caso especial para quando a posição é zero, pois neste caso devemos referênciar o novo nó na posição inicial, e o valor do nó inicial passará a ser uma referência do novo nó.

Devemos também atualizar o nó final da lista, onde ele referenciará o novo nó caso a lista esteja vazia, ou o nó contido em início caso exista um, conforme o código a seguir:

public void adicionar(T valor, int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    Node<T> node = new Node<>(valor);
    if (posicao == 0) {
        if (inicio != null) {
            novoNode.setProximo(inicio);
            fim = inicio;
        } else {
            fim = novoNode;
        }
        inicio = novoNode;
    }

}

Com isso, o que resta agora é adicionar o código para percorrer a lista até encontrar a posição correta para a adição, e fazer as referências corretas, e atualizar fim caso o novo nó seja adicionado na última posição da lista, conforme o código a seguir:

public void adicionar(T valor, int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    Node<T> node = new Node<>(valor);
    if (posicao == 0) {
        if (inicio != null) {
            novoNode.setProximo(inicio);
            fim = inicio;
        } else {
            fim = novoNode;
        }
        inicio = novoNode;
    } else {
        Node<T> node = inicio;
        // encontra o nó onde a nova referência será adicionada
        for (int pos = 1; pos != posicao; pos++) {
            node = node.getProximo();
        }
        // faz as referências corretas, adicionando o novo nó
        // na posição correta
        novoNode.setProximo(node.getProximo());
        node.setProximo(novoNode);
    }

    // caso adicionado na última posição,
    // atualizamos o valor de fim para o novo nó
    if (posicao == tamanho) {
        fim = novoNode;
    }

}

Repare que adicionamos este código como else no if existente, pois ele será executado para toda posição p válida e maior do que zero.

Para finalizar, precisamos incrementar o novo atributo tamanho que adicionamos na classe, pois assim conseguimos obter seu tamanho de modo simplificado.

A seguir temos o código completo do método:

public void adicionar(T valor, int posicao) {
    // posição deve ser maior do que 0 e menor do que o tamanho da lista
    if (posicao < 0 || posicao >= tamanho) {
        throw new IllegalArgumentException("Posição inválida");
    }

    Node<T> node = new Node<>(valor);
    if (posicao == 0) {
        if (inicio != null) {
            novoNode.setProximo(inicio);
            fim = inicio;
        } else {
            fim = novoNode;
        }
        inicio = novoNode;
    } else {
        Node<T> node = inicio;
        // encontra o nó onde a nova referência será adicionada
        for (int pos = 1; pos != posicao; pos++) {
            node = node.getProximo();
        }
        // faz as referências corretas, adicionando o novo nó
        // na posição correta
        novoNode.setProximo(node.getProximo());
        node.setProximo(novoNode);
    }

    // caso adicionado na última posição,
    // atualizamos o valor de fim para o novo nó
    if (posicao == tamanho) {
        fim = novoNode;
    }

    tamanho++; // incrementa o tamanho da lista

}

E para finalizar, vamor ver o novo método adicionado ao código da classe da lista ligada:

public class ListaLigadaCauda<T> {

    private Node<T> inicio;
    private Node<T> fim;
    private int tamanho;

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

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    public Node getFim() {
        return fim;
    }

    public void adicionar(T valor, int posicao) {
        // posição deve ser maior do que 0 e menor do que o tamanho da lista
        if (posicao < 0 || posicao >= tamanho) {
            throw new IllegalArgumentException("Posição inválida");
        }

        Node<T> node = new Node<>(valor);
        if (posicao == 0) {
            if (inicio != null) {
                novoNode.setProximo(inicio);
                fim = inicio;
            } else {
                fim = novoNode;
            }
            inicio = novoNode;
        } else {
            Node<T> node = inicio;
            // encontra o nó onde a nova referência será adicionada
            for (int pos = 1; pos != posicao; pos++) {
                node = node.getProximo();
            }
            // faz as referências corretas, adicionando o novo nó
            // na posição correta
            novoNode.setProximo(node.getProximo());
            node.setProximo(novoNode);
        }

        // caso adicionado na última posição,
        // atualizamos o valor de fim para o novo nó
        if (posicao == tamanho) {
            fim = novoNode;
        }

        tamanho++; // incrementa o tamanho da lista

    }

}

Repare que esta implementação é um pouco mais complexa do que na lista ligada, pois como temos o novo nó fim na lista, devemos mantê-la atualizada a cada alteração, o que adiciona um pouco mais de complexidade ao algoritmo.

Com isso finalizamos a implementação do método para adicionar na lista na posição p, que embora ela possua mais passos, se estudado de modo separado fica simples de entender o processo de adição na posição p.