Lista ligada - adicionar na posição p

Aprenda a adicionar um elemento na posição p em uma lista ligada

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 não tem í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, 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, 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 ListaLigada ficará após esta alteração adicionando a novo atributo tamanho:

public class ListaLigada<T> {

    private Node<T> inicio;
    private int tamanho;

    public ListaLigada() {
        inicio = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

}

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ó, ficando 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");
    }

    if (posicao == 0) {
        Node<T> node = new Node<>(valor);
        node.setProximo(inicio);
        inicio = node;
    }
}

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, 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");
    }

    if (posicao == 0) {
        Node<T> node = new Node<>(valor);
        node.setProximo(inicio);
        inicio = node;
    } else {
        // registra a posição atual
        int posicaoAtual = 1;
        Node<T> node = inicio;
        // busca o node da posição p
        while (posicao != posicaoAtual) {
            node = node.getProximo();
            posicaoAtual++;
        }
        // insere na lista o novo nó atualizando as referências
        Node<T> novoNode = new Node<>(valor);
        novoNode.setProximo(node.getProximo());
        node.setProximo(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");
    }

    if (posicao == 0) {
        Node<T> node = new Node<>(valor);
        node.setProximo(inicio);
        inicio = node;
    } else {
        // registra a posição atual
        int posicaoAtual = 1;
        Node<T> node = inicio;
        // busca o node da posição p
        while (posicao != posicaoAtual) {
            node = node.getProximo();
            posicaoAtual++;
        }
        // insere na lista o novo nó atualizando as referências
        Node<T> novoNode = new Node<>(valor);
        novoNode.setProximo(node.getProximo());
        node.setProximo(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 ListaLigada<T> {

    private Node<T> inicio;
    private int tamanho;

    public ListaLigada() {
        inicio = null;
        tamanho = 0;
    }

    public int getTamanho() {
        return tamanho;
    }

    public Node getInicio() {
        return inicio;
    }

    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");
        }

        if (posicao == 0) {
            Node<T> node = new Node<>(valor);
            node.setProximo(inicio);
            inicio = node;
        } else {
            // registra a posição atual
            int posicaoAtual = 1;
            Node<T> node = inicio;
            // busca o node da posição p
            while (posicao != posicaoAtual) {
                node = node.getProximo();
                posicaoAtual++;
            }
            // insere na lista o novo nó atualizando as referências
            Node<T> novoNode = new Node<>(valor);
            novoNode.setProximo(node.getProximo());
            node.setProximo(novoNode);
        }
        tamanho++; // incrementa o tamanho da lista
    }

}

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.